TopCoder SRM 511 Div1 - simezi

180.42 / 349.82 / Opened
0チャレンジ

80位
1730 -> 1859

全て背の異なるうさぎと猫がいる。
それぞれの動物に対して自分と同じ動物で、自分より背の高い動物は何匹いる？という質問をした。

全ての動物が正直に質問に答えたとして、それぞれの動物がうさぎか猫か決める場合の数を求めよ。

質問の答えは、動物ごとに集めると、0,1,2（ここまで猫）,0,1,2,3（ここまでうさぎ）みたいに、0,1,2,...,n-1と0,1,2,...,m-1みたいになっているはず。

そのときの場合の数は、2^min(n,m)+1かな？
そうでない場合は0.
サンプル通った。よーく見直しする。
オーバーフローとかも大丈夫。送信。

送信後テスト。
あれ、0,0のケースで4が返ってくる？明らかにおかしいこれ。

nとmが異なる場合は2^min(n,m)+1で、そうでない場合は2^nだー。
訂正してresubmit...orz

メモリとカードを使ったゲームをする。
二人のプレイヤーが交互に、

お互いが最善を尽くすとき、どちらのプレイヤーが勝つか求めよ。

ゲームきた。カード50枚だとメモ化探索とか無理っぽい。。。

あれ、でもカードの数字のビットのうち既に立ったビットを全部無効にしていったら、状態数ってかなり減るんじゃないの？

書いてみた。ランダムケースでテスト。
やっぱ終わらないか……と思ったらカードをソートするの忘れてた。
ソートしたら……余裕で終わる。でもこれ嘘解法くせえー！

一応提出しておく。
その後ランダムケース30個くらいテスト。全部0.5秒以下で終わるなあ。
ひょっとしたら通るんじゃないかこれ。

1次元で両端がつながったライフゲームがある。
初期盤面にいくつか?のマスがある。T秒後にK個以上生きているマスがあるような初期状態は何通りあるか求めよ。

あけただけ

自分と同じように500をメモ化再帰で無理矢理やってる人がいないか探す。
……一人もいない。みんなDP解法だ。。。

250を色々見る。既に２〜３個落ちてる。
まだあやしそうなのあるんだけど、どれもスパゲッティすぎて自信ない。

という訳で0チャレンジ。自分の500が2回防衛していてふいた。

なんと両方通った！500何でこれで通るんだ。