kaage精進録

雑な解説とかライブラリとかおきもちの垂れ流しです。

2020JOI春合宿参加記

第19回日本情報オリンピック春期トレーニング合宿に参加してきました。

Day1

集合は8:30で、少し渾身の懇親をした後、すぐに競技が始まりました。 どうでもいいですが、自分はこのような競技やテストの前には必ず特定のツイートをすることで知られています。

まず1問目を見ます。 小課題1が「ぼくDPだよ～！」と強く主張してくるので、DPを書きます。 これですぐ11点を獲得します。 O(N) で解ける雰囲気が漂っていて、これを解けさえすれば大幅に順位を上げられると確信したため、あとで解くと決めて次に進みます。 2問目を見ますが、全然わかりません。 とりあえず自明部分点2点を取ります。他の参加者が10点くらい取って自分だけ破滅する未来が見えたため、もう少し点を搾り取ろうと考察をしますが、1点の小課題が新たに分かっただけで他には何もわかりません。終了後結局ほとんどの参加者は2点未満しか取っておらず、3点は自分だけでした。特に、ABC-Cレベルの実装で取れる2点に、遅延セグ木を貼ってFortune Telling（2012年春合宿Day3-1）みたいなことをしようとしている参加者を多く目撃しました。

特に、強い人に聞いてもこの3点解法を考えた人は自分だけのようだったので、少し驚きました。 とりあえずこの1点はなんとなく面倒だったので後回しにして、次に進みます。

3問目を見ると、実家のようなJOIのデータ構造ゲーだとわかります。 愚直にシミュレーションをすると小課題1で1点もらえ、遅延セグ木を貼ると小課題3で11点もらえることが割とすぐにわかります。 特に小課題3の変な制約は、2016年の本選5問目、断層という問題で完全に既出な考え方だったため、「断層断層断層断層断層」と頭の中で唱えながら解きます。

小課題2の10点が全然わかりませんでしたが、とりあえず小課題3の方が点数は高いのでいいことにして、これらの実装に入ります。 そこまでバグらせることはなくすぐに終わりました。 ここで、後で完答すると決めていた1問目に戻り、考察を始めます。この選択が今日の競技で最も大切だったと思います。 さて、1問目、どう見ても O(N) なので O(N) 解をひたすら考えます。 DPから派生して遷移などを考えるとグラフ化して考えるのが楽だと思い、グラフを書いてひたすら考察をします。 実験をすると、O(N^2) のDPで持つべき値が必ず区間になりそうなので、これだ、と思って証明をします。できます。

実装でちょっとバグらせましたが、無事に通り、ここで勝利を確信します。 とはいえ、これは9人くらいが解いてくるというのが自分の予想でした。（理由は、体感難易度が同じだった昨年の春合宿の問題、Lampsが当時9人に解かれたからです。） 実際には13人もが解いてきましたが。 この時点でも2問目は何もわからなかったので、とりあえずもう1点を取るための実装に入ります。 すぐ終わり、合計3点が獲得できました。 E869120が3問目の満点解を通し、「やったー」と叫ぶのが聞こえたのは確かここらへんです。 これ以上考えても分かる気配はなかったので、2問目で他の参加者に負ける可能性を少し感じつつも諦め、3問目の小課題2を考えますがわかりません。 このあと、3問目の小課題2の嘘解法を2回発明して実装するなどして時間を消費し、最後には2問目の小課題6をkaage法で通そうとします。

f:id:kaage:20200320222307p:plain
kaage法をABC150-Fで使っている様子
しかしもちろん通らず、115点でDay1が終了しました。 終了直後、E869120が2完をしたと言っていました。さすが「やったー」と競技中に叫ぶだけあるなあ、と思いました。 順位は8位で、レーティング的には悪くはない滑り出しになりましたが、2位から13位まではほとんど差がついておらず、いつ誰が誰を抜かしてもおかしくない状況です。（この点、大差でリードしているE869120が強すぎる…）

この後解析/解説と写真撮影があり、そのまま解散となりました。 情報オリンピック日本委員会の科学委員長が、「そこの双子、マスコット提出して」と言っていたのが面白かったです。

2日目以降も頑張ります。

Day2

昨日と同じように8:30に集合し、すぐに競技開始です。 入口で検温を行うのですが、体温計の調子が悪く、34.0℃になった人がたくさんいました。 昨日から実家になった控室でいつものようにいつもの人と喋ってリラックスしました。 ホワイトボードに「私語NG.『ヤッター!』『全完!!』『よし、グラフだ!!!』などと書かれていて面白かったです。

今日もちゃんと開始時刻にいつものツイートをしました。

競技を開始し、封筒を開くと1問目からインタラクティブ問題です。 インタラクティブやコミュニケ―ションは一般的に実装が重いので、後回しにします。これが今日最大の失敗でした。 2問目はJoitterとMaking Friends is Funという過去の問題が元ネタとなった、Making Friends on Joitter is Funという問題です。 「よし、グラフだ!!!」と思った参加者もいただろうし、難易度も見た目非常に低そうに見えるなど、これを解けないとまずそうな雰囲気しかしないので、多くの参加者が困惑したことでしょう。 見た目難易度9/10くらいで、解けそうなので考察をしてみます。 Union-Findで併合をするなどして解けそうですが、細部が詰められずここで1時間使います。 解けそうな雰囲気がないのでまずいと思いつつも、部分点解法（嘘）を思いつき、実装しますがサンプルも全然合いません。 さすがに危機感を覚え、3問目のRuins 3を見てみますが、これも小課題含め何もわかりません。 とりあえず、「リア充爆発しろ」と思いながら1問目のChameleon's Loveで4点を取ります。（詳細は問題を見ましょう。） この辺で前のsquare1001がRuins 3を通してそうなのを察し、ちょっと怖かったです。 この下に20点の部分点があるので、今思えばこれを先に取りに行くべきでしたが、またMaking Friends on Joitter is FunとRuins 3に戻って時間を溶かします。 仕方なくMaking Friends on Joitter is Funで雑な実装をしたら1点が獲得できましたが、Chameleon's Loveの点を取りに行く暇はありませんでした。 結局このまま競技が終了します。絶望です。 周りに質問すると、25点や4点の人が目に入り、そこまで離されてはいなかったので少し安心しました。 双子が2人とも1完以上していて、やっぱり強いなあ、と思いました。 順位表が配られましたが、結局順位は変わらず8位でした。

これで、E869120がダントツ1位、square1001がダントツ2位、その下に人々が続く形となりましたが、上位勢はChameleon's Loveの部分点を通している人が多く、昨日より差は大きくなってしまいました。

あと、どうでもいいですが、帰りの電車で優美な貴婦人がたの集団がドアの前でたいへんin my wayで、またかまびすしかった限りでございましたので、小声で「性別Xうるせえ」と言うなどして、なんでXなのかとdefineに聞かれたので、染色体の話をしました。 3日目以降も頑張ります。

Day3

今日は検温が1発で終わりました。よかった。 控室に行くと、E869120がCommunicationの問題を出してくれたのでみんなでちょっと考察をした後、競技会場へ。 今日もなぜかsquare1001の後ろの席で、前から聞こえる凄まじいタイピング音を聞きつつ競技をすることになりました。 ところで、1日目と2日目には忘れなかった「いつものツイート」を今日は忘れました、強く反省します、明日は忘れないようにします… 競技が始まると、1問目のConstellation 3がなんとなくうまく解けそうな雰囲気がして考察をすると、重みつき区間スケジューリングみたいな問題だと分かります。 とりあえず実装をしてちゃんと考えると全然違うので、諦めて2問目を見ます。ここまでで2時間くらい溶かしています。 2問目のHarvestは解けないことはなさそうなものの明らかに実装が重く、やる気をなくします。 3問目のStrayはCommunication課題で、昨日と同様にここの部分点を稼ぐのが明らかに得な方策でした。 とりあえず部分点の20点を獲得して、Constellation 3とHarvestに戻りますが、やはり分かりません。 仕方がないのでStrayの考察をしていると、なんと満点解法が分かります。これが競技終了およそ1時間半前のことでした。 ここから実装に入るものの、大量のバグと実装量に悩まされ、時間があっという間に経ってしまいます。 残り10分くらいになってもいくつかのケースでWAが出ており、危機感を覚えて夢中でデバッグをし、WAの個数は着実に減らしていくものの結局正解には至りませんでした。 20点です。 終了直前に提出したコードでは、小課題5のたった5ケースでしかWAが出ておらず、非常に残念でした。あと20分あれば解けたと思います。 意気消沈して食堂に行くと、E869120が291点という驚異の点数をたたき出しており、Strayで満点を取っている同級生もいたので、絶望します。 結局順位を3つ落とし、11位となってしまいました。また、某同級生がStrayを通して抜かされたのはかなり悔しいです。 他にもStrayで満点を取っている参加者は多く、上位との差はさらに開いてしまいました。 食堂で、tozangezanさんが参加者のコードを観察した話をしていて、面白かったです。

張り合って、ABC008-CでE869120が114514桁出力していたり、「114514」という問題をyukicoderでsquare1001が作問していたりする話をしました。 明日は、難しい問題で不必要に時間を使わず、解ける問題をしっかり見極めることを意識します。 また、「よし、セグ木だ!!!」といった問題が出たときにしっかり部分点を獲得するのはとても重要だと思っています。これだけで順位が大幅に変動します。

では、最終日の明日、代表目指して頑張ってきます。

Day4

結論から言います。代表にはなれませんでした。（Day3までの結果でほぼ明らかだったので、当たり前です。） 今日も検温を1発で突破しました。やったね。 ツイートも今日はちゃんと忘れませんでした。

これまで3日間と同じようにすぐ競技が始まり、1問目を見てみます。 2019年4日目の1問目、Capital Cityは、難易度10のMergersという問題に似ていたので、多くの人が解いてくるのではないか、と一瞬予想しましたが、よく考えると結構難しく、そんなことはなさそうでした。 とりあえず小課題1は何をしても通るので、適当にsetを持ちながらDFSをして、通します。 2問目のLegendary Dango Makerを見ると、Output Only Taskです。ここしか得点源がないことを察したので、ここに全力を注ぎます。本家の団子職人はまだ解いていないので少し不利な気もしましたが、仕方ありません。 適当に貪欲を書いて提出しても、1点しか取れず、仕方ないので山登りを書きます。 適当に高速化したり、初期状態を工夫したりすると31点まで取れますが、それ以上一向に伸びないので一旦諦めようかと思いますが、ここで30分くらい粘着してしまいます。これが良くなかったです。 3問目のTreatmentは、区間クエリにひとひねり加えたような問題です。 とりあえず小課題1が遅延セグ木で取れるので、ささっと書いて通します。 小課題2はビット全探索でしたが、実装が重いので必死にコードを書きます。しかし、間に合いません。 これで競技が終了してしまいました。 1+31+4=36点です。合計は176点でした。

反省

まず、立ち回りが下手でした。 Making Friends on Joitter is Funや、Constellation2などの難易度の高い問題に粘着して時間を溶かし、結局解けなかったのは問題です。 これで、Chameleon's Loveなどの解ける問題に時間を使えませんでした。 また、単純に実装が間に合わないなど、実力不足な面も見られました。 来年までに実装力も考察力も強化して、代表目指してまた挑みたいと思います。