読者です 読者をやめる 読者になる 読者になる

ヘクトのメモ

なんとなくいろいろ書いていくと思います.

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完していました.
(チームの実力差は練習していれば,いつか埋められると個人的には思います.)
(後輩の育成もどうしましょ?)