JOI23/24の参加記です。本選までです。雑です。

一次予選たち

流石に楽勝でした。絶対需要ないので何も書きません。RTAしたり、3回目で1時間くらい存在を忘れていたりしました。

綺麗なフラグ回収ですよね、これ

A:一行　00:17
B:mod7 00:44
C:oだけ分ける 01:15
D:難読 02:36

第3回で2分切りたい
— はるく@競プロ (@halc_kyopro) 2023年10月15日

15時まで一次予選のこと忘れてた
— はるく@競プロ (@halc_kyopro) 2023年11月18日

二次予選

流石に通るとは思っていましたが、通らなかったら恥ずかしいなんてレベルじゃないので、結構緊張していました。

以下、小課題1のことを①と表記します。他の小課題も同様です。

1問目 (0:00:56)

setに想いを乗せて希望の風に乗ります。

2問目 (0:06:13)

絶対そんなわけないと思いながらも、BITに想いを乗せました。時系列順に処理すれば、計算量がひどいことになることもないです。

想定は二分探索らしいです。うん、絶対バグるのでBITで正解ですね。

3問目 (0:12:55)

ちょっと面食らいましたが、余るものが絶対区間になると気づけば消化試合です。DPでよいです。

絶対2問目より簡単じゃないですか、これ。2問目は難易度6に、3問目は難易度5.5に投票しました。

4問目①② (0:48:35)

急に殺意高くないですか？

結構考えましたがいい性質が見つからず、とりあえず5乗の自明枠を書きました。

5問目①②③ (1:24:05)

4問目は普通に考えてもわかる気がしなかったので、5問目に移りました。

が、変な嘘に気が付いてしまったあげく実装できませんでした。自明なのと、計算が容易な③を書きました。

4問目④ (1:48:16)

戻りました。赤の場所がとても多いので、赤以外の場所が中心なものを全探索するのは余裕です。

赤だけのものの最大値は、最大正方形の問題と同様にDPで求められるので、それを書いて提出しました。

結果

4問目⑤を考えましたが盛大にバグらせ、この後は何の成果も得られずに終わりました。

結果は374点。結構いい点数ではありますし、突破はほぼほぼ確約されているようなものですが、同レート帯からするとカスな結果*1で落胆します。

解説を見ました。4問目が天才でした。翌日すぐに通しました。*2

こんなんでも無事に通過し、本選への挑戦権を手に入れました。

～本選

3問目で詰まって敗退する悪夢を数回見ました。怖い。

正夢にならないよう、難易度9を調べものとライブラリ禁止で結構埋めました。得たものは多い気がします。*3

難易度7を埋めなさすぎですね…

本選1日目～2日目

ガイダンスに参加しました。自分の自己紹介を見るの恥ずかしすぎる。

その後の交流会で、95/100を獲得して2位でした。最終問題で、チームメイトが導出した答えがあってたのに自分が導出した間違った答えを提出してしまい、萎えます。

その後、最大人数のGarticPhoneが行われました。誰とは言いませんが強い人が数回お題を捻じ曲げる大戦犯*4をしてて、「あ、この人も人間なんだな」と安心しました。

本選前日、tatyamさんの本選模擬に参加しました。しかし、2問目の満点が取れず落胆します。

ちなみに、答えで二分探索でした。気づけよ。

典型を最終確認し、翌日に備えました。

本選2日目

絶対に通りたかったですが、去年中2本選落ち黄コーダーがいたのでめちゃくちゃ不安でした。

1問目 (0:22:31)

昨日見た、答えで二分探索が見えました。しかし、実装難を感じました。

頑張って実装して提出したものの85点。WAかと思ったらTLEだったので、QCFiumをするも得点は上がらず。毎回vectorを作らず、再利用するようにして満点が取れました。

ちなみに、二分探索なんていりませんでした。ばーか。

2問目 (0:36:41)

1問目より簡単ではと思いました。すんなり方針は立ち、実装します。

実装後、未証明ですがなんか答えがあってうれしくなることに気付きます。提出して、一発で満点を獲得しました。

3問目① (1:04:26)

まじでなんもわかりませんでした。

一応しばらく考えて、左端に行く→右端に行くのような貪欲を思いつきました。

これが正しければセグ木で高速化できるなとか考えて、愚直を実装するが小課題1しか通らず。そんな…

悪夢が現実になりそうで焦りました。

暫く考えても正しい方法はわからず、4問目に移動しました。

4問目 (2:50:54)

見た当初は何もわかりませんでした。3問目も5問目もわかっていなかったので、本選落ち黄コーダーになることを覚悟しました。

しかし、マッチングといえばのHallの定理を思い出し、愚直で判定できる必要条件を見つけました。

何回か使ったことがあって信用できるWavelet Matrix | Nyaan’s Libraryを借り、愚直を実装して50点。点数は想定していたので、解法が正しいことを確信しました。

ここで、このコードの一部を抜粋します。

    rep(i,Q){
        int L,R;
        cin>>L>>R;
        L--;
        string ans="Yes";
        rep(j,L,R){
            if(bw.range_freq(L,R,A[j])-1<aw.range_freq(L,R,B[j])+1){
                ans="No";
            }
        }
        print(ans);
    }

ここで、awはAをWaveletMatrixにしたもの、bwはBをWaveletMatrixにしたものです。

また、range_freqはWaveletMatrixの関数です。

私は、この部分に注目しました。

bw.range_freq(L,R,A[j])-1<aw.range_freq(L,R,B[j])+1

これが、

bw.range_freq(L,R,A[j])-aw.range_freq(L,R,B[j])<2

移項するとこうなって、

bw.range_freq(L,R,A[j])-aw.range_freq(L,R,B[j])<=1

この値は明らかに整数なのでこうなって、

bw.range_freq(L,R,A[j])-aw.range_freq(L,R,B[j])==1

この値が0になることはありえないのでこうなります。

この式の条件を考えると、[B,A]の区間がほかの人と重ならない人がひとりでもいたらNoという、あからさまに答えな条件に気付きました。

各人に対して、そのような条件を満たす左端は遅延セグメント木で計算できます。右端もです。

あとは、クエリ先読みをし平面走査のようなことをして提出し、満点を獲得します。長かったですが、一気に勝ちを確信します。

3問目②③ (3:01:25)

とりあえず、bitDPで書けるところは書きました。

$N\leq 100$ を考えましたが、区間DPがちらついたものの糸口はつかめませんでした。

5問目①② (3:24:42)

まあボス問なので何もわかりません。とりあえず、適当な01BFSを書きました。

結果

3問目を一生考えていたものの、もう何もわかりませんでした。

結果は100-100-24-100-16。Dの満点のおかげで勝ちを確信します。

解説を聞きましたが、3問目はやはり区間DPでした。気づきたかったなぁ…

ちなみに、 $N\leq 500000$ の小課題の本質には気づいていました。区間DP気付いてたらワンチャン3問目の満点を取れたのか…

まあ4問目の満点取れたし、ヨシ！

しっかりと通過していたので、春合宿への切符を手に入れました。

おわりに

本選まででもすでに楽しかったです。春合宿は、行けたら後編にします。

いい成績をとって散るぞ！！！

*1:Magentorくんが強すぎる

*2:5問目は知りませんし通してません

*3:02/04時点

*4:ちなみに、この強い人はちゃんと春合宿に行きました

halcの競プロ精進ブログ

はるくが競プロしたことを書き留めるなにか

【参加記】JOI 2023/2024 参加記 (前編)