katsu_y practice 007
記録: hadrori
問題セット
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時間ちょいで番犬の実装できたことになるので十分
反省
今回は結構うまく回っていたように感じる.
やはり一度ハマると時間が一瞬で過ぎていくので, いかにハマらずに解けるかが今後の課題かな.
しかしアルゴリズムの正当性を時間内に示すのは難しいしどうしたものかなあ.