Hatena::Grouptopcoder

kohyatohの日記

 - 非数学系な人のTopCoder参加記です。

2011-01-13

SRM 493

| 03:05

ソース・成績(要ログイン)

好調回。朝だし。

300AC 27minサンプル弱すぎ
450AC 33min計算量が大事?
1000Unopened-


11:00 Start

Room 12. 赤い影のない、すごく平和な部屋。


11:05 Easy

ゲーム問題。

状態数が100万なので一瞬探索できるかと思ったけど、100万*100万ぐらいなので普通にムリ。

なにか使える性質があるんだろうなぁ...と思いつつしばらく考える。


...よく見たら、自分のターンで相手の前の手と同じところをひっくり返せば、無限ループに持ち込めるので、即死以外に負けはない。

つまり、先手が勝つのは先手の1手目で勝てるときのみ。後手が勝つのは先手が1手目をどうあがいても、後手の次の手で勝てるときのみ。

となれば2ターン調べるだけ。ただの実装問題。


...これ実装微妙に重くない?

偶奇判定とか、はみ出してないかのチェックとか、条件が多い。こういうの苦手。

とりあえず頑張って書いて出す。偶奇で場合分けしておいて同じ文が現れたり、みにくいコード。210点ぐらい。


とりあえず、450に行く前に見直し。

移動可能かの判定はあってるはず。Drawとかの判定は...間違ってるし!

「先手が1手目をどううっても後手の勝ちとなる」とすべきところを、「先手の1手目の候補の中に後手勝ちの手がある」と間違って実装してた。

直して再提出。140点ぐらい。ぐぅ...


サンプル通ったのは、後手勝ちのサンプルが全て「先手の手の候補が1つしかない」場合だったから。

こんなんはまってる人他にいるかなぁ...と思いつつも、撃墜ケースとしてメモ。


11:35 Medium

Easyで手間取ったので若干焦り目。しかし450にしては解いてる人が少なかったので、ある程度警戒しつつ開く。


なにこれ..DPで全状態を保存したら、50^7とか7^50とかになる。

最小幅を決めうちで調べるとか、なにかアドホックな解法があるのかなーと思ったが、すぐ反例がでるものばかり。


適当にメモに数字を並べて試したりしてみる。

...これ、1~7までしか数字がないなら、最小幅は最大で7じゃん。

ということは、過去6マスだけ覚えておけばいいので、dp[7^6]みたいな感じでいける。


実装。実はdp[50][7^6]であることをなぜか失念してて、途中で慌てて直す。

計算量が10^7クラスで大きいので、最大ケース(0を50個、7)でTLEしないか確認。1sだったので遅めだが問題なし。

提出。240点ぐらい。450にしては頑張ったほうか...?


Hardは開きませんでした。


Challenge

とりあえずEasyの自分の再提出ケースで落ちそうな人をさがす。

-> 二人もいた。ありがたく撃墜。

Easyを数学っぽく解いてる人が落ちそうな気がしたけど、わからないのでやめとく。

Mediumを貪欲でやってる人を見つけたけど、タイムアップ。


Result

AC/AC/Unopened 2 challenge successful

148.12 + 241.02 + 0 + 100.00 = 489.14 18位(部屋1位)

1843 -> 2012


初の2000超え。

しかしまあ浮き沈みが激しいなぁ。

今回はChallenge(というか部屋運)に助けられた感が大分強いので、次回はきっちりコーディングの速さで稼ぎたいです。


Review

450をあとでコードを眺めると50*(7^6)*7*6になってた。

いくら幅チェックのループが途中で打ち切られるといっても、よくこれで通ったなぁ。


->調べてみると、たしかに一番深いところで1億6千回ループを実行している。

ただ、そのループ内で比較演算子しか行なっていないため、コンパイラの最適化が盛大に効いて、定数倍で通っているらしい。

ちなみに最大ケースは手元で最適化なしだと2.8sec, -O2で0.6secでした。