FCCPC

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

ACM-ICPC2013 アジア地区予選会津大会参加記

ICPC 2013 会津大会に参加してきました. FCCPC_alphaというチームでした. 結果は全体8位でした.

凍結される前のランキングがもうなくなっていたので時間はアバウト. ACした大体の時間に対して, その時間までのことを書きます.

~0:40 A, B Accepted

AはDP, Bはシミュレーション. Bは蟻の反転を一度に2回やっていてバグっていた.

~1:30 E Accepted

これを通す前にCを投げているがWA なにが間違っているのか全くわからず, デバッグが苦行. EはDijkstra書くだけらしく, デバッグしている間にAC.

~2:40 C, D Accepted

時間はおさけーさんの参加記から適当に推測 Cは結局直せず, 別の実装(どちらも座圧だが, エリアの分け方が違う)でAC. もともとは四角形に覆われた部分をビットでマスクして色を塗り, つながっていてかつ同じ色の数をカウントしていたが, 修正後は四角形の枠を書いて, 塗られていないエリアを塗っていくようにしていた.

ここらへんでstandingsをみて, binding.pryに勝っていたけれど, 絶対にこの5問と+2問ぐらいは通してくるから安心はできない.

~3:58 H Accepted

G, Iを解こうとしていたが, 他のチームがHを結構通していたのでちゃんと見てみると簡単そう. 幾何ライブラリを写すが謎の文字列があり混乱. ライブラリ部分以外はすんなり通ってAC.

~5:00 Iに投げまくる

HがACしたあと, FGIのどれかに絞ることに. どれも考えていたがIが一番何とかなりそうということでIを選択. が, 結局方針が立たずダメ元でゴリ押しコードを投げることに. TLEだったので解の精度を下げて定数倍高速化を試みる. 途中で枝刈りできそうな部分が見つかり, 刈る. ここから精度の微調整をWAとTLEをみながらつづけ, 結局そのまま終了. 終了10秒前ぐらいまで投げていた気がする.

終了後, 話しているとFの制約が正確に伝わっていなかったことが判明. 次回以降は制約リストを作ることを決める. またMi_SawaさんにCの話をしたら, 元のやつだと四角形がつながって真ん中の部分が四角形内部ではないけど外と区切られている場合というのがカウントされないのではと指摘をうけた. 確かによくあるケースでなぜ気づけなかったのだろうか……

まとめ

Cの実装総取っ替えはナイス判断だった. しかしあのケースは気づけるケースなのでそうなる前に修正できればよかった. 問題文はちゃんと読もうというのはn回目なので, 制約はリストを作るというルールを設けた. Hを何故か後回しにしていたのはもったいない. 幾何っぽい→実装重そう→後回し という思考は問題をちゃんと考察してからでも遅くない. ライブラリの整備をちゃんとする.(台湾に向けて今できることは完了済み)

binding.pryがスロットを取るのは確定的なので今年のWFの可能性は消えました.(海外含めて両チームがスロットを取った場合は会津の結果を優先するという取り決めのため) しかし, 反省すべき点を踏まえても納得できる結果ではあったのでよかったです. 今週の台湾では反省をさっそく活かすチャンスなのでいろいろ意識しながらやりたいです.

来年は僕ももーっと強くなってWFのスロット取りにいきます. たぶんチームメイトはもっともーーっと強くなってきます.