TopCoder SRM588

writer でした。今回は Magical Girl がどこにも登場しませんでした

D2Easy - KeyDungeonDiv2

各ドアに対して独立に考えてよく、赤鍵と緑鍵だけで開けようとして、足りない分を白鍵で補って開けられればよいです。

D2Mid / D1Easy - GUMIAndSongsDiv[1|2]

どう考えたって tone の昇順/降順に歌うのがいちばんいいです
Div1 のほうは、tone の最小値 / 最大値をきめると使える曲が決まるのでソートして greedy。DP なんてどうやってやるの
Div2 では、曲をきめた後 (高々 2^15 = 32768 通り) tone の最小値 / 最大値を求めてもよいです。

D2Hard - GameInDarknessDiv2

dp[t][x][y]: Bob が t 回目の動きの直後 (x, y) にいられるか。
Alice が Bob のいるマスに行く場合と Bob が Alice のいるマスに行く場合の両方で Alice が勝つことに注意。

D1Mid - KeyDungeonDiv2

白い鍵はもらったらすぐに全部赤鍵、緑鍵のどちらか（すべて同じじゃなくてもいい）に変えます。
dp[開けたドア][赤くなった白い鍵の数] として DP
見たところ、dp[開けたドア] でがんばって DP しようとして failed してる人がたくさんいました。

D1Hard - GameInDarknessDiv1

Bob の勝利条件は、「Alice からの距離 - Bob からの距離 >= 2 なる頂点 P で、盤面が下の構造を部分木として含む P が存在する」ことです。

これが満たされない時 Alice が勝てます。
別に 900 や 1000 で出してもいいかなと思ったんですが admin が話し合った結果 1100 になったらしいです。
（りんごさんによると、「admin になって以来最難問」「人間に解けるものに見えない」らしい）

(証明)
Bob の勝利条件を満たしているときは、条件をみたす点を X として、Bob は X を目指します。Alice に追いつかれずに X に到達することができます。
(距離の条件は、「その点に着くまでに Bob は Alice に捕まらない」ということです)
ここで、簡単なプログラムにより Bob が X に着いて、Alice が 2 or 3 マス隣にいる状態でゲーム開始したら Bob は逃げ続けられることが示せます。
別に木がもう少し大きくても Bob は無視して逃げ続ければかまいません。

条件をみたさないときは Alice 必勝です。
最初 Alice は Bob を追いかけます。Bob がどっちにいるかわからなくなったら、葉までの距離が 1 or 2 のほうをまず片づけます。
1 のほうは何もしなくてよいです（Bob がそこに逃げてたとすると自爆する）
2 のほうは、その枝を 1 マスだけ進むと Bob は捕まります。その後すぐに戻れば、Bob が反対側に回りこむ危険はないので枝を減らせます。

Sample 3 みたいなものは少し例外で、この場合は一度適切な葉に Alice が行ってから改めて Bob を捕まえに行くとよいです。