TopCoder SRM 470(Div 1)

TopCoder 参加記録

みょんみょん言ってるアルゴリズマーさんと同じ部屋だった。自分も含め日本人4人の部屋。

Result

75.00/ Unopened/ Unopened
Challenge 2ミス
25.00 483位
1590 -> 1546

うーんうーん、練習のモチベーションが上がらないよう……
テストステロンが足りない？（笑

Easy DoorsGame

問題

番号が0,1,..,NのN+1個の部屋の、部屋0にJohn,部屋NにGogoがいて、
隣り合う部屋はある色の扉によりつながっている。
部屋iとi+1をつなぐ扉の色を表す文字列（N文字からなる）と、ゴールの部屋の番号が与えられる。


このとき、次のようなゲームを行う。

  • 初期状態で扉は全て閉じられている。
  • 最初はJohnから交代にターンがまわる。
  • 順番のプレイヤーはまだ選ばれてない色のうち好きなものを指定し、その色の扉を全て開ける。
  • 両者が同時に動けるだけ動く。
  • ゴールの部屋に先に辿りついたプレイヤーが勝ちである。（ある色の扉を開けたときに両者が到達可能になるならば引き分け）

両者のとる戦略が以下のようであるとき、Xをゲームにかかるターン数としてJohnの勝ちならX,引き分けなら0,Gogoの勝ちなら-Xを返せ。

  • 自分がある色を選んで、相手がどのような選択をしても自分の勝ちになるならば、その色を選ぶ。そのような色が複数個あるならばゲームが終了するまでに選ばれる色の数を最小にするような色の選び方をする。ただし相手はゲームが終了するまで選ばれる色の数を最大にするように選択してくるものと考える。
  • それができない場合、自分がある色を選んで、相手がどのような色を選んでも引き分けにできるとき、その色を選ぶ。そのような色が複数ある場合どの色を選んでも良い。
  • それもできない場合、ゲームが終了するまでに選ばれる色の数が最大になるような色を選ぶ。相手はゲームが終了するまでに選ばれる色を最小にしてくると考える。
試行錯誤

えーと何だこれ……問題の把握がやたら大変だ。
がんばって読む。探索問題？ゲーム木っぽい感じの？ものっすごい苦手分野だorz


Standingsを見るがみんな提出が遅い。やっぱ難しいよねこれ？？
どう探索書くんだろう。全く方針が立たない。


(十数分思考)


えーと、もう一度整理。

  • 自分のターンですでに勝利状態ならX点、引き分け状態なら0点、敗北状態なら-X点

でしょ。

選ばれてない扉の色を全て選んでみて、

  • 相手の最高点がマイナスのがあったらその選び方を（のうち|X|が最小になるもの）
  • 相手の最高点が0のしかなかったらその選び方を
  • どれも失敗したら|X|がなるべく大きくなる選び方を

おお、これ再帰でいけるんじゃないだろうか。


実装する。方針を確認しながら慎重にがりがり。
やっぱり書いたことないタイプのはバグが出る。何とか直して終了15分前に送信。


さてどうしよう、Mediumは無理っぽい。Easy見直すか。
"ABCDEFGHIJKLMNOP", 8みたいなでっかいケースを適当にテストしてみる。


TLE！？
やばいやばいやばいやばい


色の選ばれ方は2^16*16=32768*16通りしかないはずだ！メモ化しよう。
メモ化。サンプルとおらない。何故！！！


2^16=65536じゃねーか馬鹿野郎。修正してSubmit. 75点……

Challenge

今75点だろ、ミスしてもほとんど順位変わらん。
上のでかいテストケースを適当にソース読まずに投げる。失敗。はい死ね。

System Test

Passed.
よかったー。サンプルが親切じゃなければ2^16=32768のバグでテスト落ちてるところだった。


んでも順位相変わらず酷いなあ。
どうモチベーション上げよう、ほんと。