実装系を多めにしてみました。 なお今日はJavaで書いてみました。慣れない。
- A : 落ち着いて問題文を読んでループを実装
- B : 1行入力するメソッドがわかれば(C++:getline, Java:nextLine)、文字を1文字ずつ見るだけ。Javaはsplit(" ")で長さを取るだけ。
- C : ソートします。私はクラスを作ってソートしました(Javaの書き方わからない......)
- D : 誰をどっちに入れるかを2^Nパターン全探索します。ビット演算を使うと楽。DFS(再帰)のほうが速い
- E : 実装がやばい 基本的にBFSを書きます。ステップの回数は決め打ちで良いかと (ゴーストが10ステップで20x20を飛び回るので20x10x2=400ぐらいあると良い)
- F : 動的計画法の典型です。解説では終点から広げましたが私のコードはf(x,y):=(0,0)から(x,y)までの通り数 としてDPを書いています。
- G : こちらも動的計画法の典型、0-1ナップサック問題です。
- A : http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1824743#1
- B : http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1824767#1
- C : http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1824836#1
- D : http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1824880#1
- E : http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1825191#1
- F : http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1825232#1 (配るDP)
- F2: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1825246#1 (貰うDP)
- G : http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1825278#1
まず、DFS(深さ優先探索、再帰)では、問題のサイズを落とすことを考えます。
例えば今回のFであればゴールに近い解を足しあわせたり、GではN-1個の解から求めたりします。
すると、再帰関数を使って、漸化式のようなものが求まります(添字が小さい奴にのみ依存する式)。
ここで漸化式となれば、小さい方から値を決定してその値を保存しておけば、次の値を効率よく求められます。
これが**「メモ化再帰」や「動的計画法」(DP)**です。
なので、動的計画法を考える基本は、問題のサイズを落とすことにあります。式が立たなければDPも立ちません。
なお、計算量はO( 状態数 × 1状態の解を計算する計算量 )となります。
Fであれば状態数はW*H、1状態の計算は足し算するだけなので1、よってO(WH)です。
Gであれば状態数はN*W、1状態の計算はやはり足し算するだけなのでO(NW)です。
ちなみに、今回のDは2^Nの全探索ですが、これも0-1ナップサックを行ってどのような値を取れるかを計算しておき、 合計値の半分に近い値を探す、ということも出来ます。
今回はN<=20のため2^Nのほうが速いですが、Nが大きく、値が小さい場合は、G同様のナップサックが有効となります。
ナップサック問題はDPの典型問題としてかなり有名な問題です。
この問題の一般的なもの(制約のないもの)はNP困難(指数時間でしか計算出来ない)というクラスに所属しています。
基本的な全探索方針は各アイテムに対して取る/取らないの2択を繰り返すため、O(2^N)となります。
この有名な高速化がDPです。Nが大きくWが小さい場合は、重さが同じになるような組み合わせが多く発生します。
そのような状態の重複を、DPテーブルで管理することで排除され、状態数が削減されます(上記の通りO(NW))。
また、逆に価値の総和(V)が小さい場合は、逆に「dp[i][v] := i個のアイテムで価値vを達成する最小の重さ」とすることで解けます。
こちらはO(NV)となります。
最後に、半分全列挙というDPとは違う方針のものがあります。
これは、N/2ずつのグループに分け、それぞれで全探索を行います。これはO(2^(N/2))です。
次にその2つのグループをうまい具合に合体させます。まぁ二分探索系を使うのですが、すると全体でO(2^(N/2) log(2^(N/2)) )となります。
つまりO(2^(N/2) * N)です。
このようにナップサック問題はあらゆるアプローチが可能で、使い分けが大事です。
という問題がABCにあります。確認がてら解いてみましょう。↑で説明したことを実装するといい感じです。