ICPC2016国内予選参戦記

チームUSAで出場、AとBとCの三問といて61位でした。チーム名の由来はチームメンバー(うま,ゼレ(selee),あーちゃん)の三人の頭文字。

 

予選開始前

練習問題のJ,K,Lをあーちゃんが通してた。その後別チームのわにさんが「Mの解法思いついた」とか言い出して通してた。で、なんか僕に伝えてきたので僕も通しといた。自分で思いついた訳ではないが4完。

 

予選開始

作戦としては、僕とあーちゃんで速攻でAとBを通し、その間にCをゼレ氏に読んでもらう。で、AとBを通した頃にはゼレ氏がCの問題を把握していて、解法も思いついてたらいいなーって感じで。このチーム、考察力がかなり低めなので、D以降は解ける問題があれば解く的な感じでした。あと、一番コードを書くのがうまいあーちゃんが基本キーボードを触り、僕とゼレ氏は見て間違いを指摘するようなチーム編成です。そのため、使ったPCはゼレ氏のものだったが、.vimrcの設定などは全部あーちゃんのもの。

 

A

sortして差を見ていって最小値を選ぶだけ。なんか解法というよりコードをそのまま口で言ってた。それをあーちゃんに打ってもらってた。

 

B

投票する、sortする、残りの票が二位の人に入った場合、1位の人を抜けるかどうか判定、抜けなくなった時点で確定。そこそこスムーズに通せた。

 

C

愚直解を回した。ゼレ氏が問題読んでくれて把握まではしてくれていたので、問題本文をしっかり読んだのは予選終わってからだった。解法はいいアルゴリズムがぱっと思いつかなかったので、「とりあえず回そうか」的な。最初書いたものは毎回mをループの初期値にするというコードでめちゃくちゃ遅かったが、前回埋めた数字より小さいことはないので、その埋めた数字を初期値とするというコードにしたら結構早く終わって、AC。

 

D

解けず。奇数番目と偶数番目が同時に抜けていくので、二部マッチングっぽいなーって話をしていた。区間DPで解くのが正攻法だったっぽい?来年までに要復習。

 

E

解けず。模擬国内BのC問題で出た座圧+imosを三次元でやるのかなー、でもこれだとくっついた物体が2つ以上ある時どうやって分割すればいいのかな、わからんな、とか考えてた。

 

F

解けず。UnionFindでグループ作っていくのはいいけど、その後どーすりゃいいのかわからなかった。

 

G,H

一応目を通しはしたが、ぱっと思いつきそうではもちろんなかったのでパス。

 

 

以上です。大学内1位は取ったけど、それだけでした。来年頑張ります。