この記事は新歓ブログリレー2026 50日目の記事です

はじめに

どうも、25Bのn3と申します。
先日行われたCPCTF2026において、PPCを3題(原案で関わったのは5題)出題しました。作問時に考えたことなどをここに記しておこうと思います。せっかくなので没になった案も抜粋して紹介します。

Sign up for traP [Lv1, 星1.5]

問題文

No.3497 Sign up for traP - yukicoder

競技プログラミングの練習サイト

yukicoder

コメント

原案担当です。writerは @alyth_sol です。

この問題を作るために、traQの内部実装を見てきました。ログイン時の処理で、

• traQid は1文字以上32文字以下の、英大文字(A~Z)、英小文字(a~z)、アラビア数字(0~9)、アンダースコア(_)、ハイフン(-)、によって構成される
• password は10文字以上32文字以下の、ASCIIコードにて表現可能な文字列である

というバリデーションコードがあったので、そのまま問題にしました。
しかし、「、ASCIIコードにて表現可能な文字列である」みたいな表現だと、日本語文字が入ってくることがあるのかとかが曖昧であるので、問題では「文字列 $S$ は ASCII code で 33~126 と表現される文字から構成される。特に、半角スペースを含まない。」という形になりました。

結果

B問題とsolved数が逆転しちゃった...
まあ文字列の判定で意外と大変...そうか？

Brackets Stack Query 2 [Lv2, 星2]

問題文

No.3503 Brackets Stack Query 2 - yukicoder

競技プログラミングの練習サイト

yukicoder

コメント

原案担当 兼 writer です。

集合の内包表記 $\{x|P(x)\}$ のような表記から、棒付き括弧列というアイデアを思いつきました。
この問題を思いついた当時は、通常の括弧列の判定のようにネストの深さを表す整数を持って実装しようとして迷走しました。その結果、「永続stackを使えば解ける！」という結論になっていたのですが、作問者仲間の @t-oka に出題してみたら、「スタックを使って判定しつつ差分を別のスタックに保存すればいいのでは？」と指摘されました。変にデータ構造に頼りすぎるのはよくないですね...

以下は独り言です。
こういう、スタックを使ってその文字列が条件を満たすかどうかを判定できるものは、プッシュダウンオートマトンとかの概念と密接に関わっています。そもそも「括弧列の深さを持つ」というのは、「スタックに(が何個積まれているか」を保存しているものであり、つまりスタックの状態と等価なものを持っているということです。スタックと等価な情報を持つから、通常の括弧列はセグ木に乗せれたり...と考えることができます。つまり、通常の括弧列で「ネストの深さを持つ」というのは「プッシュダウンオートマトンのスタックの状態を持つ」と考えることができ、逆に言えばその状態が一次元的な整数で常に表せる訳ではない...だから最初に迷走した「深さを表す数値を持つ」という方針は良くなかったんですね。直接陽にスタックの状態を持って差分更新すればよかったわけです。この問題を作問することで、自分の中での理解が深まった気がします。

結果

E,F問題とsolved数が逆転しちゃった...(2回目)

提出を見ると、ちょこちょこ永続stackを使ってる人がいておもしろいですね。

Sum of Prod of Root [Lv3, 星2.5]

問題文

No.3505 Sum of Prod of Root - yukicoder

競技プログラミングの練習サイト

yukicoder

コメント

原案担当です。writerは @alyth_sol です。

今回のコンテストの中では、自分の一番のお気に入りです。式の形が好きです。

解法としては、まず $k\ge 2$ の変化点を列挙する + 連続する自然数の和を $O(1)$ で求めることで $O(\sqrt{N})$ で解けます。ここまでは簡単ですね。最初はこれで出していいかな～と思いました。

ここまでは高校数学の内容なので 星2.5 でいいですね。

ですが、頑張れば $O(\sqrt[3]{N})$ に出来そうですよね。
ということで、

$$\sum _{i=0}^{N}i\lfloor \sqrt{i}\rfloor =\sum _{i=1}^{\lfloor \sqrt{n}{\rfloor }^2-1}i\lfloor \sqrt{i}\rfloor +\sum _{i=\lfloor \sqrt{n}{\rfloor }^2}^{n}i\lfloor \sqrt{i}\rfloor =\frac{(\lfloor \sqrt{n}\rfloor -1)\lfloor \sqrt{n}\rfloor (\lfloor \sqrt{n}\rfloor +1)(8\lfloor \sqrt{n}{\rfloor }^2-5\lfloor \sqrt{n}\rfloor -2)}{20}+\frac{\lfloor \sqrt{n}\rfloor (n-\lfloor \sqrt{n}{\rfloor }^2+1)(n+\lfloor \sqrt{n}{\rfloor }^2)}{2}$$

となります。これは高校生でも群数列の分野とかで解けます。結局高校範囲ですね。

よって、この問題は高校数学で解けるので 星2.5 でいいですね。

ってしたら、コンテスト後にXとかで「星2.5じゃないだろ」って意見が見られました。結局難易度の適正は何だったんでしょうか...

ちなみに、没案としては以下のようなものがあります。

$$\sum _{i=1}^N\prod _{k=2}^{\infty }\left(1+\lfloor {\log }_{k}i\rfloor \right)$$

$$\sum _{i=1}^N\left(\prod _{k=1}^{\infty }\lfloor \sqrt[k]{i}\rfloor \right)\left(\prod _{k=2}^{\infty }\left(1+\lfloor {\log }_{k}i\rfloor \right)\right)$$

$$\prod _{i=1}^N\sum _{k=2}^{\infty }\lfloor {\log }_{k}i\rfloor$$

ちなみに上のやつらが $N=10^{18}$ で解けるかは真面目に確認していません。気になる人はやってみてください。

結果

計算ミスやオーバーフローでやらかした人が結構いるかも？

RangeSum RangeUpdate RangeSqrt [Lv4, 星3]

問題文

No.3507 RangeSum RangeUpdate RangeSqrt - yukicoder

競技プログラミングの練習サイト

yukicoder

コメント

原案担当 兼 writer です。

問題としては2番目にお気に入りです。美しい形してますよね。

遅延セグ木に関するお勉強を セグメント木と代数構造の理論 でしたので、せっかくなら何か作ろうと思ってできたものです。なんとなく「RangeSqrt ってできないかな～」って10分ぐらい頑張って悩んだら、「isqrtは繰り返すとすぐに1に収束する」という事実に気づいて、じゃあ「isqrtを何回書けたか」という情報を遅延情報に乗せればいいのではということに気づきました。「遅延情報に合成回数を乗せる」という発想が自力で思い付けたのが嬉しいです。ACLとかに頼らずにちゃんと内部実装を勉強したからこういう非典型なものを乗せれる発想が思いつくのかもしれません。A=0のコーナーケースも、モノイドをいい感じにすれば簡単にできますね。あと Python で通るんですかねこの問題。モノイドが重いから多分難しいかも。

ただ、作問してすぐに「Segment Tree Beats! で殴れない？」と言われて悩みました。当時は分かってなかったのですが、償却解析とかポテンシャルとか勉強して、2月ぐらいにやっと Beats! の本質を理解しました。今になって思えば、Beats! で殴ってくださいと言わんばかりの問題に見えるなぁと思います。Range Update とか、Beats の得意分野ですしね。Beats を殺すためにも、Range Restore (ある範囲を初期化配列に戻す、参考) とか永続化をすれば Beats を殺せるなあとは思ったのですが、そうすると実装が重いとかPythonのTLがヤバいということで断念しました。あと問題の美しさが損なわれちゃうのでね。難しさよりも見た目の美しさの方が大事だと思ってます(思想)。あと Python はBeats を使えばモノイドの要素数が減るから、結局許容すべきかな～になりました。まあ結果的には、結構 Beats! で殴ってる人がそこそこいましたね...まあ K問題 までたどり着く人は Beats! ぐらい当然に使ってるんですかね...
ともかく、isqrt に関する問題を作れたのは満足です。しかも上も合わせて2問も。
コンテスト中に僕の過去ブログを見てくれた人もそれなりにいるのでは...？

参考：【c++】二分探索より速いisqrtを実装する

結果

結果的には、Beats!が意外と使ってる人いて驚きです。そんな典型なんですかね...？
良く言えば、Beatsを使わせる典型問題でも、知らなくても考察で遅延セグ木で解ける応用問題としても捉えられるって言えるんじゃないでしょうか？

OR Mapping [Lv4, 星3]

問題文

No.3508 OR Mapping - yukicoder

競技プログラミングの練習サイト

yukicoder

コメント

原案担当(?) 兼 writer です。
原案担当とはいっても、自分が無向グラフでこの問題を出したら、@Nzt3 さんが「有向グラフでも解けますよ」って指摘して問題になったので、原案としての貢献は半分以下ぐらいです。

なかなかコーナーケースを見抜いていくのがしんどいと思います。というか自分もはじめ実装ミスをしていて、@Naru820 さんに「この入力だと正しく判定できてないんじゃない？」って指摘されて見返したら、想定解にバグが2箇所と、テストケース生成の方に3箇所ぐらいバグがありました、頭が上がりませんね...。ちなみにそれで指摘された入力は、handmade.txt として入れてあるのですが、これのおかげで落とせてる提出がいくつかあります。あと答えは $K$ に依存しないっていうギャグです。$K\le 51$ の $51$ は、作問者仲間に $2^{51}=2251799813685248$ がいるからっていう内輪ネタですね。

結果

本コンテストで一番ペナ数が多い問題になりました。

終わりに

途中から雑な話しか書いてないですが、いかがでしたでしょうか。ちょっと課題で忙しくて...
本当は提出を数えて、解法を数えて統計を取りたかったんですが、僕が直前までブログのタスクをためていたためにできませんでした。ほんますいません...。

ともかく、自分の気に入る問題ができたこと、そして新たな知識の獲得と再確認、この作問経験によっていろいろ学ぶことができました。そして僕の問題を解いていただいた人々に感謝をします。ありがとうございました。

明日の投稿者は@2251799813685248と@lemonです。お楽しみに！