Competitive Programming Advent Calendar Div2013の21日目の記事です。この記事では自分が今まで解いた問題の中で解法に衝撃を受けたものを2つほど紹介したいと思います。去年と一昨年の記事は一応初級者の方の上達に役に立つかもしれないものだったのに対し今年のは本当に誰にとって得なのか良く分からない個人的な趣味だけで書いた記事ですがよろしければお付き合い下さい。
問題概要
赤青黄緑の4色のボールをシリンダーに入れていく。上のL個のボールの色が同じだとそのL個のボール全てが消える。ボールを順番にN個入れた後シリンダーが空になるようなボールの入れ方は何通りあるか。
要するに一列のぷよぷよです。題意が良く伝わらなかった場合はすみませんが上のリンクから原文を見て下さい。さて、本番でこの問題を見た時は「A個目からB個目までのボールで全部消える並び方」を区間DPで求めることを考えてたのですが、O(N^3)なので計算量が危ないですし、そもそも重複なく数え上げるのが大変で解けずじまいでした。
ですが、SRM終了後のLayCurseさんの放送を見て衝撃を受けました。解法はやはりDPだったのですが、その更新式はたったこれだけだったのです。
if(j==0) dp[i+1][L-1]+=dp[i][j]*4;
else{
}
どういうことかというと、「i個目まで入れた」というのに加えて、「あと最低j個のボールを入れれば全部消える」という情報をキーに持ってDPを行うのです。そうすると、次に4色のボールのうち正しい色のボールを入れれば「全部消えるために入れる必要のある最小のボールの数」は1つ減り、それ以外の3色のボールを入れれば、まずそのボールと同じ色のボールをL個つなげて消さなくてはいけないので、「全部消えるために入れる必要のある最小のボールの数」はL-1個増えるのです。
ただし、「全部消えるために入れる必要のある最小のボールの数」が0個、つまりi個目までボールを入れた状態で既に全部のボールが消えている場合には、どの色のボールを入れても「全部消えるために入れる必要のある最小のボールの数」はL-1個増えるので、そこだけは例外扱いする必要があります。
それにしても、本番中1時間くらい考えても全然分からなかった問題が、こんなにシンプルに解けてしまうことに衝撃を受けました。
続いては最小カットです。最小カットは最大フローと等しいので、問題を最小カットに帰着できれば最大流ライブラリを用いて解くことができるという形で、競技プログラミングではしばしば用いられる定理です。最近のSRMのMedium問題にこの題材が出されたり、また診断人さんの生放送で最小カット講座が行われたりしているので、ご存知の方も多いかもしれません。
自分もこの定理は（競技プログラミングにおいては）「最小カットを求めるためのもの」と思っていましたが、次の問題を見てその考えを改めることになります。
問題概要
平行な壁に囲まれた通路に、いくつかの断面が凸多角形となる高さ無限の柱があります。風が通路の入り口から出口に向かって吹いているとき、1秒ごとに通路で流されることができる空気の最大量を求めなさい。ただし、幅wの通り道に対して風は1秒ごとに最大でwの空気量だけ通ることができる。
相変わらず概要が分かり辛くてすみません…。要するに「通路の入り口から出口までの最大フローを求める」という問題なのですが、多角形同士の位置関係をグラフに落とし込むのが極めて難しいです。恐らく、空間を適切に分割して、それぞれの分割された空間が点、分割された空間同士の間にある線分が辺（そしてその線分の長さが辺の容量）というグラフを作ることが出来れば解けるのでしょうが…。
解放の糸口すらつかめず諦めて解答（正解者のコード）を見てしまったのですが、これが予想より遥かにシンプルでびっくり。両側の壁と各柱を点として、2点間の辺の長さは相当する物体同士の最短距離、というグラフを作り、片方の壁からもう片方の壁までの最短距離を求める、といったものでした。
最初に解答を見たときは何故これで正しい答えが出るのかすぐには分かりませんでしたが、つまり
最小カットを求めることで、最大フローを求める
という解法だったのです。
片側の壁からもう片側の壁までの経路に壁を作れば風は全く通ることができません。つまりこの経路の長さがカットの大きさになっているので、最小カット＝最短経路を求めれば最大フローが求まるという訳です。この最大フロー最小カット定理を逆パターンで使う問題は初めてみたので中々に衝撃的でした。
短い上に本当に誰が得するのか分からない記事になってしまってすみません（汗）。ただ、このように解法を知った時のインパクトが大きいと、解法が頭に残りやすく次に似たような問題に当たった時に参考にしやすいのでいいですね。自分もこの記事を書くときに他にも衝撃的な解法だった問題が無かったか思い出そうとしたものの思い出せず…。この程度しか記憶に残ってないので最近コンテストで中々思うように行かないのかもしれませんね（汗）。
今年も残り10日ほどとなりました。一応まだSRMやCodeforcesなどがいくつか残ってはいますが、みなさん今年1年間お疲れ様でした。また来年も競技プログラミングを頑張りましょう。よいお年を！