ACPC2025-立命セットの話とかを書く

を、書きます。主に僕の作問(CとK)の話とかです。C, K以外は解法に触れるつもりはないですが、まぁネタバレはあるのでご注意を。

さて、オンサイト・オンラインともに参加してくださった皆様ありがとうございました。connpassページ上ではあまり参加人数が多くなさそうで(ショボン...)としていましたが、実際にはたくさんの方が参加されていて嬉しい限りです。昨年のRUPC2024は運営に関わっておらずであまり詳しくは知らないのですが、サークル内で聞く感じ去年よりも良いセットが作れたのではないかなぁ、と思っています¹。

セット全体の話とか(軽く)

なんか個人的に難しいな〜と思ってた問題が多かったんですが、かなりの速度で多くの問題が通されててびっくりしました。人類は天才です。

12問・同時コーディング禁止・簡単枠は特に設けていないセットでこの速度ってマジですか？個人的にはFが思ったより通されたなぁという印象があります²。結構難しいと思っていて、私は挑戦しましたがいまだに通せていません。あの？

セットの配置自体は問題が生まれた順になっていて特に何かを意図した配置をしたりはしていなかったのですが、3問ずつ割るとちょうどギャグであるEが最初に見られやすくて開始早々バレてしまったのがちょっと悲しい³。

Gは0ACだったわけですが、まぁ、むずいよね...

自分の作問文について

まず2つぐらい謝罪をさせてください。

CのPrefix Sum Permutationについて、$O(N^2\log N)$が想定解だったのですが、制約でかなり非本質な勘ぐりを産んでしまいました...。思ったよりAOJのジャッジが早くて、なんと元々設定していた$N=5000$では$O(N^3)$が通ってしまい、致し方なくという形で⁴少し強くしました。これでもランダムケースはほとんど通っており、キラーケースのみがTLEとなるぐらいなんですよね...

KのTiny A=Bの方ですが、自分の確認不足で問題文に不備がいくつかあり、本当にもうしわけないです... これは本当に....

私個人としては初めての作問⁵で、原案が全然生えなくてにゃーんと言っていました。原案をたくさんはやせる人は本当にすごいと思います。不可能か自明しか生えん。

C - Prefix Sum Permutation

たくさんの人に面白いと言ってもらえて嬉しいです。見た目の上では怖い⁶ですがよく観察するとかなり典型の問題に落ちてくれて自分としても好きな問題です。

個人的には簡単枠ぐらいのつもりで置いていましたが、FAが30分経過した後と思ったよりACが出ずびびっていました。その後はどんどんとACが出てくれて安心。$O(N^2)$で解けるんだなぁとか思っていました⁷が想定は二分探索分の$\log$を許容するつもりで出していました。

「やっぱり競プロといえば順列の問題っしょ！」とか言いながらARC178A - Good Permutation 2を眺めていたら突如生えました。結果として全然違う問題に落ち着きましたが。本当は貪欲っぽく見せたくて$O(N\log N)$ぐらいの解法を模索していたんですが、そんなの可能なんですか？となってしまって、運営陣からも強化が提案されることもなくそのままの形で世に出ました。

あまり触れられていない⁸ですが、入力例2に置いてあった

5
65 67 80 67 2025

は、前半4項をASCII文字としてみるとACPC2025になります。小ネタすぎる。

K - Tiny A=B

考察自体は気付けば一瞬で終わるんですが、そのあとが面倒くさい問題でした。思ったより通されなくてびっくり(全体で2AC)。というか、本当にACしてくれてありがとうございます。

本質パートは、「$N$行のプログラムのうち、実は実行されうる命令は高々26通りとなる」で終了です。でも実際にこの部分はネックになっていたのかな？という感じで、「本質部分に気付いた瞬間解けるじゃんこれ、ってなりました」という感想をいただいて良かったのかもしれない？ 実装パートは操作が高速にできるならばなんでもよくて、想定のTreapを用いる方法のほかに隣接リストを使ってうまくやる方針が提案されていました。他にもいろいろありそう。

提出を覗いている感じ、無限ループの判定がかなり省略されていて少し悲しい気持ちになる⁹などしました。まぁちゃんとやると面倒くさいし、制約で出力する値の文字列長を示しているので仕方ないという気持ちもある。うん...。ちゃんとやると考えることが多くてマジで面倒くさいです。

元ネタは言うまでもなくSteamで配信されているゲームA=Bです。めちゃくちゃ難しいです。なんかチューリング完全らしい？証明のPDFがゲームについていたので読んだが、読めない。実はこの問題の提案と合わせて以下の問題の提案を考えていましたが、5秒ぐらいよく考えるとプログラミングコンテストではなくA=Bだなぁとなったので棄却しました。興味があればぜひ。多分解けます。私は解いていません。

2進数の排他的論理和の式が与えられる。具体的には、 010101^100100 のように、複数の0と1、および^一つからなる文字列が与えられる。 この式をevalするA=Bプログラムを1つ出力せよ。

命令長は全部書くのを禁止するぐらいの制約で、A=Bで使える命令は全て許容とする気持ちでいました。

---

ということで、振り返りでした。楽しんでいただけたなら幸いです。次回がいつになるかはわかりませんが、またよろしくお願いします。

Footnotes

1. より良いセットを世に出せて嬉しい、の意 ↩

2. 実際は$O(W^3)$が想定解で、非想定の$O(NW)$が思ったより通されてしまった(運営のTLE解はちゃんと落ちていた)という背景があったり ↩

3. 作問は僕じゃないですが、それはそうとしてもっと耐えると思っていたので ↩

4. これが発覚したのが前日の夜中で打てる手がそれぐらいしかなかった ↩

5. 不備の言い訳というつもりは全くないです。不備は自分が悪い。 ↩

6. 自分は特に何も思っていなかったが、言われてみれば本当にその通りでございます ↩

7. 準備段階で$O(N^2)$が提案されていた ↩

8. 誰が気付くんだよこれ ↩

9. 実際のところは、割と落ちていた印象がある？これが理由かはわかりませんが... ↩