# IOI17 Day2 Virtual Contest

例によって全問題を見る。インタラクティブ2問なのが怖そうだが、唯一のBatchであるbooksはがんばればいけそうな気がしてくる。正直OIのこういう系の問題はかなり苦手なのだが、そんなことを考えていても仕方ないので考察を始めた。

暫く考え進めるうちに、サイクルをいい感じにつなげばいいらしい。ひとつのサイクルを処理するとき、その区間内にあるやつはコストを増やさずについでに処理できるのだが、外にあるやつはその距離ぶんだけ出張しないといけない。というわけで区間のマージでよさそうな気がして実装するが、実装途中でグループが`aabbaa`みたいに分かれていてかつ `b` からはじまるとやばそうということがわかった。ついでに謎だった $s=0$ の意味も理解できて、$s=0$ ならこういうことがないらしい。確認のため、実装しきって提出すると案の定50点が返ってきた。それはそう。

ここからセグ木を持ち出していい感じにやれば満点が取れそうな気がしたが、実装していくうちにだんだん細部を詰めるのがやばそうな気がしてくる。提出してバグを取ってを繰りかえし、ここで2時間くらいを徒に浪費してしまった。

しばらくして、やっていることがそもそも間違っていることに気付いた。さっきみたいなやつのもっとも外側に出れればあとは $s=0$ と同じことをすればよくて、結局ダイクストラ法みたいなことをすればいいだけであった。実装して漸く満点が帰り、安堵のようなものを覚えた。ここまでで2時間半ほど。

prizeとsimurghのどちらを考えるかは迷わなかった。prizeの部分点をよく見ると、なんかクエリの数を減らさずに90点が取れ、そこからはかなり頑張らないと100点にはならないみたいなことが書いてあった。90点だけ取ってsimurghに行こうと考えた。

prizeの90点もすぐに思いついた。飴以外の箱は500個くらいしかないはずで、それらを片っ端から開けてよさそうだった。飴かそうでないかは二分探索を繰り返せば最低限のコストでわかる。計算してみると9500回必要そうだったが、まあよさげなので実装する。少しバグらせていたが、直すと何事もなく90点が帰った。ここまでで3時間半ほど。

当然残りの時間でsimurghを考える。$n\leq 240$ というのは、辺の数がクエリの数を超えないぎりぎりの数ということだろう。そういうことを考えていたらそこまでの解法が生えた。

まずは適当に全域木をとる。そこからすべての辺に対して、その辺を取り除いて別の辺をつけたらまた全域木になる、みたいなすべての辺にクエリを投げる。そうすると、ソートして大きい方が含まれる辺であり、そうでないほうが含まれない辺である。ただこれだと重複して質問しすぎるので、答えに含まれる、または含まれないとわかった場所については端折る。

実装して、春のバグ取り祭りになったものの通った。51点。残りの時間で19点を取ろうと試みるが、これは無理だった。

90-100-51Σ241だった。本番10位相当くらいでいいのだが、この年の日本選手団の3人に負けた。maroonさんとyutakaさんに勝てるわけがないよ…

Day1もやったが、結果だけ言うと73.53-20-0Σ93.53だった。正直やってるとき最悪な気分すぎたので、思い出したくもない。(Day1を書いていない理由もこれ)

2日の合計は334.53点で、僅差で銀メダル相当であった。Day2で反省すべきところは特に思い当たらないので、Day1でもう少しでもとれていれば…