読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

JAG夏合宿 2016 day3

夏合宿の3日目のコンテストの時のアレです.
この日は模擬予選も兼ねていて,LINE様に提供していただいた会場でコンテストを行いました.
色々オフィスがすごかった.(こなみかん)

まよバタ+紺青さん(@konjo_p)の即席チームで参加しました.
実は紺青さんとは去年の夏合宿でもチームを組んだ(splas_boomelangのとき)
この3人は全員TCのレートが黄色で,日頃競い合っている人とチームを組めたのは私にとって大きな勉強となりました.

コンテスト開始前

この日はマヨ子さんのPCでやることになる.
...と思ったのですがAtomsublimeなどのエディタが色々vim仕様になってるらしく,デフォルトに戻すためバタバタする.

vimvimょい.

コンテスト開始

順位表を見ながらできるだけ問題を開けていく方針.
というわけで英文の短いDを譲ってもらう.
問題文は理解したけど解法は分からない...
ので問題文の短いEを読む.
プロ達はA,Bを通していく.

A,B AC

プロプロ
とりあえずDの内容だけ伝えてEを考えることにする.
木の同じ高さの頂点同士のマージ回数ならO(N)になるから愚直にやっていけると勘違いしてコードを書き始める.

E TLE

はい戦犯
原因が分からないのでDをやってもらいながら考え込む.
マヨ子さんはCを凄く書きたくなさそうにしていた.

D AC

はいプロ
紺青さんの手が空いたのでEの解法を相談する.
O(N^2)になっていることを指摘され,悲しい気持ちになる.
ロリハ解を提案され,やり方を確認しながら実装することにする.

E AC

本当にすみませんでした.
マヨ子さんがCを本当に辛そうにしていたのでデバッグを手伝いつつFを考える.
Fがひらめきそうでひらめかなくて本当につらい.
Gをちらっと読むと動的凸包で解けることが分かったけどそんなものは持ってきていないので捨てる
(実は動的無しでも解ける自明な解法があったので捨てたのは本当にミス

C AC

はいプロ.
なんとかFを閃いたので時間少ないけど頑張って実装することにする.

最小値RMQが必要になり,持参したsparse tableを実装する.
ライブラリを確認しながら実装していると,明らかにライブラリの間違っている部分を見つける 悲しい

F WA

デバッグタイム
怪しいところを修正して終了20秒前にラストサブミットをする

F WA

つらい.
落ちたケースを見てみると,sample3だけ落ちている.発狂した.

というわけでABCDEの5完で13位でした.
宿に帰ってからFをデバッグすると,RMQの取得区間が1間違っていただけなので本当に悲しい.

初めてのローリングハッシュなど,学ぶことの多いコンテストでした.

夏合宿は3日間とも効率化のため進捗表を上のように作っていたのですが,この日の私の仕事して無さがひどい