IOI18 Virtual Contest

もう1,2週間前の話ではあるが、IOIに向けた練習をはじめた。QOJのコンテストサイトを見ればわかる通り、集団的にやっているがそれはそれとして。

IOI18を両方走った。私は取れる部分点をすべて集める、堅実な立ち回りといえるものを好んでいる。実際、これで失敗したのはJOIspのDay3とAPIOくらいだろう。APIOは取れる部分点を堅実に集めたらshowが全人類に解かれていて終わったのでかなりトラウマだが、それはまた別のお話。

ということで、今回もその戦略で走った。コンテスト中の立ち回りとその反省をまとめる。

Day1

問題を見る。精進中に簡単枠であることを知ってしまったCombo君がさりげなくいるが、とりあえず全問を見る。たぶん知らなくてもComboから挑むであろうセットだったからセーフということで…

真面目に考える。初手の文字をとりあえず2回の質問で特定すれば、あとは2N回くらいで特定できそう。まあそれではだめで、もっと改善しないといけない。乱択とかを考えたが通る確率がすさまじく低そうなものしか思いつかず、そういえば4N文字使えるなあ、今2N文字くらいしか使ってないなあとか考えていたら生えた。Aが最初の文字だとして、B,XB,XX,XYをつけて質問すればよい。最後の文字を決めるときだけ困るが、ちょっとだけ余裕があったので2回質問すればよし。普通に実装も楽で、簡単に満点が取れた。

SeatsとWerewolfの部分点を見て、どちらも1次元の場合を解くとかなりおいしそうということがわかった。Werewolfは嫌な見た目しかしていないので、Seatsを解いてみる。しかし、考えていくうちにSeatsのほうがヤバイ気がしてくる。

冷静に考えると、いるいないの境目が2個以内ならいいらしい。遅延セグメント木があれば処理できそうだが、最近空書きしてなかったこともあって別の楽な方針を探す。少しして、セグ木で処理できそうであることが分かった。書いて提出するが謎のREが出る。他の人も同じ症状に合ったらしく、QOJからoj.uzに変えたらいけた。Seatsの小課題5をゲット。その勢いで自明な124を取る。3は全然わからず、後回しにすることにした。

Werewolfの1次元の場合を考える。とりあえず、Moをしてみるとセグ木に乗せるやばそうな解法が浮かぶ。当然そんなものを実装して通るはずはないのだが。Moを使わない方法を考えたが、それは冷静に考えたら自明だった。小課題3をゲット。その勢いで自明な1,2もとってしまう。満点は思い浮かぶ気がしなかったので、Seatsに戻ることにした。

小課題3を考える。いろいろ考えるうちに、長方形領域が拡張される回数が高々H+W回であることを利用すればよさそうだと思った。実装して提出するがTLE。例によってQOJからoj.uzに変えることを試してみるとTLEは割と余裕で回避していた。QOJだめだこりゃ。

そのあとは特に成果はなく、100-70-49で終わった。本番8位相当でうれしいのだが、他の人はみんなWerewolfの満点を取ってたらしい。可能枠らしいのでUpSolveを試みた。うまくマージすると木構造になることまでは気付いたものの、うまくマージする線形時間とかの方法もそこからの処理もめんどくさそうで、未だに寝かしている。ダメですね。反省しましょう。

Day2

既に他の人との実力差を見せつけられていて泣くが、Day2もやる。今回は、とりあえず紙を印刷することにする。私の場合、紙に問題文があったほうが見やすいらしい。

全問題を読んでみる。Dollの見た目がなかなかに嫌だが、冷静に考えたらそれほどでもない。とはいえ残りの2つがあまりにも人間的な見た目すぎる。OIはこういう問題の方が難しいのが定石なので、Dollを考えることにした。

こんなん自明やろと思ったが、よく考えたら困るのは同じやつを2回以上通るやつ。それをうまくスイッチで分岐すればいいらしい。

QOJから取得できるファイルに不備があったのでoj.uzでバチャ自体をやることになったのだが、そのときにSolvedが見えてしまっていた。Dollが比較的簡単であることが見えてしまったが、見なかったことにする。ちなみに、この拡張機能の存在を教えてもらい導入した。次回からはこんな悲しい事故はないだろう。きっと。

アクシデントとは関係なしにDollを引き続き考える。それぞれから分岐させようとすると最低N*1.2くらいかかるのが容易に構成できてしまったが、冷静に考えたら分岐させるのは1か所からでよかった。というわけで、結局N回入ってそれぞれ違うルートに分ける回路を構成するゲームになった。

2分木状にしていらんところからスタートに戻す、はすぐに思いついていて、実はこれでいいのだがこれN*1.5くらいじゃね？になっていた。Pythonでいろいろ実験するうちに、実はN+logNで抑えられていることを知ったので安心して実装する。

めちゃくちゃバグらせたが、なんとかAC。これに2時間かけてるのは反省した方がいい。

Highwayの木構造の部分点がおいしそうなのでしばらく考えていたが、うまく考えがまとまらない。いったんMeetingsを考えることにした。

H<=20をとれたらおいしいつもりでいたが、全然自明じゃなくてつらいのでとりあえずそれより前の自明たちを全部取っておく。H<=20をかなり長い間考えて、max(H)*2個くらいの情報をセグ木に乗せたらいけないかなとか考えたが、重そうで諦める。これはコンテスト後に知ったことだが、この方針でいいらしい。本番中はちゃんとこういうの実装しないと駄目だね…

Highwayの木を考える。二分探索して、パス上に含まれる辺をひとつ特定することができて、そうしたら片方の端点からの距離を二分探索、そしてありえる頂点を二分探索とする解法が思いついたが、これだと60回をわずかにオーバーしてしまう。どこか無駄がないか探ると、よく考えたら2つ目の二分探索はいらなかった。これで安心して実装できる。無事に木の部分点が全部入った。

その後は何の成果もなく、100-51-36で終わり。悪くない気がしていたが、他の人たちの提出をカンニングしてすべてを察した。この人たちみんなHighwayとってるやんけ。割とへこんでいたが冷静に考えたら私の成績も本番10位くらい相当であった。

2日の合計点は406点で、本番8位相当らしい。かなりうれしいが、これはもう5,6年位前のコンテストなのでこの程度の実力では通用しない可能性も十二分にある。中国チームとか全員LGM経験者の化け物たちなので…

今回バチャをしたうちの2人が合計点で500点を超え、余裕で本番1位相当をとっていた。周りとの実力差が大きいことはもちろん理解しているつもりだったが、ここまで実力の差を見せつけられるとは思わなかった。それにしても軽々本番1位相当を取るのおかしいと思うんですが、これこの人たちが強すぎるだけですよね？