ICPC 2016 国内予選 - ヘクトのメモ

去年と同じくチームnocowとして今年も参加しました．(4回目のICPC国内予選)
ACM-ICPC 2016 国内予選

チームメンバー
@osrehun
@icchyr
@xthexworldx

結果は5完13位でした．今年は学内で1位を取ったし，アジア地区に行けます!
あと，学内の国内予選の最高順位を更新したと思う．

以下詳細なタイムスケジュールと感想

使用した競技環境は次のとおりです　
Ubuntu 14.04
GCC 4.8.4

0:00
まず，全問題を印刷してもらう．icchyrが環境構築を行いながら，自分がA問題を読む．xthexworldxにはB問題を任せる．

0:03
icchyrがスクリプトを書き終えたところで，A問題のコードが頭に浮かんだのでicchyrにコードを伝える．

0:07
特にバグもないので，そのまま提出する． A AC
この段階でB問題の方針が浮かんだと聞いたので，コーダーをxthexworldxにバトンタッチ
2人で残り6問の問題文を読み進めていく．

自分がC問題を読む．
エラトステネスの篩を応用すれば解けそう．
最大値はどのくらいだ? 問題文に書いてあるぞ!
ということで，C問題の紙コーディングを行っておく．

icchyがD問題の概要を伝えてくれる．
2つの積み木を打ち飛ばしたためには，間の積み木を打ち飛ばしされていないとダメ．
区間DPで解けることに気づく．

0:19
このタイミングでB問題のコーディングが終わったらしい．
サンプルを試すが，合わない．文字を数値として出力していたみたい?
それを修正して提出する．

0:22
B AC
C問題の紙コーディングが終わっていたので，自分がコーダーに変わる．

0:25
C問題のコードを3分で書き終えて，チームメイトを呆然とさせていた気がする??
サンプルを走らせたら，問題なく通ったので，提出する．
データセットの実行時間が多少重かった．

0:27
C AC
この時点で3ACして7位くらいだった気がする?
D問題について話し合っていく．
区間DPをした後にもう一度DPすれば良さそう!
反例があるかを多少考えるが，なさそう!
自分が実装を始める．

0:40
サンプルが合わない
区間DPの初期化やDPの更新式をバグらせる．
サンプルが合ったので提出する．

0:49
D AC
1時間以内に4ACしていることにチームで動揺する．
次にE問題に取り掛かる．

自分が連結した立方体の関係はグラフで表せて，そのグラフは特殊なグラフであることに気づく．
icchyrが立方体の重なりで減る表面積の式を立ててくれる．
チーム全体でいろいろ話した結果，次数2以下のグラフなので，パスまたはサイクルしかありえないことに気づく．
コーディングをxthexworldxに任せる．

1:16
実装するもサンプルが合わない．
何かをバグらせているみたいだ．
構築したグラフを出力してもらう．
辺のコストの計算にミスが発覚．
また，dfsでサイクルの計算がミスっていることに気づく．
サンプルが通ったので，提出する．

1:38
E WA
どこがまずいのかを調べていく．
xthexworldxが，K=2のときにサイクルであると判定されいることに気づく．
修正して，間違った出力ファイルとdiffを取って，一致しないことを確認する．
再度提出する．

1:46
E AC
ここからは，自分がF問題の方針は立ったので実装を始める．
木を構築して，木の同型判定をすれば解けそう．
ただし，実装方法とアルゴリズムを詰めきれていないので，時間が取られる．

2:10
チームメイトがG問題を思いついたらしい．
というわけで，自分は紙コーディングに戻る．
xthexworldxがG問題の実装をする．

2:40
G問題を実装したけど，答えが全く合わない．
問題文を誤読したので，方針自体が間違っていたらしい．
F問題の実装に戻る．

2:50
実装できたけど，バグがあって通らない．
ここで，タイムアップ

3:00
感想
去年の反省点をちゃんと活かし切れたのが良かった．
osrehun.hatenadiary.jp

特に，E問題はチームプレイで+1ACできたのが，今年の特筆すべき点だと思います．
また，例年の傾向からA問題に最初から取り掛かっていないのはICPCのスコア計算方法では不利になるので，
環境構築は最小限に，A問題に取り組みました．
個人的には，ABCの早解きがICPCの爆速実装に十分生かされたなと思いました．(A問題とC問題)

今年の反省点
やっぱり，難しい問題を解き慣れていない場合には，解法の正当性が判定できていない．
最後の1時間は割と迷走していましたが，5ACした時点で迷走しても構わないと思っていました．
ただ，6ACしたいなら，この方針は悪かったかもしれない...

というわけで，アジア地区予選の練習をしていきましょう!

大学のサークルとしては，今年は去年と同じ3チーム参加となり，残りのチームも3完していました．
(チームの実力差は練習していれば，いつか埋められると個人的には思います．)
(後輩の育成もどうしましょ?)