天下一プログラマーコンテスト 2015

予選A-C 「天下一美術館」

問題文はこちら。

想定解法は動的計画法(Dynamic Programming, DP)を使った解法です。アートを上から1段づつ変換していくことで、コストの最低値を見つけます。

以下のような例を考えます

アートA

□■
■□
□□

アートB

■□
□■
■□

どちらのアートからの変換を考えた場合でも最低のコストは同じになるので、ここではアートAからアートBへの変換を考えます。

まず、アートAの1段目がBと一致するように変換した後に、アートAの状態としてありえるのは以下の4通りです。

■□
□□
□□

↑の状態までの最低コストは2

■□
■□
□□

↑の状態までの最低コストは1

■□
□■
□□

↑の状態までの最低コストは2

■□
■■
□□

↑の状態までの最低コストは2

ここで注目すべきなのは、この4つの状態について異なるのは2段目のみであり2段目の情報だけをつかってコストの情報を持てば良いということです。

■□
○○ ←この行の情報だけ記録しておけばいい
□□

つまり2段目の状態を2進数で表現し、以下のような配列で持つことが可能です。

cost[00] = 2
cost[01] = 2
cost[10] = 1
cost[11] = 2

この2段目の情報から、次は以下の状態へ持っていくのに必要なコストを計算します

■□
□■
○○ ←この行については、4通りの状態がありうる

このとき3段目の各状態を2進数で表現した場合、各状態までに必要なコストは以下のとおりです

cost[00] = 2
cost[01] = 3
cost[10] = 3
cost[11] = 4

さらに、この4種類の状態から以下の状態に持っていきます。

■□
□■
■□

この状態にもっていくまでに、必要なコストは3です。よってこの場合の答えは3です。

この解法では、 O(2^N * N * M) で答えが出ますから、N, M <= 10であれば十分に間に合います

まず、前提条件として以下の4つの点を確認しておきます。

色の変更（黒マスから白マスへの変換、または白マスから黒マスへの変換）を行ったマスを、もう一度色の変更を行っても、コスト2を使ってもとに戻るだけなので、禁止しても答えは変わらない。
- 例: ■ → □ → ■
同じ色のマスどおしでマスの交換をしても、コスト1を使って何も変わらないので、禁止しても答えは変わらない。
- 例: ■■ → ■■
1マスに対して2回マスの交換を適用する行為はコスト2かかるが、2回以下の色の変更によって代替できるので、禁止しても答えは変わらない
- 例: □■■ → ■□■ → ■■□ は、□■■ → ■■■ → ■■□で代替できる
一度、マスの交換を行ったマスに対して色の変換を行う行為はコスト2だが、色の変更1回によって代替できるので、禁止しても答えは変わらない
- 例: □■ → ■□ → ■■

さて、以下の2つのアートの相違度を求めてみます

アートC

■■■□
■■□■
■□■□
□■■■
■□■□

アートD

□■■■
□□■□
■■□■
■■□■
□■□■

前提条件から、各マスについて行える操作は色の変更かマスの交換のどちらか1回のみです。

すでに2つのアートで一致しているマスについて色が変わってしまうと元に戻すことはできません。つまり、既に一致しているマスについては変更が出来ないものとして無視することができます。

既に一致しているマスを除いたアートCは以下のとおりです。

■××□
■■□■
×□■□
□×■×
■□■□

残りのマスについて、色の変更かマスの交換のどちらかを1回だけ適用して、白マスを黒マスに、黒マスを白マスに変更する問題を考えます。

ここで以下のことに注目します

つまり、マスの交換の方が効率的ですから、なるべく多く白マスと黒マスの交換を適用したいです。

なるべく多く白マスと黒マスをマッチングする問題ですから、これは2部グラフの最大マッチング問題です。

2部グラフの最大マッチングは、最大フロー問題のアルゴリズムで求められることが知られています。

最大マッチングでマッチングされなかった残りのマスは、コスト1で色の変更を行えば良いです。よって、相違度は (最大マッチング数) + (余ったマスの数)で求めることが出来ます。

また、これは(2つのアートで異なるマスの数) - (最大マッチング数)に等しいので、こちらの式で求めても構いません。

アートC、アートDの場合、異なるマスの数は15、最大マッチング数は5、余ったマスの数は5で、答えは10です。

なお、この解法の計算量は O(H ^ 2 * W ^ 2) となります。