ICPC国内予選2014 参加記

ICPC国内予選に，TeraCoders(nisshy, dddai1206, kenya)というチームで参加しました．

以下はその参加記です．各問題のAC時間は，2つめのジャッジデータに対する出力の生成時刻．

コンテスト中の流れ

16:30 コンテスト開始

開始後はkenyaがテンプレートを書いている間に，

自分がA，dddai1206がBを読んで解法を考える．

テンプレートを打ち終わった後，まず自分がAを実装する．

しかし商品が1つだという訳の分からない読解ミスをしてしまい，

いきなり詰まってしまうがミスに気づいて修正する．

2つの商品の税抜き価格で全探索．誤差が怖いので整数演算のみで求める．

16:45 A AC

いきなり読解ミスをするし，先行き不安な立ち上がり．

Bは解法の確認だけしてdddai1206に実装をまかせ，CとDを読む．

どちらもICPCの典型問題じゃないし，Cは幾何でつらそう．

まずCの解法を考えるけど，あまり良い解法が思いつかない．

どうしようか考えている間に，Bの実装が終わったがバグっているらしい．

いくつかバグを指摘して，修正してもらうとサンプルが通ったので提出．

17:11 B AC

とりあえず，パッと思いついた解法でCを組んでいく．

全ての座標が整数値で与えられ絶対値も小さいので，

1*1の各マスに建物があるかを2次元配列で保持．

あとは建物がないabs(x) <= rであるマスについて，

そのマスに太陽が到達する時間を計算して最小値を取れば良さそう．

しかしここから泥沼に嵌っていく．

適当に書いてみてサンプルを実行してみるが全く合わない．

ソースコードを見ると，配列のオフセットや添字と座標の関係などおかしなところがたくさん．

1つずつ直していこうとするけど，頭がバグって何が正しいのかも分からなくなってくる．

そもそも太陽が到達する時間を求める計算式が合ってるかも，頭がバグって分からない．

プログラムもバグっているし，自分の頭もバグっている．

もうどうしようもないし，国内予選落ちかなとか悲しい気持ちになってくる．

そんな時にkenyaが今の解法にこだわるのをやめよう，

時間を0から進めていく解法にするのはどうかと提案してくれる．

確かにCは出力誤差の制約がゆるゆるなので，適当に小さい時間ずつ進めていく解法も出来そう．

今の解法をそのまま続けていても直せる気がしなかったので，そちらの解法に切り替える．

その後，いくつもバグを出すがなんとか修正してサンプルが通る．

ジャッジデータを落としてきて，実行するとめちゃくちゃ遅い．

ひとまずバックグラウンドで実行しておいて，Dの実装に移る．

Cで長らく詰まっている間に，dddai1206が文字列を複合していく解法を考えてくれていた．

それを聞きながら実装しようとするが，頭がバグっていて理解出来ず，

とりあえず入出力部分など自明な部分を実装してお茶を濁しながら考える．

そうこうしていると，Cの実行が終わる．

結局，実行時間はジャッジデータごとに7分くらいかかった．

18:25 C AC

Cが通りホッとして，少しずつ落ち着いてきたのでDの解法を理解する．

どの変換規則を使用したかを覚えておきながらDFSで探索して，複合文字列を全列挙．

サンプルが通って提出するもWA．

ソースコードを見返していくと，DFSの探索部分に不必要な遷移があったので削除．

サンプルが通り，ジャッジデータにはWAになった出力と異なる出力を吐いたのを確認して提出．

18:48 D AC (1 WA)

4完したが，最近の国内予選では4完で落ちてしまうチームもあり，

Cで嵌ったせいでペナルティが大きいので，5完しないと安心できないと思っていた．

kenyaがE問題を読んでいたので説明してもらう．

このE問題はパソコン甲子園で既出だったらしいが，自分は解いたことがなかった．

落ち着いて，1つずつ考察していく．

全ての辺は最終的に削除されるので，辺の削除のコストは常に全ての辺の重みの総和になる．

だから，移動のコストの最小化のみを考えれば良い．

辺は接続されている頂点にいるときに削除可能なので，葉に移動するメリットはない．

そのため次数2以上の全ての頂点を訪問する際の移動コストを最小化すれば良い．

始点と終点を決めると，そのパス上の辺は1回のみ通り，その他の辺は2回通る．

なのでパスの重みの和の最大値を求めればよく，つまり直径を求めれば良い．

直径はDFSなどでも求められるがn <= 800と小さいので，

実装が楽なワーシャルフロイドを用いる．

特に大きなバグも無く実装は完了．

19:18 E AC

残り10分でF,Gを解けるわけがないので終了．残り時間は順位表を眺めるなどしていた．

19:30 コンテスト終了

感想

結果は5完25位で，コンテスト中はボロボロだったけど

最終的に通過出来て良かったという感じ．

チームメイトに助けられた．

dddai1206はBの実装とDの解法を考えてくれて，

kenyaはミスの指摘やサンプルの図示をしたり，相談相手になって落ち着かせてくれた．

2人ともグッジョブだったし，それなりにチーム戦が出来たかなと思う．

ただ自分としては順調だったのはEだけで，Aの読解ミス，Cの頭のバグ，DのWAと反省点ばかり．

アジア地区予選までには，もっと精進します．