Skip to content

Instantly share code, notes, and snippets.

@n-ari
Created May 26, 2016 14:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save n-ari/cf7fe6a608a6b62b9fc5152694684356 to your computer and use it in GitHub Desktop.
Save n-ari/cf7fe6a608a6b62b9fc5152694684356 to your computer and use it in GitHub Desktop.
2016 05/26 traPcontest

160526

実装系を多めにしてみました。 なお今日は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ナップサック問題です。

Javaによる解答例

動的計画法

まず、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にあります。確認がてら解いてみましょう。↑で説明したことを実装するといい感じです。

http://abc032.contest.atcoder.jp/tasks/abc032_d

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment