‌‌

ICPC の国内予選に参加しました。

メンバー

noshi91 昨年に引き続きです
Hemimor 新しく入ってもらいました
potato167 これ書いてる人　唯一の traP メンバー

m の要素が消えなかったのでチーム名も継続です

予選まで

個の力で押せるだろうなというのもあってチーム練をしませんでした。

模擬はやる予定でしたが、Hemimor さんが他の用事があったため不参加、noshi さんが遅刻したため、特にムーブを考えたり試すこともしませんでした。

当日

14時ごろに会場について、他の東工大チームに話したりしてました。
また、Hemimor さんとは初めましてだったので、色々話してました。

ポスターがもらえたのでもらったり、暇すぎたのでチームの札作ったりもしました。

コーチの方と「どれくらいで問題文届きますか？」「10分くらいですかね〜」みたいなことを話していると 16:29 になったので慌てて話をやめ、開始を待つ。

コンテスト

A

自分がパソコンの席に座り A を見る。解けたので問題文を B にスクロールさせてコードを書く。通す(4:43)

B,C,D

B 問題を noshi さんが書いてる間に問題文を C にする。C を Hemimor さんに考えてもらってる間に自分は D を読んで考察をする。

noshi さんに B を通してもらった段階(14:34)で、 C の考察が詰まってて、自分の D の考察は終わっていたので、Hemimor さんには E を考えてもらい、noshi さんに C を考えてもらうことにして、自分は D の実装を行うことにする。

D は答えが $7$ 以下になることから全探索で、場合の数が $O(n^7)$ だが、ちゃんと被りを省けば定数倍で $\frac{1}{(7!{)}^2}$ くらいつくだろと考えて実装した。(本当は $6$ 個以下の分割しか考えなくていいので遅いコードを書いてしまった。)

ぼちぼち待って出力が $7$ 以下しかないことを確認して提出。FA でした。(24:40)

noshi さんの C の考察が終わっていたので C の実装をしてもらい、自分は F を見たけどわからなかったので G を見る。

他のチームが C のペナを出していたので、C の judge を書くことを提案したけど noshi さんが必要ないと判断する。僕は心配だったため noshi さんと2人でサンプルの出力を目視で確認したところ間違っていたので C のコードをプリントし、デバッグしてもらうことにして E の実装を Hemimor さんにお願いする。

が、僕の確認不足で、実は E の考察が完了していなかったので、 noshi さんが C を普通にデバッグする。程なくして通る。(37:31)

E,G

Hemimor さんに E の実装を軽くしてもらってる間に、 G の考察が終わったので G を自分が実装する。

G は少し問題文がきつかったが、ちゃんと式変形すると2人がそれぞれとったサイコロの出目の和の差と今まで何個持ったかと何個目まで見たかの情報だけ持てばいいことがわかり、どっちが何個とってるかや誰がどのサイコロを今まで選んだかなどの情報を持つ必要が一切ないこともわかる。

ぺぺペーと実装してサンプルが通ったので通すと wrong answer (59:00 くらい？)コードをコピーしてデバッグする。

自分が G を実装している間に、2人で話し合って E のいい別の解法が見つかったぽいのでそれを Hemimor さんに実装してもらい、その間、 G の考察を noshi さんに説明して、正当性を確認してもらう。

確認してもらってる間に自分がコードのバグに気づく。遷移が足りてなかった。

E が終わりそうだったのと、 noshi さんのチェックが終わっていなかったので、気づいた後も間違っている部分が他にないかを確認する。

E の実装がバグってしまったのと、G の考察の noshi さんの確認も終わったのでキーボードをもらい、実装して出力に違いがあることを確認して通す(1:15:55)。だいぶグダってしまったが、順番が後ろの問題なのでこれもFAでした。

Hemimor さんに E の実装を続けてもらってる間に noshi さんから F の解法を教えてもらう。

凸包のライブラリの確認をしている間に E のデバッグが終わって通る(1:26:46)。 この時点ではまだ1位でした。

F,H

F の実装を noshi さんにしてもらってる間に、 Hemimor さんと H について考える。

色々案は出しあったものの、特に解法に辿り着きそうなものが思いつかない。 noshi さんの実装が難航していたので、 Hemimor さんが助言などをして通す(2:03:19)。だいぶ前に Speed Star が 7 完していたのでペナの差で 2 位。

H は定式化すると LP の形になるのでこれを解くアルゴリズムが欲しい。 noshi さんが最小費用流で解ける形にならないか考えるが、難しかったので simplex 法で解くことにする。

実装がしんどいが何とか終了 10　分前くらいに終わりサンプルがあったので実行するが出力が全く終わらず、そのまま時間切れ。順位は変わらず 2 位で終了。

コンテスト後

チーム練どうするか見たいな話をしてました。

教室を出た後、 traP のメンバーでカレー屋さんに行きました。

感想

自分の G のペナがなければ優勝できてたと思います。個人的にはかなり悔しいです。

まあでも yokohama にいけるので良しとします。僕的には同時コーディング禁止ルールは少し事故っただけでも順位が大きく下がるルールだと感じているので、かなり強いチームだと思うけど落ちる時は落ちるからなぁとか思ってました。他の東工大チームが強いと感じたり、体調が悪化したり、少しナイーブになってしまったためか、今週の月曜は icpc みたいなコンテストに落ちる夢を見てました。

host 校なのもあって、東工大からはおそらく 4 チームが yokohama にいけるっぽいのでそれは嬉しい限りです。

8,9 月はたくさん競プロのイベントがありますね。yokohama や去年の分の WF に向けて頑張ります。