AtCoder Regular Contest #012
初AtCoder。最近はCfもやってなかったので競技プログラミング自体久々です。
全体的に変わったことしようとして時間費やした感じが。
A - 週末
http://arc012.contest.atcoder.jp/submissions/70373
完全一致で検索するのは癪だった、というかnew[]{...}を書くのが面倒だったので、それぞれの頭二文字を並べた文字列から検索。木曜日を書き忘れてWAもらったのは悔しい。
この問題は後にWhitespace版も投げた。
http://d.hatena.ne.jp/unarist/20130210/wspace_in_atcoder
B - アキレスと亀
http://arc012.contest.atcoder.jp/submissions/70716
この手の問題、「(速度A-速度B)*t=t時間で開く/縮む距離」で解くことが多くて今回もそれを使ったのだけど、「L*(Vb/Va)^N」で解いてる人が多くてえっえっという。
加えて、ここまで実行時間気にする必要は全くなかった。
C - 五目並べチェッカー
- 白と黒が等しい＝白を置いた直後なので、黒5個or白9個（一手で作れる限界）でアウト
- 黒の方が一個多い＝黒を置いた直後なので、逆
- それ以外の数はアウト
という条件を見つけて、じゃあ端から順に走査して縦横斜めを一気に数えられるんじゃないのーと思っている間に時間切れ。
一回目->WA http://arc012.contest.atcoder.jp/submissions/71473
まさにこの通り。この解法だと×型の五目を検出するタイミングがばらばらで判断しにくい上に、一点で交わっているかどうかを判断するのが面倒。なので五目検出した時点で最後の一手チェックに切り替えるようにした。
二回目->AC http://arc012.contest.atcoder.jp/submissions/71596
交差してるかどうかも場合分けして走査を減らす予定だったけども、周囲8マスのカウントがすっきり実装できなかったのでここまでに。
ところでこれバグがありますね。正しい五目かの検証は石が途切れたときにやっているので、右下のマスにつながっている五目は検証されません。
................... ................... ...............x... ................... ....x.............. ................... ......x............ .......x........... ..........x........ ........x....x..... ................... ..............x.... .......x........... ...............x... ...............o.o. ...........x...o.o. ...............o.o. ............x..o.o. ..............ooooo
二箇所で交差しているので一手でこの状態にするのは不可能ですが、先のプログラムだとYESに・・・しーらない。
