〜 -1日目

前日に yukicoder があり、それに出ていたらリハーサルをやるのを忘れた...

リハーサルはちゃんとやりましょう！

当日（開始前）

僕の所属する研究室に集まって参加。

他の早稲田のチームもいくつか（MSB, give us, STT) 大学に来て参加する予定っぽかったので普通に楽しみにしていた。

m_tsubasa さんが研究室に遊びに来たので、今度発売されるモンハンの新作の話をしたりした。モンハンの新作を買わせて闇討ちしようとしてきたので危なかった。

他にもコーチの hatty さんがアルフォートをくださったのでありがたく頂いたりしていた。

僕が A、suta が B、ikefumy君が C を担当することになっていた。

先程も述べた通りリハーサルをやり忘れているので、不安になりながらスタート・・・

A を読み、「面倒だし O(N²) で実装するか...」と言いながら実装したらセグフォで動かず、よく見たら入力を受け取っていなかった...

直してもう一度サンプルを試そうとするとまた動かない。よく見たら「./a.out」ではなく「./a.cpp」を実行していて流石に笑ってしまった。

実行するとサンプルが合った。A を AC

B と C の状況を聞いてみると、なんと B が難しいとのことだった。

suta から概要を聞くと「それ桁DPじゃね？」という気持ちにしかならなかったのでそれを伝えると、

suta「え、そうじゃん　書きます」

あんまり詰めてないけどまぁそうだよね、てか今回は厳密には桁DPとはちょっと違うか、まぁいいや、C 大丈夫そうか聞いて D読もうかn...

suta「B 通った」

早すぎる...　この時 1桁順位だったと思う

C は適当にmapで実装を頑張るだけっぽかったので ikefumy君がそのまま実装し、 suta と D に取り組むことにする。

D をしばらく考えたり E を読んだりしているうちに C が通る。ちょっと実装がつらそうだった

E の概要を ikefumy君に伝えて D を再度考える。

ここで suta に「ある点が次の頂点にたどり着くまでの時刻でイベントソートして、その区間を三分探索すれば良いんじゃないか」と言われ、完全に正しそう（未証明）だなと思う。

三分探索に苦手意識があるので書いてもらうことに（これは僕が書くべきだったかも...）

E は数学で、かなり苦手意識があったが suta が D を実装していてやることがないので E の考察に混ぜてもらうことに。ちなみに MSB が爆速で E を通していて（FAだったらしい）かなり焦らされた...

しかしほとんど役には立てず、研究室に置いてある蟻本を持ってくるぐらいしか役には立てなかった。

結局 ikefumy君が1人で考察を終え、実装を始めた。僕は実装で苦しむ suta のデバッグを手伝うことに。

しばらくすると D のサンプルが合う。同じタイミングで ikefumy 君もサンプルがあったらしい。

同時にデータセットを実行し提出すると 1つめのデータセットがどちらも通る。無事もう1つも通り、盛り上がる。

ここまでの順位はいい感じで、コンテスト時間は後1hぐらい残っており、最後 F, G どちらに取り組むかという感じになっていた。FとGを手分けして読み全員で概要を把握した。

F は最小費用流で辺を O(MK) 本張れば確実に解けるが、終了までに実行が終わるとは思えないし、他の方法もわからない。

G は問題の見た目が Ears(耳DPの名前の元ネタ) に似ており、こちらの方がかなり希望があるように見えたのでGと心中することにした。

G は実際ほとんど考察が Ears に似ていて、それをベースに考えると i -> i+1 を何回通るかというのを左から決めたときにどのようなものがvalidになるかというのを考察する必要がある。

実際、i -> i+1 と i+1 -> i+2 の通る回数の差を d とすると、

という条件になり、逆にこれを満たすような順列が存在するので左からdp出来る。

しかしこの問題は復元が必要なので更に考察が必要。

ここで ikefumy君が「折り返せるならその時点で貪欲に折り返してもよい」という考察をしていて実装していたが、時間切れ（結局この方針で正しかったらしい）

16位 (selected 14位) でこの成績が取れればアジア進出ですが、去年は模擬国の成績はよかったものの本番で大失敗してしまったので油断しないようにしたいです。upsolveしっかりやります（まだ手をつけられていない...）