srm425

調子に乗ってる時だけ更新するsrm日記。

div1:250

深さ14で枝が4本伸びると2億、うーん。。。もしかしてNESWの列だけ見て簡単にsimple性を判定する方法があるのか？と悩んで遅れる。ちょっと考えてバック出来ないんだから枝の数は3本以下になって400万余裕じゃん〜という事になり普通にdfsを書いた。
passed system test 201.75

div1:500

うおーまた探索！しかもボードゲーム！！とテンションが上がる(ポーンだけのチェスとかの問題が好きです)。25C5を計算して状態数は5万だし余裕じゃん、そんで5*5=25で見え見えのintエンコードですね。bfsbfs〜でも盤面をintで持ってると連結チェックでアクセサかかなきゃいけないし嫌だ〜と思ってset >でopen nodeを管理しようとしたらやたら時間がかかったのでsetにしたら2倍くらい速くなった。まだ遅いけど、

o...o

.....

..o..

.....

o...o

が0.9secで終わったからまぁなんとかなるだろ、450とかで提出してる赤い人たちが手の込んだ事してるはず無いし、と思って提出。
challenge phaseで盤面を全部列挙するのにnext_permutationを使ってるのを見てなるほど〜と思った。
passed system test 417.14

div1:1000

終わった後のchatでPetrが「解法はググった」って言ってて戦慄を覚える。
compiled

div1全体で33位になって200強レーティングが上がった。喜びを通り越して若干引くな。。。とりあえず黄色になる目標は達成しました:)