prime's diary

そすうの日々を垂れ流しちゃうやつだよ

ICPC 国内予選 2014 参加記

競技プログラミング

ICPCの国内予選に出たことについての感想を書きます。

チームと結果

チーム名: Primasta

メンバー: @asi1024 @TakiTakiTakise @_primenumber

6問正答/全7問, ペナルティ: 23875

全体で5位、大学別4位、大学内1位

国内予選が始まるまで

京大から他にAlkachu,Colorful Jumbo Chickenという強いチームが出るので、ツイッターでは

みたいなことを言っていたが、模擬国内予選の結果を鑑みるにアジア地区予選に出られる望みは薄いなあという感じでいた。

特に前日深夜のTopcoder SRMで0完してしまい気分が最悪な感じな上に、ICPCが始まるまでに起きれるかが不安になる程度に生活習慣も崩れまくっていてダメダメっぽい感じ。

競技開始直前

チーム内で担当をどうするか決めた。私は模擬国内予選の時に他人の書いたコードのバグを見つけるのが上手いらしいことがわかったので主にデバッグ担当をすることに。

デバッグ担当は実装担当が実装してる後ろでバグってそうな場所を突っ込んだりする。ペアプログラミングの要領。

競技中

私が実装した問題のみソースコードを載せます。 asiさんが実装した問題のソースコードはhttp://asi1024.hatenablog.com/entry/2014/07/14/034221から見れます。

A問題

実装: @asi1024 デバッグ: @TakiTakiTakise

私は問題を読んでない。5分程度でAC。この間にB問題を読んでどういうふうにコードを書くか考えた。

B問題

実装: @_primenumber デバッグ: @TakiTakiTakise

制約が緩いので単純にシュミレートするだけだけどちょっとバグりやすかった。15分程度でAC。

C問題

実装: @asi1024 デバッグ: @_primenumber

シルエットの座標が整数しか取らないことを利用すると実装が簡単になることをasiさんが見抜いていたので早かった。10分程度でAC。

D問題

実装: @asi1024 デバッグ: @_primenumber

各文字について変換が高々一回しか起こらないので、候補となる文字列を全列挙できることをasiさんがすぐに見ぬいた。パフォーマンスを重視してmapではなくvectorを使うことにしたが、重複が起こりうることを忘れていてWAしてしまったので裏目に出た。17分程度でAC。

E問題

実装: @TakiTakiTakise デバッグ: @_primenumber

ほぼ同じ問題を解いたことがあったので、解法はすぐにわかった。 実装を楽にするために(辺の重みの3倍)-(葉についている辺の重みの2倍)-(葉を除いた木の直径)という求め方をした。DFSを2回して木の直径を求める方法を忘れていたので各頂点からDijkstraをした。実装をどうするか詰めている間にasiさんにDijkstraのライブラリを写してもらった。

23分程度でAC。それなりに上位にいたが、残り2時間弱あることを考えると十分に抜かされうるので、時間をかけてでも必ずどちらかは通そうという事を考えた。

G問題

実装: @asi1024 デバッグ: @_primenumber, @TakiTakiTakise

Fはサイコロのやばそうな問題に見えたので、まだわからんこともないGを考えた。幾何ライブラリにお世話になりながら、いろいろなバグに苦戦を強いられたが、1時間半弱かけてAC。この間にぼんやりとF問題の解法を思いつく。ACした瞬間のうれしさは半端無かった。ここでアジア地区予選に行けることを確信。

F問題

辞書順とか関係なく、与えられた6つの数を持つサイコロが作れるかがO(t)で判定できれば解けることに気づいたので、asiさんに言ったら作れるかの判定が割と簡単にできるとわかり、実装しようとしたがさすがに時間がなかった。

全体的な感想

今年の問題セットは考えれば実装がかなり楽になる問題が多かったように思う。実装が苦手な傾向のあるPrimastaにとって有利に働いた気がする。

うーん、でもこの結果はさすがにうまく行き過ぎに思えるなぁ。チーム戦略がうまくハマったのも大きそう。

今後について

JAGの夏合宿に参加したかったけど運転免許の教習とかぶってしまったので出れなくて悲しい。

それはともかく、精一杯World Finalに行けるように頑張りたいけど、数学にそろそろ本腰を入れないとやばいので困ってしまう。