SRM 464

writerをやっていました。いかがだったでしょうか？
Editorialを執筆中なので詳しい解説は後日そちらを参照してください。また Practice Room にofficialな解答を上げています。
以下に出題した5問について簡単なコメントを。

ColorfulBoxesAndBalls (Div 2 250)

赤箱青ボールと青箱赤ボールが必ず同じ個数なので、それについて [0, min(numRed, numBlue)] でループを回せば十分です。単調性から、端2つを比較するだけでもOKです。

ColorfulStrings (Div 2 500 / Div 1 250)

同じ数字は二度使えない・ n <= 8 にしか解がないので全探索で十分間に合います。効率が良いのはDFSですが、next_permutationでも大丈夫です。偶然生まれた n = 1 というコーナーケースに注意しましょう。

ColorfulMazeTwo (Div 2 1000)

途中でダメージを受けたから方針を変える、ということができないので、踏むと決めた色がすべて安全である場合だけ考えることになります。(踏んだ色, 位置) の 2^7 * 50^2 通りの状態に対してBFSなどを行ってもいいし、あるいは色の集合 2^7 通りに対してそれらを自由に踏むとしてゴールできるか判定して、ゴールできるものに対して踏む色が安全である確率の最大値をとってもいいです。

ColorfulDecoration (Div 1 550)

答えについて二分探索、可能かの判定は2-SATそのままです。Floyd-Warshallで実装するのが最も楽だと思います。TopCoderでは2-SATの問題が全然ないみたいなので難易度予想ができない、ということで550になったのですが正答率はMediumとして妥当なところに落ちついた感じです。

ColorfulMaze (Div 1 1000)

(踏んで危険だった色(高々1つ), 踏んで安全だった色, 位置) の 8 * 2^7 * 50^2 通りの状態に対してそこからゴールできる確率をDPします。ここでDPの依存関係にサイクルが存在しますが、それらのDPの値はすべて同じなのでDFSをする、Union-Findで頂点を繋げる、などの方法で解消することができます。

Result

Div 1 は550と1000の2完が2人、3完は惜しくも出ませんでした。
Div 2 は1位の人がすごすぎる、に尽きます。