読者です 読者をやめる 読者になる 読者になる

FCCPC

FCCPCについてお伝えするブログ

katsu_y practice 007

practice programming AOJ

記録: hadrori

問題セット

ACM-ICPC 2011 国内予選

2014/07/07 16:45 - 19:45 (3h)
コード
練習用コンテスト

練習前

問題は前回全く手を付けなかった2011年の国内予選
どうやら練習会も同じ問題らしい(奇遇だ).
計算機室で授業があったので終わるまで待機

練習

3分 A AC

A AC(stqn). Bの実装開始.
Cは全通り試せば良さそう.
Dはメモリがやばそうだけどcharでやれば……(国内予選なら気にする必要なし)
Eはメモ化再帰.

6分 B AC

B AC(ponyo).

24分 C AC

少しバグっていたが初期化忘れとか程度だったので修正して提出. AC(hadrori).

38分 D AC

特に問題なくAC(ponyo).

47分 E AC

サンプル試すと遅い. メモ化忘れていたので修正し提出. AC(stqn).
Gのドアを通るときにそのドアが壊れてた場合のそこからの距離をコストとする方針は結構よさそう.
入力部分だけ面倒なので詰めるのと平行して実装しておく.

80分ぐらい

Gのサンプルが合わない. デバグと平行して手でも解いてみる.

120分

Gがいまだにサンプルと合わない.
答えになっている経路と, 各コストをみてみる.
しばらくにらめっこしてるとそこまでの距離をちゃんと考慮しないとDijkstraがそもそも成り立たないことに気づく.

157分 G AC

各部屋に最大何ステップで来るかよくわからないので512まで見積もって修正して提出. AC(ponyo)
Fの実装を開始する. 間に合うのか……

180分

さすがに間に合わなかったが継続して実装を続ける.

190分

stqnがemacsの謎コマンドを使っていて, 端から見ると完全に魔法.
高度に発達したemacsコマンドは魔法と区別がつかない

200分ぐらい

サンプルが合わない. 式を見直しながらデバグ.

221分 F AC

サンプルが合ったので提出. AC(stqn) 結局1時間ちょいで番犬の実装できたことになるので十分

反省

今回は結構うまく回っていたように感じる.
やはり一度ハマると時間が一瞬で過ぎていくので, いかにハマらずに解けるかが今後の課題かな.
しかしアルゴリズムの正当性を時間内に示すのは難しいしどうしたものかなあ.