ACM/ICPC 2010 アジア地区ジャカルタ予選チーム練習記

７月中に１回くらい５時間セットで練習しておこうという話になったので, チーム(僕, @slip0110先輩, @kioa314先輩)で練習してました.
チームRokkakuのメンバー(@epee_noir先輩)も合同で練習してました.

結果

Rokkakuさん : 0問(Aをひたすら考えていたようです)
.shiomoriさん : 6問(B,D,F,G,I,J)
2D : 4問(B, D, F, I)

B	D	F	I	総ペナルティ
154 / 1miss	96 / 0miss	276 / 2miss	130 / 0miss	716

本番

＜序盤１時間＞

kioa先輩が遅れてきたため, 最初１時間は２人で考える.
僕はA, slip先輩はBを考える. １時間たっても, 何も思い付かなかった（＾＾
kioa先輩が来てくれたので, 僕と一緒にAを考えた. でもやっぱりダメ.

＜次の１時間＞

kioa先輩がAはあきらめようと決断してくれたので, ２人で次の問題へ.
この間, slipさんがBの方針をある程度思い付いていたので, 実装. かなり長時間, この実装は続く.
　　(以降, .shiomoriさんの真似が続きます)
僕とkioa先輩が, Dを読解. ただのシミュレーションだ…. ペアプロで実装 & AC.
次は, I問題へ. kioa先輩と読解. 明らかにGreedyで実装すれば通りそうだとkioa先輩が言ってくれたので, ペアプロ & AC.

＜次の30分間＞

ここで, kioa先輩は, slip先輩のBのサポートにまわることに.
僕は, F問題の読解. ワーシャルフロイドは明らかに間に合わないことはわかる. 再帰や幅優先でやっても, 間に合わなそう.
ここは, 最近勉強しておいた, 強連結成分分解の出番だと思いつく.
この時点で, slip先輩とkioa先輩がBを通すことに成功.

＜地獄の2時間前半戦＞

slip先輩は, 他の問題の読解・解法にまわって, 僕とkioa先輩がFを考える.
強連結成分分解を使う方針に, kioa先輩も納得. がんばって, 強連結成分分解後のDAGを作りあげる. DAGができさえすれば, あとはもうやるだけだったので, 実装.
サンプルが正解したから, 提出.
ＷＡ！？
グラフが連結じゃないときのことを考えてなかった・・・. 「これのせいで大幅にコードを書き変えなきゃいけないじゃないか！」と, ちょっとパニック状態になった. しかし, 考えてみれば, 全てのノードにエッジがつながる新しいノードをひとつ作ってやればいいだけだった.
修正して提出.
ＷＡ！？！？

＜地獄の2時間後半戦＞

コードは今度こそ完璧なはずなのに, なぜかWA. なぜWA.
いろいろテストケースを作ったり, 何度もコードを見直し. これでもう１時間悩まされることになった.
↓
結論：ある処理を1行下の行に下げてやるだけで通った
処理を書くべき位置が少しずれていただけだった. これで, まさかの一時間も悩まされました. とんでもなくひどいです.

＜ラスト30分＞

Gをみんなで考えながら終了.
僕は, DPで解けないかなあ〜, とか考えてましたが, そんなの使わなくてもいいのかな.

ヒトコト

Fの非常につまらないミスを直すために, こんなに時間をかけなければ, もう一問くらい解けていたので, 非常に残念です.
これから, テスト期間に入るので, 7月の練習はこれで終了です.
夏休みに入ったら, 戦略を考えたり, 問題解きまくったり, 猛特訓していきたいと思います.
と, その前にテストがんばってきます. では, 2週間ほどブログ休みます.

結果

本番