結果
47 + 100 + 100 = 247 点 Official Rank 2 位タイ（Gold）
めちゃくちゃ嬉しい！
やったこと
春合宿前に比べると精進量は落ちていた。 何度か外国 OI の 5 時間バチャをやったり、APIO の 2014 年以降の過去問を全て埋めたりした。
競技の流れ
0:00 ~ 0:10
問題文を印刷し、配布ファイルをダウンロード。全問に目を通す。
0:10 ~ 0:50
「各問について <30 分考察して難易度を見極め、どの小課題まで取れそうか考える」という立ち回りをすることは元から決めていた。
第一問 Hexagonal Territory
見るからにやばそうな問題。JOI 難易度 11 の Territory をめちゃくちゃ進化させたみたいな問題内容だったので、これは難易度 12+ だろうと目処をつけた。
15 分ほど考えたが、 すら解けそうで解けない。
第二問 Rainforest Jumps
Hexagon よりはずっと人間的な見た目をしているが、20 分ほど考えても愚直以外の方法が思い浮かばない。どうせダブリングだろうとは思ったが各頂点から辺が二本あるのがきつい。
第三問 Road Closures
見てすぐ「木の問題じゃん！これは解きたいな…」と思った。 JOI 難易度 12 の Designated Cities という問題に若干似ていて、貪欲が効くのではないか？と考えたがダメ。
0:50 ~ 2:30
今年の問題は難しいと思い、少し焦る。 一時間経って 0 点はまずいと考え、とりあえず Hexagon の 9 点と Jumps の 4 点を取っておく。 しばらく Jumps と Road を往復したのち、Jumps を頑張って詰めようという選択に至る。
何とかしてダブリングが使える形に落とし込みたい。経験上、このような問題は貪欲によって戦略を絞ると単純な形になって解けることが多いと感じていたので、貪欲を考える。
30 分間くらい何も思い付かず焦ったが、 の小課題を考えていると、「ゴールの高さを超えない間は、左右のうち高い方に登ればよい」ということに気づく。この時点で「この問題は解けるな」という謎の安心感を覚えた。
だけを解いても点数的にそこまで美味しくないので、
の制約がない場合も解いておきたい。少し考えるとスタート地点は一通りに絞れることが分かったが、それを高速に特定する方法が全然思い付かない。20 分ほど考えて、JOI の Scarecrows という問題で使ったテクニックを応用すれば解けることが分かった（実際はこのパートもダブリングできることがコンテスト後にわかった）。
ここまで来れば、満点はそう遠くなかった。とりあえず高速化していないコードで部分点が取れることを確認したのち、満点解法を実装した。 コンテスト時間半分が経過した時点でようやく緑色のランプが灯り、とても安心した。
2:30 ~ 3:50
Road を考察する。「各 について愚直に解けたらいいのに…」と考えていたら、次数
以上の頂点のみに注目すれば調和級数の計算量になることに気づいた。
自分の木 DP 力 / データ構造力にはそれなりに自信があったので、ここまで来たら解けるだろうと信じる。
実装したものを提出すると、TLE。
TL が 1.0s だったので、「 log 2 つだとダメなのか…」と、春合宿の二日目にひたすら TLE に苦しまされ、一問に粘着した結果ろくな点が取れなかったことを思い出した。
しかしよく見るとパスグラフすら通っていない。パスグラフなら log は 1 つになるはずである。
についてループを回していたのを、
に制限するとパスグラフの小課題が通った。
おかしいな…と思ってコードを見直すと、「次数
以上の頂点を格納する配列」が、随時 push_back していくつもりだったのに元々要素数
確保されていたことが分かった。
直すと AC になった。この時点で 209 点。これは勝ったろ！と思い勝利の舞を踊っていた（誇張）。
3:50 ~ 5:00
は取っておきたいな…と考える。六角形の移動は、傾きを変えて縦横斜めにすると考えやすいので、そのようにして考察する。
すると、
はピックの定理で解けることが分かった。実装すると 36 点になって喜んだ。
残り 20 分だったので愚直 BFS を書いてさらに 11 点を取り、コンテストが終了した。
もうこれ以上は取れない、という実感があった。大満足だった。
感想
悔いなく実力を出せたと思う。 この調子で IOI も頑張ります。
