JOIsc 2024

JOIsc 2024 の参加記です。問題のネタバレを多く含みます。

去年は春合宿を通過できると思っていなかったため気持ち的には軽かったが今年は去年通っている上で最終学年なので緊張面ではかなり去年よりは不利だったと思う。参加者内レート 1 位だが去年より下にかなり詰められてしまっているのもあり、勝てるかどうかがかなり怪しかった。本選はかなり事故ってしまったのもあるが低い順位を取ってしまったことも精神的に悪影響だった。

day 1

問題を全て見る。batch - communication - batch で見る限りは普通のセットだった。

fish3 が簡単枠に見えたので取り組むと D = 1 がセグ木で処理出来て、D が一般の場合は自分の作っていた問題(AGC065-A)と似ていたのですぐ気付くことが出来て 100 点を取ることが出来た。

次に ski2 を見る。自分はこのような嘘貪欲が無限にありそうで O(N^2),O(N^3),O(N^4) のような dp が想定解である問題が苦手なので身構える。始めの小課題 2 個を取るもそれから先が一切見えない。N <= 10 すらもいい探索方法がわからず、難易度 12 の不可能問題に見えてしまった。ここで嘘解法を無限に生やして時間を消費してしまう。結局点数は伸びなかった。

流石にまずいとなり spy3 に取り掛かる。自明の 8 点は生えるがそれ以上がなかなかわからない。ここで、わからない辺の始点に対してそこに頂点 0 から最短経路で向かう際に最後に通るわからない辺の終点の情報を送ればよいことに気付き実装に取り組む。しかし最後までバグが取れることはなかった。

100 - 8 - 17 で 125 点全体 8 位だった。ボーダーまでは 61 点もある。ski2 が不可能枠ならそこまで酷くないとは思っていたが周りがかなり ski2 を通していたのでかなり酷い結果となってしまった。本選 C でも同じような問題で同じようなミスをしてしまっていたのでかなり落ち込んだ。去年はかなり調子がよかっただけだったのか？とも思った。

day 2

ここである程度取り返さないと本当に間に合わなくなってしまう。セットは batch - communication - batch

vegetables5 を見る。N <= 2000 までは自明で、二分探索をすると点と幅が定数の区間があり、点削除と点追加と全体で点と区間のマッチングが出来るか答えるクエリを処理する問題になる。少し悩んだがこれは区間の左端と右端に分解してそれぞれ累積和を左と右から取れば 1 点加算累積 min セグ木で処理できる。だが log が 2 個と重い定数倍のせいで N <= 2000 のケースまでしか通らない。この問題でまだ使っていない A が山形であるという制約があるのだが使い道もよくわからず定数倍高速化を試みるも通ることはなかった。

今日もまずいとなり boardgame を解き始める、少し考えると人 1 以外は 1 回目以外は 2 回の移動でターンを終わらせられ、それとは別に少し遠回りして毎回ターンを 1 回で終わらせることも出来る。これは始めを除いで折れ線になるので折れ線を何本かの直線に分解して人 1 からダイクストラをすると O(MKlogM) などで解け、K が大きい場合は人 1 が遠回りできなくなるのでこれで解けそうだと思い、前者の解法を実装するも K = 2 は通るが N,M,K <= 3000 と K <= 100 が通らない。これも結局バグは取れることがなく 40 点で終わってしまった。

tricolor は少し考えてある 1 箇所だけ同じ色にしてそれから両方側に違う色を伸ばして N <= 250 の 10 点だけを取る。

40 - 10 - 30 で 80 点。A,C は満点が分かっているので確実に終わった、代表争いから外れたと思った。だが周りもバグらせたり TLE したりしていてこの日だけなら 5 位、全体なら昨日から 2 位上がって 6 位に浮上。本当に助かったが、まだピンチは終わっていない。この時点でボーダーまではあと 37 点。

day 3

day 1,2 は両方失敗に終わってしまったため今日でなんとか巻き返したい。セットは今日も batch - communication - batch

見た目が簡単そうな tower を解こうとする。B = D,A = 1 のケースはつまり到達判定が出来ればいい。踏める N+1 個の区間それぞれに対してそのうち他の区間から +D で飛べるもっとも手前のマスがわかればよく、これは適当に処理すれば解ける。少しバグらせるも 25 点。B < AD のケースが問題で、出来るだけ +D を使いたいという問題になる。先程までとあまり変わらないが、ある区間に他の 2 個以上の区間から遷移が来た時にごちゃまぜになりそうでよくわからない。とりあえず一旦置いておくこととする。

collection を見る。とりあえず 3 値化すると {1,1} のペアがあればその端がずっと {0,2} もしくはその反対でなければ OK、{0,1},{1,0} がそれぞれあれば {0,1} は {0,2} を、{1,0} は {2,0} を消せるため {1,1} よりも軽い条件...とこのように沢山条件がありいずれかを満たすかを判定のように見えたが場合分けの量が異常に多い。そこで、長さ 5 以下の場合全てに対して解きその Yes のケースのいずれかを部分列に含んでおり更にその左、右側が対処できるなら Yes を返すコードを書く。落ちる。

とりあえず長さ 5 以下を解くのに使った区間 dp を出して 11 点を取り後回しにする。

tower に戻ってくる。ここで「2 個以上の区間から遷移を受けたとしても、1 個の区間から遷移を受けたときの状態として持つことが出来る。」という予想をして実装に取り掛かる。マージがかなり複雑でバグらせるもランテスを書き何度も何度もバグを修正することでなんとか 100 点。ここに来てようやくきっちり問題を解くことが出来たので思わずガッツポーズをしてしまった。

collection で端らへんのケースが不味そうと思い色々と処理をする。この時点でそれぞれのケースに対して 2000 通り以上も Yes のケースを試していたのだが N <= 2000 だけでも取ろうとする。端に {0,2} や {2,0} のあるケースを追加したり、端についての処理を色々書き換えたりするとランテスが落ちなくなったので提出すると N <= 2000 が通り 49 点になった。恐らく難問枠であろうことからかなり大きい 38 点だと思った。

N <= 200000,M <= 10 を通そうとケースを削ったり定数倍高速化をするもなかなか通らず諦めた。(コンテスト後に色々と試していたら通って 71 点まで伸びた。)

ここで手つかずの joitour を考える。自明な 20 点は取るが、余事象にこだわってしまいパスの場合に行列をセグ木に載せる解法が見えずこの世の全ての情報をセグ木に載せようとしてしまい結局間に合わなかった。

49 - 20 - 100 で 169 点。心残りは joitour が点数をかなり取られているか collection の簡単な解法があるかだがどちらもなくこの日だと 1 位、全体だとなんとか 4 位のボーダーラインになった。かなり成功した寄りだったので安心した。

3 日目にしてようやく成功を引くことが出来た。だが 5 位との差はたった 3 点で気は全く抜けずいずれにしよ苦しい状態だった。

ところでだが、私の A は実は嘘でありランテスをかけ続けると N = 5 のケースで落ちるケースがあった。(これに気付いたのはコンテスト後の話だが...)

追加する個数を多くすれば正当なのかそれともどれだけ多く追加しても嘘解法なのかは分かっていない。

day 4

今日で最悪の場合 JOI 人生が終わってしまうと考えるとどうしても緊張してしまう。ただ day 1 の状態からここまで持ってきたのだから意地でも勝ちたいと思った。

セットを見る。最終日も batch - communication - batch である。だが最後の batch は構築だった。

まず espace2 を考える。M_i <= 5 の場合は始めに乗る飛行機を決めればあとは一意に定まるので平方分割をすれば解けると思い実装するも N <= 2000 すら TLE した。ここでダブリングが使えることに気付き、ダブリング解法に切り替えて M_i <= 5 を全て取り 54 点。これ以降は M_i が大きいものを平方分割しそうだったがとりあえず置いておくこととする。

tabbletennis を見る。とりあえず M <= N-2 と N <= 7 を実装する。するとそれぞれの N に対して達成可能な M 以下の値は全て出来そうである。ここで最大値をなんとか構築してそこから勝敗を swap して三すくみの個数の変化を O(N) で求め、減ってかつまだ M 以上なら採用を繰り返したら出来ないか？という大胆予想を立てる。まずは最大ケースの構築である。N が奇数のときは人 k は人 k + i(1 <= i <= (N-1)/2) には勝ち、それ以外に負けるとする、偶数の場合はほぼ同じで余った辺を適当に向き付けると最大値が N <= 7 で愚直と一致した。ここから 1 回 swap して上手くいったら採用を繰り返すコードを提出すると N <= 20 が通りかなり喜ぶ。ここでどこまで通るかを試してみるとなんと N <= 150 までは通ってしまう。N <= 600 だと TLE したので、始めの構築を答えの最大値が M を超えるギリギリの N を持ってくると減る回数が抑えらえるのでは？と思い採用してみると N <= 600 でも通った。ここまで来たら bitset 高速化も試してみる。残念ながら TLE する。だが手元で色々試しているとやけに実行が早くなり、出力がボトルネックになっていることに気付いた。ここで ios::sync_with_stdio(false) を忘れてしまいかなり焦ったがなんとか思い出して提出すると 100 点。N <= 20 のまともな解法すら思いつかなかったのでかなり大きい 100 点だと思い、かなり喜んだ。

一旦 espace2 に戻ってくる。M_i が大きくても、sqrt max M_i 回移動すれば今乗っている飛行機の候補は sqrt max M_i 回に抑えられる。なので、移動が sqrt max M_i 回未満のときは答えを前計算しておいて、そうでない場合は sqrt max M_i 回移動した先の飛行機のどれに乗るか、それに L_i からたどり着くにはどれだけかかるか(これは前計算から分かる)を考えれば O(sum M sqrt max M + Q sqrt max M log N) で解ける。これで N,M,Q <= 9e4 を通して 90 点になる。この時点でかなり勝利の確信があったが、tabbletennis が天才構築があり全員通している場合があったのでまだ気が抜けない。9e4 すら 1.5 秒程かかっていたので残りの 10 点は諦めて残りの問題をやることとする。

island を解くことにする。とりあえず L = N^2 の場合が葉から考えると解けたので実装する。ついでにパスグラフとよくわからないグラフについても解き 50 点を得る。ここから頂点の index が小さいものから順番に辺で繋がれている頂点集合を特定する方針を考えたが 2 ケース落ち、1 ケース落ちが続いてしまって最後まで L = 3N すら通せなかった。

90 - 50 - 100 で 240 点でこの日だと 1 位であり、全体だと 2 位で IOI に進出することが出来た。この日の結果はかなり満足できるものだったが、island はもう少し取れてもよかったなとも思った。

全体を通して day 1,2 は大失敗してしまったものの day 3,4 は上手くいったのでなんとか代表になることが出来てよかった。ただ自分の弱点である次元の高めの最適化問題の弱さや実装のバグを取る速度も際立ってしまったので IOI までに対策を重ねたい。

IOI では去年以上の満足の行く成績を取りたいと思う。