FCCPC

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

ICPC国内予選2014

programming ICPC

記録: hadrori

2014/07/11にICPCの国内予選がありました.
僕達(hadrori, ponyo, stqn)はFCCPC_Aliceとして参加していました.
5完して10位だったのでたぶん予選は通過しているでしょう.
final standingsはここで見られると思います.

練習フェーズ

J問題でで提出ファイル間違えた時のペナルティがあるかなどの確認をした.
Mを去年と同じコードでやったら通ったのであとは適当に埋めた. 1位でした.
またライブラリを印刷してくるのを忘れたのでラボに行って印刷してきた.

間の暇な時間

暇でした.
暇なので他のチームのところに遊びに行ったりしていました.

本番

時間はちょー適当です. 詳しいペナルティとか出ることがあれば更新します.

戦略: ペナルティ勝負になるのは目に見えているので最初5問を爆速で通す. 僕は実装クソ遅いし, 他2人が爆速なので実装しない.

問題: http://icpcsec.storage.googleapis.com/icpc2014-domestic-live/icpc2014/contest/all_ja.html

0分

All Problemsから3部印刷. Aはそのまま解きはじめる.
残り2人はBを読む.

5分

Aが詰まっているように見えたので題意を聞く.
入力から消費税適用前の値を出すのは闇が深そうだったので, 適用前を1から全部試すことを提案する.

11分 A AC

方針を変えたらすぐ出来たので提出. AC(stqn)
Cの題意を伝えておく(やるだけっぽい)
Bの実装を開始する(僕は横からコーディングミスっていたら指摘する人).
これでバグって詰まるというのをかなり回避できる.

19分 B AC

特にバグらずAC(ponyo)

24分 C AC

気づいたらAC(stqn)していた.
Twitterによるとこの時点で2位だったらしい
Dは制約からビットで全部試せばよさそうなので実装開始.
Eはまだまとまっていない

44分 D AC

はじめサンプルが合わず慌てていたが, 冷静にみると配列の添字ミスっている.
そこらへんを修正すると直ったので提出. AC(ponyo)
standingsをみると2位.
きごうだらけのチームが既に6完していてやばい.
Eは木DPすればよさそうなので実装開始

55分ぐらい

サンプルが合わない.
手では解けているので実装がおかしいはず.
FGの方針が全然立たないので全員でデバグ.

65分ぐらい

基本的なミスがあったのでそれを修正.
後他にも修正していたがよくわからない.

72分 E AC

EがAC(stqn).
standingsを見ると2位.
あと1問はなんとかして通したい
FとGのどちらを解くか問題.
0peraが爆速で6完していたのでFは気づいたら一瞬なのかなあとか話す.

90分ぐらい

Fは辞書順のセオリー通りENSWの順に見て可能かどうか判定できればよさそうなので, 判定部分だけ残して実装を開始する.

100分ぐらい

まじで何も思いつかないので小さいケースを全探索して実験.
何も見えない.

120分ぐらい

Gは円が鎖状にループするとき中心をつないで多角形つくれば楽そう.
円の内部に同じようなループあったらどうするの？と棄却される
あとで考えたら3つ重なってるじゃんってなって, そこで円盤が重なるのか輪っかが重なるのかという議論になる.
伝言ゲームで情報が途中で失われていたっぽい.

150分ぐらい

Fの判定はフローでは？と一瞬思って提案するが計算量やばそうな気がして却下.
あとで考えたら頂点数が超少ないしそこまで重くないよなあとなって後悔.
結果論だが, もっと詰めるべきだった
他のチームが続々と6完していて焦りまくる.

170分ぐらい

結局まともな方針が立たない.
9位と10位が東工大で10位以内に3チーム, 東大が2チームだったのでこのままいってくれ.
しかし慶応が6完して抜かれてみんな仲良く2チーム以内になった.

180分 終了

とこはるさんがF通していたので解法を聞いて唖然とする(こっちでも出ていたので).

終了後

味庵でお疲れ様会.
国内予選の解法談義やTMPCクソ談義に花を咲かせた.
アジア地区の海外はどこ行こうかなあ
タイが有力候補だったのにクーデターとかやばい.
来年のWFがモロッコになる前はタイだったらしいが治安やばくて変更になったらしい.

反省

今回, 去年の国内予選, 会津大会, 台湾大会すべてであと1問解かなければいけない状況だったのに解けてないのはどうなんだろう.
伝言ゲームはしない.
妥当っぽい解法にFもGもたどり着いてるのにスルーしてしまった.
迷走しているときは3人独立で考えたほうが良さそう.

感想

超絶優良セットだったと思う.
A, B, Cは誰でも解けるが上位の人でも方針次第では詰まっていたように見える.
EはICPCっぽくないなあと思ったけどこういうのガンガン出して欲しい
F, Gは人類にも解けるが, 簡単には方針が立てられない良問っぽい
WF行くにはbugrepをなんとかして倒さなければならないので反省から練習方法を見なおしていきたいです