結果
100+100+26=226pt
日本5th(unique)
全体43rdタイ
Silver Medal
問題
A Walls: 複雑さを追い求めただけの問題。mod × indexの平面に図示すると貪欲法になる。難易度10
B Cities: グラフの性質の問題。連結成分に関する条件になって、永続ufやHLD+parallel binary search（後者を使った）で解ける。難易度11
C Tour: 木の性質のインタラクティヴ。直径を取り続ける。難易度11
経過
時間は分の一の位を四捨五入していることがある
10:02-(0+0+0=0)
コンテスト開始
Aを読む。条件が複雑で、それを整理する。
読解verifyのため小課題1,2の12点を取る。
10:40-(12+0+0=12)
眺めていると解けそうだということがわかる。
複雑な条件の扱いに時間がかかる。
Dijkstraを書くと、最後の小課題がTLEして、63点を取る。
11:30-(63+0+0=63)
よく考えるとDijkstraは必要なくて、貪欲法で解けることがわかる。
実装して100点を取る。
11:40-(100+0+0=100)
Bを読む。これも条件が面倒で、それを整理する。
読解verifyのため小課題1の6点を取る。
12:00-(100+6+0=106)
小課題2を考える。見落としで時間を使う。追加で7点を得る。
12:20-(100+13+0=113)
愚直の小課題3,4を書く。50点を取る。
12:40-(100+50+0=150)
満点に対するクエリの平方分割解を思いつく。TLEする可能性があり、実装も重いので、別解を思いつく可能性も考えてCに移る。
12:50-(100+50+0=150)
Cを読む。直径を繰り返し取れば良いことが分かり、小課題1,2の26点を取る。
13:30-(100+50+26=176)
小課題3の二分木のケースを考える。構築的な解法を考えたが、実際はプログラミング的な解法だった。小課題4には変な制約が付いていたが、真意が掴めなかった。残り時間が少なくなったので、Bに移る。
14:30-(100+50+26=176)
Bの満点を考えると、HLD+parallel binary searchで解けることが分かる。実装して、木のケースの小課題5に正解し、追加で23点を得る。
14:50-(100+77+26=203)
最後の小課題の小課題6は一般グラフのケースで、最小全域木を取ると木のケースに帰着できる。残り1分のところで提出し、100点を取る。（結果は見えていない）
15:01-(100+100+26=226)
ジャッジを見守る。
100点が返ってきて安心する。
15:02-(100+100+26=226)
コンテスト終了
感想
APIO2019は、開催日が土曜日であるところを日曜日と勘違いして参加できなかった。
APIO2020には参加できて嬉しい。
