2014年06月28日
■動的計画法の問題を機械的に解く方法
情報オリンピックという中高生向けの競技プログラミングの大会があります。国内予選・選抜が3回あり、最後に世界大会があります。アルゴリズムの問題が出題されます。予選の毎年のパターンは問1, 2は問題文をコードに起すだけの問題で、問3はアルゴリズムの問題だったり、中学受験的な算数の問題だったりします。問4はいつも動的計画法の問題が出ます。競技プログラミングでは動的計画法が一番の入門であり、これがスタートラインです。これが解けないと始まりません。動的計画法の問題、機械的に解けるのかなと思い色々と考えたのですが、できそうなので、このブログ記事にまとめます。
動的計画法
動的計画法ですが、やはり一番しっかり書かれているのが、書籍「アルゴリズムイントロダクション」 http://www.amazon.co.jp/dp/476490408X です。動的計画法の章は熟読に値すると思います。「動的計画法」という言葉の定義は若干人によってブレがあるのですが、アルゴリズムイントロダクションの定義に従いますと、以下の2つを行うアルゴリズムの総称です。
なお、トップダウン（全体問題を解いてから部分問題を解く）とボトムアップ（部分問題を解いてから全体問題を解く）という2つの実装方法があるのですが、これは、あくまでも実装方法の話であり、トップダウンをボトムアップに置き換えるのは機械的な作業であり、本ブログ記事ではトップダウンで記事を書きます。トップダウンはメモ化再帰とも呼ばれます。
そして、このように定義は広いにもかかわらず、実際に出題されるのは、もっと狭い範囲で出題されます。問題文はこのパターンばかりです。
デカルト冪(リスト, N).findAll { list -> 問題文の条件に合うリストを絞り込む }.collect { list -> list を整数に変換 }.集約関数()
上記を含め、以下、Groovy 風の擬似コードを使います。Groovy は Java の文法を拡張しているのですが、{ } でクロージャを作れて、メソッドの引数がクロージャ1つの時はメソッド名の後の ( ) が省略可能です。あと、collect メソッドは、リストの各要素をクロージャにわたし、その返り値から新しいリストを作るメソッドです。あと、1..3 という表記は [1, 2, 3] のリストという表記です。あと、記事の書きやすさの都合上、Groovy とは異なるのですが、リストの添え字は 1 から始まると言うことにさせてください。
デカルト冪の定義は 直積集合 - Wikipedia に書いてありますが、例えば、デカルト冪(1..2, 3) == [ [1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 2, 2], [2, 1, 1], [2, 1, 2], [2, 2, 1], [2, 2, 2] ] です。リストのリストです。
集約関数は max(), min(), sum() のどれかです。場合の数を数える問題も良く出ますが、その際は collect { 1 }.sum() にすると、統一的にこの表記になります。
解法の手順
解法の手順は以下の通りです。詳しくは具体例で説明していきます。
- リスト末尾 k 個を定数化します（k は通常 1〜3 です）。findAll 内の定数をまとめ、collect 内の定数は集約関数の外に出します。
- ループ1つ前のリスト末尾 k - 1 個を定数化します。
- 1 と 2を比較して、代入します。
定数化するというのは場合分けをするという意味です。以下、読んでいくとその意味が分かると思います。また、出題パターンとして、部分問題に分ける際は、N を 1 と N - 1 に分ける問題ばっかりです。
0-1ナップサック問題
動的計画法の一番基本的な問題は、0-1ナップサック問題です。これの派生形で出題されます。問題文は ナップサック問題 - Wikipedia を読んでください。これを擬似コードにおこすと以下のようになります。
答え(N) = デカルト冪(0..1, N).findAll { list -> (1..N).collect { i -> c[i] * list[i] }.sum() <= C }.collect { list -> (1..N).collect { i -> p[i] * list[i] }.sum() }.max()
配列 c や p は問題から与えられる定数配列です。N や C も int 定数。
では、解法。この問題では、リストの末尾1つを定数化します。X = list[N] と置きます。すると、こう変形できます。
f1(N, X) = デカルト冪(0..1, N - 1).findAll { list -> (1..(N - 1)).collect { i -> c[i] * list[i] }.sum() + c[N] * X <= C }.collect { list -> (1..(N - 1)).collect { i -> p[i] * list[i] }.sum() + p[N] * X }.max()
ここで、c[N] * X も p[N] * X も定数です。findAll において、C が定数なので、引き算して一つにまとめます。また、collect の方は、定数の足し算を集約関数の外に出すことができます。この手順も、毎回毎回行うパターンです。この変形を行うと、以下のようになります。
f1(N, X) = デカルト冪(0..1, N - 1).findAll { list -> (1..(N - 1)).collect { i -> c[i] * list[i] }.sum() <= C - c[N] * X }.collect { list -> (1..(N - 1)).collect { i -> p[i] * list[i] }.sum() }.max() + p[N] * X
次に、ループ回数を一つ減らした物を考えます。上記で、リスト末尾 k 個を定数化したときは、こちらでは k - 1 個を定数化する必要あるのですが、ここでは、k = 1 だったので、一つも定数化しません。 k >= 2 の例はこの先、別な問題でやります。
答え(N - 1) = デカルト冪(0..1, N - 1).findAll { list -> (1..(N - 1)).collect { i -> c[i] * list[i] }.sum() <= C }.collect { list -> (1..(N - 1)).collect { i -> p[i] * list[i] }.sum() }.max()
で、この2つの擬似コードを比べると、ほとんど同じ形です。C と C - c[N] * X の違いがあるので、この部分を変数 y と置きます。
f2(N - 1, y) = デカルト冪(0..1, N - 1).findAll { list -> (1..(N - 1)).collect { i -> c[i] * list[i] }.sum() <= y }.collect { list -> (1..(N - 1)).collect { i -> p[i] * list[i] }.sum() }.max()
f1 の方も、C を引数に入れちゃいます。
f1(N, X, C) = デカルト冪(0..1, N - 1).findAll { list -> (1..(N - 1)).collect { i -> c[i] * list[i] }.sum() <= C - c[N] * X }.collect { list -> (1..(N - 1)).collect { i -> p[i] * list[i] }.sum() }.max() + p[N] * X
すると、
f1(N, X, C) = f2(N - 1, C - c[N] * X) + p[N] * X
になります。また、答え(N - 1) = f2(N - 1, C) つまり 答え(N) = f2(N, C) です。
そして、X = list[N] は末尾1つを定数化して作った物なので、以下の等式が成立します。
答え(N) = (0..1).collect { x -> f1(N, x, C) }.max()
まとめると、以下の式ができました。
答え(N) = f2(N, C) = (0..1).collect { x -> f1(N, x, C) }.max() f1(N, x, C) = f2(N - 1, C - c[N] * x) + p[N] * x
下の式を上の式に代入して、以下の通りです。
答え(N) = f2(N, C) = (0..1).collect { x -> f2(N - 1, C - c[N] * x) + p[N] * x }.max()
f2 の N が1ずつ減っていくループになっています。
ただし、ループの最後、f2(1, ?) は、省略してしまったのですが、別扱いで書いてください。最初の問題文に N = 1 を代入すると出ます。
答え(1) = デカルト冪(0..1, 1).findAll { list -> (1..1).collect { i -> c[i] * list[i] }.sum() <= C }.collect { list -> (1..1).collect { i -> p[i] * list[i] }.sum() }.max()
整理すると、以下のようになります。
答え(1) = デカルト冪(0..1, 1).findAll { list -> c[1] * list[1] <= C }.collect { list -> p[1] * list[1] }.max()
もっと整理すると、以下のようになります。-∞は詰められないパターンです。空リスト.max() == -∞ としました。
答え(1) = c[1] <= C ? p[1] : (0 <= C ? 0 : -∞)
そして、あとは、f2 の引数が同じなら、返り値は常に一緒なので、メモ化すればOKです。ボトムアップなら配列に書けば良いです。ここから更に整理したり高速化したり少々できますが枝葉末節なので省略します。
JOI 2014年予選問4
さて、2013年12月に開催された、2014年予選問4です。問題文は http://www.ioi-jp.org/joi/2013/2014-yo/2014-yo-t4/2014-yo-t4.html 。擬似コードにおこすと以下の通りです。every() メソッドは全て true の時に true になるという Groovy のメソッドです。問題文は鍵に関する部分があるのですがその部分は連続同じ人が出席する必要があるという形で整理済みです。
答え(N) = デカルト冪(0..7, N).findAll { list -> (list[1] & 1 != 0) && (2..N).every { i -> list[i] & list[i - 1] != 0 } && (1..N).every { i -> list[i] & P[i] != 0 } }.collect { list -> 1 }.sum()
このように、list[i] & list[i - 1] のように配列の2つの要素にアクセスしているときは、定数化すべきは 2 個になります。全く同じ手順ですすめますね。リスト末尾2つを定数化し、X1 = list[N], X2 = list[N - 1] とします。
f1(N, X1, X2) = デカルト冪(0..7, N - 2).findAll { list -> (list[1] & 1 != 0) && (2..(N - 2)).every { i -> list[i] & list[i - 1] != 0 } && (X2 & list[N - 2] != 0) && (X1 & X2 != 0) && (1..(N - 2)).every { i -> list[i] & P[i] != 0 } && (X2 & P[N - 1] != 0) && (X1 & P[N] != 0) }.collect { list -> 1 }.sum()
ループの1つ前にリスト末尾1つ、つまり、X2 = list[N - 1] だけを定数化した物はこのようになります。
f2(N - 1, X2) = デカルト冪(0..7, N - 2).findAll { list -> (list[1] & 1 != 0) && (2..(N - 2)).every { i -> list[i] & list[i - 1] != 0 } && (X2 & list[N - 2] != 0) && (1..(N - 2)).every { i -> list[i] & P[i] != 0 } && (X2 & P[N - 1] != 0) }.collect { list -> 1 }.sum()
記事の都合上、N を具体化していないのですが、3 とか 4 とか具体的な数字を入れて取り扱うと、より分かりやすく、簡単になります。
で、いつも通り、この2つを比較すると、(X1 & X2 != 0) と (X1 & P[N] != 0) という定数が増えていて、かつ、これらが false だと、findAll のクロージャが常に false になり、全体が 0 になるので、
f1(N, X1, X2) = (X1 & X2 != 0) && (X1 & P[N] != 0) ? f2(N - 1, X2) : 0
と分かります。
また、末尾定数化により、答えやf2は以下の形で表現できます。
答え(N) = (0..7).collect { x1 -> f2(N - 1, x1) }.sum() f2(N - 1, x1) = (0..7).collect { x2 -> f1(N - 1, x1, x2) }.sum()
あとは、さっきの式で f1 が f2 より求まり、f1, f2, f1, f2 と行ったり来たりするループが出来上がります。そして、ループの最後は、答え(2) を整理すればＯＫです。加えてメモ化をします。
JOI 2013年予選問4
本当にワンパターンですが、一応軽く2012年12月の2013年予選4も触れます。問題文は http://www.ioi-jp.org/joi/2012/2013-yo/2013-yo-t4/2013-yo-t4.html 。擬似コードにおこすと以下の通りです。
答え(D) = デカルト冪(1..N, D).findAll { list -> (1..D).every { i -> A[list[i]] <= T[i] && T[i] <= B[list[i]] } }.collect { list -> (2..D).collect { i-> abs(C[list[i - 1]] - C[list[i]]) }.sum() }.max()
今回はループ変数は D です。そして、list[i - 1] と list[i] を使ってるので、定数化は2個です。
f1(D, X1, X2) = デカルト冪(1..N, D - 2).findAll { list -> (1..(D - 2)).every { i -> A[list[i]] <= T[i] && T[i] <= B[list[i]] } && A[X2] <= T[D - 1] && T[D - 1] <= B[X2] && A[X1] <= T[D] && T[D] <= B[X1] }.collect { list -> (2..(D - 2)).collect { i -> abs(C[list[i - 1]] - C[list[i]]) }.sum() + abs(C[list[D - 2]] - C[X2]) + abs(C[X2] - C[X1]) }.max()
collect の中の定数 abs(C[X2] - C[X1]) は集約関数 max の外出しです。で、ループ1つ前の末尾1つだけ定数化したのは、
f2(D - 1, X2) = デカルト冪(1..N, D - 2).findAll { list -> (1..(D - 2)).every { i -> A[list[i]] <= T[i] && T[i] <= B[list[i]] } && A[X2] <= T[D - 1] && T[D - 1] <= B[X2] }.collect { list -> (2..(D - 2)).collect { i -> abs(C[list[i - 1]] - C[list[i]]) }.sum() + abs(C[list[D - 2]] - C[X2]) }.max()
代入すると、以下の通りです。空リスト.max() == -∞ としました。
f1(D, X1, X2) = A[X1] <= T[D] && T[D] <= B[X1] ? f2(D - 1, X2) + abs(C[X2] - C[X1]) : -∞
末尾定数化したと言うことより、
答え(D) = (1..N).collect { x1 -> f2(D - 1, x1) }.max() f2(D - 1, x1) = (1..N).collect { x2 -> f1(D - 1, x1, x2) }.max()
と同じ話が続き、ループの最後の 答え(2) は別枠で整理したらメモ化して完成です。
2012年予選4も2011年予選4も同じ解法で解くことができます。