この記事はharurunのお気持ちメインです。 解説は今週中にはあがります。
途中で敬体と常態が混ざってます。すみません......
5秒でわかる概要
- オンサイトコンテストをやった
- 5時間コンテストで26問出した
- harurunはかなり頑張った
誰
NAISTのharurunです。 レートは昔は1600あったはずが今は1500付近をさまよってます。 3月上旬に1593まで戻ったのに開催直前でABC3完をやらかして1500下回りました。最悪です。
後述する†Xx純白の聖剣士xX† のharurun4635さんとは別人です。
全体
†Xx純白の聖剣士xX† (中身はRinshan Solution?) 全完ギリギリするかしないかのラインでドキドキさせられました。 すごい感謝してます。
他の方々もたくさん解いて頂きありがとうございました。
開催まで
頑張った。 半年前くらいから準備しました。 当初は20問同時コーディング無しにする予定が、年末くらいに僕がトチ狂って6問増やして同時アリにしました。
テスターに渡した時点でテストケースがカスで、本当に申し訳ございませんでした。 ランダムに木を生成したら高さが $O(\log N)$ にしかならない、言われてみればそうなんですけど、考えもしませんでした。 この辺りは生成AIを用いてどうにかしました。どうにかなってるはずです。たぶん。 圧縮はしてないので結果としてジャッジに負荷をかけることになってしまいました。 どうにかならない部分は頑張って作ったりもしました。
テストランで(Aを除いて)難易度降順で出したらとあるチームが大事故を起こしてしまい、他の方の指摘もあり、さすがにまずいと思ってシャッフル(っぽく)しました。 実はB~Yは(絶対に気が付けないような)規則性があります。(B~Yの転倒数を計算してみると...? 並び替えたのはChatGPTなので人の手は入ってません)
作問方法
これを買って読みました。 Jとかはこれをやって生まれました。
ところで、記事内で触れられてる(と記憶している)ように、問題を作って解いて作問する方法は非効率という話だったんですが、これは生成AIの登場により、ある程度のレベルまでは非効率とまでは行かなくなったように思います。 生成AIは原案を出させるのは非常にカスなんですが、解法はある程度正しいので(人間が証明しましょう)、人間が考えた原案を投げて解けるかの判定には(ある程度)使えます。 実際に、いくつかの問題はこの方法を使用しました。 作問に生成AIを使用することに賛否両論はあると思いますが許してください。
生成AI作問と書くと原案も生成AIがやってそうな字面ですが、ほとんどの問題は人間が原案を考えてます。 (少なくとも人間の脳みそを経由してます)
各問題のお気持ち
A - I Hate Lazy Segment Tree
A問題にゲロムズなインタラクティブが置いてあったら面白くねという思想で置きました。 一番お気に入りの問題で、僕的にも少なくとも開始1時間で解かれるような問題ではないと思っていたのですが、Nachiaさんに47分で通されました(???)。 Nachiaさんを40分ほど止められたと考えればいいのかもしれません(???)。 全体を通してオンサイトで2チーム、オープンで2チーム、テストランで1チーム通していて、想定内かなという感想です。
ライターは $3Q-1$ で解いているんですが、見る限り $2Q$ で通してそうで頭いいなと思ってます。 テストランで通されて説明受けてそれはそうとなりましたが、 $2Q$ だと自明になる気がして $3Q-1$ のままで出しました。
B - Strong Shift
まあ、はい。頑張りましょう。 構文解析パートは良くて、計算部分がやばいですね。 これが無ければ。 trap.jp
無くてもいけます(解説参照)。
生成AI作問その1でした。 Wandboxに適当な数式を投げるのが趣味なので(???)、実際にどうなるか気になってやってみたら解けるらしいので、頑張って理解しました。
C - NASURA
ライターではないですが、生成AIが生成した500行くらいある焼きなまし/ ビームサーチ/ chokudaiサーチを落とすテストケースを作成しました。 焼きなましだけ落とすのに手古摺って2日くらい考えました。ありがとうDaily Akari。
こんなに解かれないと思ってなくて、驚きです。
D - Large Log
正当性が証明できずに消えた没問の代わりとして急遽生やしました。 $x$ が 2以上は赤文字にすべきだったかなと少し反省しています。
オンサイト全チーム通してえらい。
E - Sad World
実装が地獄。 一番最後に実装しました。 なもりだからほぼ木DPなんですが、オープンのほうは解かれなさ過ぎでは。
F - Cut Connect Operation
DEGwer式作問その1 (だったはず)。 全方位だよねという気持ちになるんですが、なぜこんなに解かれていない。 想定以上に解かれてなくて、解説に全方位木DPとしか書いてなくてやばいなって。
G - 2025
上手い感じに探索する必要があるんですが、オンサイト全チーム通しててえらい。
H - Shortest Path on Ring
生成AI作問その2。 生成AIに出させた原案を原型が残らないくらいに改造した、 これ作ったあとにABCでmin-plus半環出たのに解けなくて悔しかった。
I - Three Palindromes
原案が出されてから無限に悩んで線形で解けないなという気持ちになってたら、いつの間にかbitset解法が生えてた。 生成AIに投げると回文木の解法が出てくるが、作問陣誰も理解できなかったので流石に想定にはしなかった。 (が、回文木周りの嘘はちゃんと落とした、はず)
回文木使わずに(準)線形で解ける解法募集中です。
J - MAKE PATH
DEGwer式作問 その2。 これもお気に入りなんですが、通されるの早すぎませんか。 27分で通ってやべ～～って気持ちになってました。
K - Eat Bombs
生成AI作問その3？ 厳密には3年前くらいの原案ストックを投げたら解けるらしいというのがわかって、さすがに単純だったので既出を探してABCにあった。 ABCにあったのはグリッド上だったので2次元座標でも解けますよのお気持ちだったんですが、僕の典型力が足りてませんでした。 典型ではあるけど、そこまで自明か？という気持ちだったんですが、かなり自明だったらしい。 上位勢がみんな通すもんだからみなさん嘘貪欲をしてしまって順位表が大惨事に。本当に申し訳ございません。 サンプルに嘘貪欲を落とすケースを入れておくべきでした。大反省。
L - Grade Up
ライターが誰だか丸わかり。⍋はtexで出てこない(と思っている)ので色々大変でした。 思ったより解かれていてみんな賢いなと。
M - 孤独
生成AI作問その4。 $i=0$ だけ解いて(フィボナッチになる)、一般解ありそうだなと投げたら出てしまったので。 文字列への言い換えさえできてしまえば、あとは形式的べき級数なのでギリできるかなというお気持ちです。 これを機に形式的べき級数を勉強しました。 ジャッジが遅すぎてPythonの $O(N\log2 N)$ がTLEしたのは解せぬ。
N - NAIST String
僕は知りません。 Suffix Automatonで解けるよね。
O - Digit Sum 2
生成AI作問その5。 ストーリーに書いてある問題の乱択解法を評価したら高確率でACになることがわかって強化した姿。 ダイクストラやDPでテストケース当たり定数で解けるんですが、みなさん行列累乗してTLEバトルしてましたね.......
P - LIS Query
生成AI作問その6。 親だけ見ればいいのはそれはそう過ぎるんですよね。 想定より解かれずに驚きだったり。
Q - Non-Adjacent Subsequence
ジャッジに移植したらPython通らなくて草。
R - Ancestor Query
生成AI作問その7。 これは原案も生成AIに出させて、それを(人間が)改良して...を繰り返した。
S - Two Way Magic
生成AI作問その8? One Wayが解けなくてTwo Wayを投げたらギャグだったので、はい。 当初は入力に負があったり、大きさが $10^{18}$ だったりしたんですが、直前に 正整数かつ$10^{12}$ にした結果があの順位表です。
80分も耐えてくれてありがとう。
ゼロや負を許さないver.はずっと考えていますが(制約が大きいときは)解けてないです。
T - Fermat Point
ライターではないですが、幾何で解いて相対誤差ずれてもACできるかの確認をしました。 幾何の場合分けミスったものを落とすテストケースも作りました。
U - Coloring Graph
マージテク+DSUで、隣接の色を管理しなければいけなくて、非常に実装が面倒です。 生成AIより賢い実装をしてるつもりです。
V - Jump Game
生成AI作問その9。 生成AIが20分くらい考えると解けました(当時5.2)。
天才を要求してるようで、(空きマスを移動させることさえ見えれば)典型です。 左にすべて寄ったときを考えると、空きマスの偶奇になります。
蟻本を読むと解けます。
この辺りを読むと典型ということがよくわかります。 www.kyoritsu-pub.co.jp
W - Minimum Distance
これどっちだったか覚えてない......けどbitsetなんて僕が思いつくわけないから生成AIを使った気がする。 これも3年前くらいの原案ストックから。 出力が異常に多いんですが、これ以上減らすとFastIO+QCfium法の $O(N3)$ が通るので許してください。
X - Multiplication Table
以前九九表がTLで話題になってて、そこから着想を得て。 本当は $a\cdot b$ をまとめて出したいんですが、ポラード・ロー法は理論的な時間計算量の上界が存在しないので出せず。 本当に様々な嘘解法があって、ジャッジの割り算が遅いのもあり時間制限がギリギリになってしまいました。 ポラード・ローとミラーラビンの高速素因数分解の枝刈り解法が通ったのは許してください。
定数倍をかなり抑えて証明する必要があって、その部分だけ生成AIの助けを借りました。(嘘つかれまくったけど)
Y - Maximal Matching
生成AI作問その10。 元はbitDPではなく、愚直判定だったんですが、投げたらbitDPで解けるらしかったのでそっちに。
FAが4分で電流が走りました。
Z - Yes No Trouble
こんくらいは許されるだろうという気持ちで激長ストーリー文を出しました。
最初はnext_permutationsくらい要求しようかという気持ちだったんですが、簡単問は簡単であるべきという思想によりこうなりました。
for文で言われた通りに実装するとよいです。 ソートするとWAになります(意図してなかった)。
生成AIの使い道その2
解法が合っているか、カスタムジャッジにバグがないか。 (たまに間違えるので注意)
特に睡眠不足のときはやりましょう。
人間の目では見逃すところも見てくれるので投げるとよいです。 特にカスタムジャッジは意図しない動作をされると困るので念入りに。
出題範囲において、有名ライブラリにバグはありませんでした
そりゃ試すよね。残念。 デバッグ用の関数が範囲外参照してたりはしたけど。
謝辞
突然の依頼にもかかわらず、テスターを引き受けてくださった方々、ありがとうございました。
謝辞2
ChatGPTなかったら絶対に弱弱テストケースになってた。ありがとうOpenAI
