CPCTF2025 作問者writeup Naru820

はじめに

お久しぶりでございます。Naru820と申す者です。以後お見知りおきする必要はございません。皆さまの脳のリソースを無駄にするだけですので。

さて、この度はCPCTF2025に参加していただき、誠にありがとうございました！新歓ブログリレーで個人的にCPCTFの宣伝用に書いたブログでも同じようなことを言いましたが、やっぱり問題を多くの人に見てもらって、しかも解いてもらえるのは、本当に作問する側としてはこれ以上なくうれしいことです。本当にありがとうございます。

本編

問題準備が他の人になっていたり、そもそも出題されずに没になった問題もあるのですが、CPCTFの準備期間中に、自分が提案した問題を全部書いておこうと思います。問題の詳しい解説は、PPC作問陣writeupやyukicoderのコンテスト上などに書いてあるので、この記事では、出題された背景とか、自分が何を考えてこの問題を作ったか、そしてコンテスト中に順位表や皆さんの提出を眺めながら思ったことなどを書いていきたいと思います。

問題文も、私が出した原案の時の物をそのまま引っ張ってきました。なので、yukicoderなどで実際に出題されている問題文とは異なる場合があります。ご注意ください。

PPC

Like CPCTF?

英大文字からなる文字列 $S$ がCPCTF的であるとは、 $S$ の長さが5でかつ $S_{i} = S_{j}$ と $i = j \lor {i, j} = {1, 3}$ とが同値であることをいいます。( $S_{i}$ は $S$ の $i$ 文字目を表します。)すなわち、 $1$ 文字目と $3$ 文字目のみが等しく、それ以外の文字がすべて違うような長さ5の文字列のことをいいます。例えば、 $A B A C D$ はCPCTF的ですが、 $A B A BC$ はCPCTF的ではありません。
長さ $N$ の英大文字からなる文字列 $S$ が与えられます。 $S$ の連続とは限らない部分文字列であって、CPCTF的であるようなものはいくつありますか?ただし、部分文字列は取り出した部分が違うならば文字列として同じでも別のものとして数えます。

$1 \leq N \leq 30$
$S$ は長さ $N$ の英大文字からなる文字列

全探索枠です。新入生向けに、forとif文が使えれば、解けるような問題を作りました。それ以外特にいうことはないです。解説にも書いた通り、O(σ^2N)(ここで、σはアルファベットの文字数で、今回はσ=26です。)でも解ける(前計算のもと、3文字目の文字の場所を全て試す)はずです。包除原理とかを頑張ればσを一個落とせる気もしますが考えるのが面倒になってやめました。結局定数倍重くて速度的には変わらなさそうだし。

実際の提出を見ていると、まあまあREとかを踏んでいる人が多くて、forとifだけでも意外に一発で通すのは朝飯前というわけではないんだと思いました。プログラミングは人間には難しすぎるので仕方がないですね。

Decrement or Mod Game

AliceとBobの二人はそれぞれ正の整数 $A, B$ を持っています。二人がこの数でゲームをします。
二人はAliceを先行として、どちらかの持つ数が0になるまで交互に以下のどちらかの操作を行います。

自分の持つ数を1減らす。
自分の持つ数を相手の持つ数で割ったあまりに置き換える。この操作は、相手の持つ数が自分の持つ数以下の時のみ行える。

先に自分の持つ数が0になった方が勝ちです。二人が最適な行動をするとき、どちらが勝ちますか？なお、このゲームは必ず決着がつくことが証明できます。

$1 \leq A, B \leq 1 0^{18}$

簡単算数パズル枠です。昔のARC-A 300っぽい問題にしようと思って作りました。

コンテスト中に順位表や提出を眺めて、上位勢がバンバンWAを出しているのをずっとニヤニヤしながら見ていました。実験をしなくても、最初から理詰めで解けるかなとも思ったのですが、実験をちゃんとしていないコードがことごとく落ちて、実験をちゃんとしているコードが通っているのを見て、やっぱり冷静に条件を整理するのは大変なんだなあと思いました。(自分がはじめ作って自分で解いた時も、実験して答えが分かったうえで理詰めで考えました。ちなみに私も最初想定解を実装した時にtypoして一か所a,bを逆にしていました。バカすぎ。)

Swap

長さが $N$ の数列 $A, B$ と正の整数 $K$ が与えられます。
あなたは、以下の操作を好きなだけ繰り返すことができます。

$A_{i}$ と、 $A_{i + K}$ を入れ替える。

$A$ を $B$ に一致させることができるか判定して下さい。

$1 \leq N \leq 2 \times 1 0^{5}$
$1 \leq K \leq N - 1$
$1 \leq A_{i}, B_{i} \leq 1 0^{9}$

出題する問題を選定しているときに、Lv.2が足りない！となって急遽2分ぐらいで作った問題です。急いで作ったので裏取りをしなかった結果、なんと後にABC254Cにほとんど同じ問題があることが発覚し、改題されて出題されました。んな昔のC問題なんて覚えてねえよ涙

これはそんなに詰まってる人がいなさそうでしたね。やっぱりちょっと罠があるけど簡単みたいな問題じゃなくて典型のほうがみんなできるんだなあという気持ちになりました。

Toll Optimization

$N$ 個の町と、 $M$ 本の橋があります。 $i$ 本目の橋は、町 $u_{i}$ と町 $v_{i}$ を結ぶ橋で、どちらにも渡ることができ、渡るのに $C_{i}$ 円かかります。
あなたは、 $K$ 枚のクーポンを持っており、橋を渡るときにクーポンを1枚使うと、橋を渡る料金を $0$ 円にすることができます。
あなたは、現在町 $1$ におり、町 $N$ に行きたいです。クーポンを適切に使用したときに、あなたが支払うべき料金の最小値を求めてください。

$1 \leq N, M \leq 1 0^{5}$
$1 \leq K \leq 3$
$1 \leq u_{i} < v_{i} \leq N$
$1 \leq C_{i} \leq 1 0^{9}$
$i \neq = j \Rightarrow (u_{i}, v_{i}) \neq = (u_{j}, v_{j})$

簡単枠が足りなくて急遽作った問題part2です。典型すぎるというご指摘は受け付けておりません。でも絶対どっかにありそうだよな～と思ったら、ABCで大体一緒の問題が出てきちゃった。でも真に新入生を意識するなら、昔のABCみたいにこのレベルの難易度の問題がボス一歩手前ぐらいでいいのかもしれません。もっと簡単でもいいのかもしれない。

まあ、ある程度強い人なら、ドドドドドド典型ですし特に詰まることはなく解けるかな～と思ったのですが、提出を見ていると、クーポンをK枚使っている場合のみ考えて、WAを出している人が青や暖色コーダーにもちょこちょこいたのが印象的です。もしかしたら、yukicoderがWAによるペナルティがないしレートもかかっていないからAtcoderとかと比べて適当に出してるのかな？と思いました。

0 → 1

$0$ と $1$ からなる文字列 $X$ が以下の条件を満たすとき、 $X$ をよい文字列であると呼びます。

どのような $X$ の長さ2以上の連続部分文字列も、その文字列に含まれる $0$ の個数がその文字列に含まれる $1$ の個数を超えない。

例えば、 $101$ はよい文字列です。また、 $00111$ はよい文字列ではありません。
$0$ と $1$ からなる長さ $N$ の文字列 $S$ が与えられます。あなたは一回の操作で、 $S$ に含まれる $0$ を1つ選び、 $1$ に変更することができます。 $S$ をよい文字列にするために必要な最小の操作回数を求めてください。

$1 \leq N \leq 2 \times 1 0^{5}$
$S$ は $0$ と $1$ のみからなる長さ $N$ の文字列

traPが初心者向けに開く0→1講習会が元ネタです。0を1にできたらなんでもよかったので、問題を考えるのが逆に大変でした。結局AGC060Aの弱体化問題みたいになってしまいました。

コンテスト中はThe Farthest point を飛ばしてかなり通されているようでした。やっぱり木DPはだるいからこうなるかな～と思っていたので、想定通りでよかったです。(問題を入れ替えればよかったんじゃないんですか？)あと、一応想定解はDPだったのですが、おまけのところに書いた貪欲で通している人がかなり多かったのも印象的でした。

Increment or Multiply

整数 $A$ が与えられます。 $N \geq X$ を満たす正の整数 $N, X$ に対して、 $f (N, X)$ を以下の問題の答えとします。

変数 $C$ があり、初め $C = X$ です。あなたは $1$ 回の操作で $C$ に $1$ を足すか、 $A$ を掛けることができます。 $C = N$ とするために必要な最小の操作回数を求めてください。

$\sum_{i = 1}^{N} f (N, i)$ を求めてください。ただし、答えは非常に大きくなる場合があるので $998244353$ で割ったあまりを求めてください。テストケースは全部で $T$ ケース与えられます。

$1 \leq T \leq 2 \times 1 0^{5}$
$1 \leq N \leq 1 0^{18}$
$1 \leq A \leq 1 0^{18}$

典型的な問題を何か作ろうと思って作った枠です。元ネタは、ABC188Fを考えたときに僕が生やした嘘解法です。-1するの、やめてね。地味に、Decrement or Mod Gameと対照的な問題名になっているのが好き。(ちなみに先にできたのはDecrement or Mod Game。)

コンテストの結果を見ると、Reversible Tileとめちゃめちゃ逆転していましたね。並び順を決める会議の時に、私はこの問題をかなり易しいと評価していたのでLv.4の下のほうに置いていたのですが、他の人がいや難しいと言っていたので真ん中ぐらいに置いたのですが、ほらだから言ったのに～とこっそり思っています。

初め私が想定解を実装したときにオーバーフローした(バカ)ので、結構みんなオーバーフローで落ちるかなと思ったら、思ったよりはWAが出ていませんでした。まあ多分ここまで来るような人はある程度強いので、多分そこらへんへの耐性もあるのでしょう。というよりも、みんな私が後から別解として思いついた漸化式による解法で解いているようです。確かに、Testerもそうやって解いていたので何も前提情報がないところから解くと漸化式のほうが思いつきやすいのかもしれない。

あと、とある日本の最上位勢の方にコード内のコメントで「なんだこれは　スタートが動いて目的は変わらない」と書かれていたのが印象的でした。あんまりこういう設定の問題を見たことがなかったのでしょうか。相当な数問題を解いている方なので、物珍しいと思っていただけたのならうれしいですね。簡単すぎるだろみたいな意味かもしれないですが。

Lower Nim

この問題は インタラクティブな問題 (あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題)です。
$N$ 個の石の山があり、始め $i$ 個目の山には $A_{i}$ 個の石があります。あなたとジャッジは交互に以下の操作を行えます。

(操作) 石の山を一つ選び、そこから石を1つ以上取り除く。ただし、直前に相手が取り除いた石の個数より多く取り除いてはいけない。すなわち、ゲームが $M$ 回石を取り除かれて終了し、 $i (1 \leq i \leq M)$ 回目に取り除かれた石が $S_{i}$ 個の時、 $S_{1} \geq S_{2} \geq ... \geq S_{M} \geq 1$ でなければならない。

操作が行えなくなった方が負けです。与えられる石の山を見てからあなたは先手か後手どちらでプレイするかを選ぶことができます。このゲームでジャッジに勝利してください。

$1 \leq N \leq 2 \times 1 0^{5}$
$1 \leq \sum_{i = 1}^{N} A_{i} \leq 2 \times 1 0^{5}$
石の山はプログラムとジャッジの対話が開始する前に決定されている。

ここら辺から、見た目から作った問題になります。最初はインタラクティブじゃなかったので大ギャグ(必勝判定条件が普通のNimと同じ)だったのですが、Nzt3さんがインタラクティブにすることを提案して問題が形になりました。今回出した問題の中で一番お気に入り。(ちなみに2番目はDecrement or Mod Game)

…だったのですが、直前になって既出であることが判明して血涙を流しながらまあインタラクティブだし…と言って出しました。くやしい。

答えが分かれば、実装はまあ長いけれども難しくはないかなと思っていたのですが、実際の提出や統計情報を見ていると、実装で詰まった人もかなりいたようです。3,4回ペナを出している人もかなり多かったですし、なんと最多ペナ数は31回でした。多分提出デバッグだとは思いますが。

後述するように、実装でなるべく詰まらせないような問題作りを心がけていたので、申し訳ない...

Median of Medians of division

長さ $N$ の整数列 $A = (A_{1}, A_{2}, ..., A_{N})$ が与えられます。以下の $Q$ 個のクエリに答えてください。

$i$ 番目のクエリでは、 $L_{i} \leq R_{i}$ を満たす整数 $L_{i}, R_{i}$ が与えられるので、 $B = (A_{L_{i}}, A_{L_{i} + 1}, ..., A_{R_{i}})$ に対して以下の問題を解いてください。

$B$ を $1$ 個以上の非空な連続部分列に分割し、分割された列全てについて、その列の中央値を計算した後、さらにそれらの中央値を計算します。分割する方法は全部で $2^{R_{i} - L_{i}}$ 通りありますが、適切に分割したときにこの値は最小でいくつになるでしょうか？

ただし、長さ $L$ の整数列 $X$ の中央値とは、 $X$ をソートした列を $X^{'}$ としたとき、 $X^{'}$ の $⌊ \frac{L + 1}{2} ⌋$ 番目の要素のことをいいます。
$1 \leq N, Q \leq 2 \times 1 0^{5}$
$1 \leq L_{i} \leq R_{i} \leq N$
$1 \leq A_{i} \leq 1 0^{9}$

Lv.5一問目です。実はこの問題が一番最後にできました。(4/12にissueが立ちました)

これは見た目じゃなくて解法から作りました。コンテストの問題を眺めていたら♰二分探索♰の問題がない!?と思って、流石に一問ぐらい出すかと思ったのが始まりでした。二分探索と言えば中央値だよなあと思うと、median of mediansがどうしても頭から離れなくなり、この問題ができました。でも結局想定解は二分探索じゃなくなりました笑。今の原案みたいに更新クエリがなかったら、多分並列二分探索で解けるはずですが、本番では更新クエリありバージョンの問題なので並列二分探索もできません。たぶん。

ちなみに最初はO(N^2+Q(log N)^2) (Aの要素しか答えになりえないので、それらすべてについてにぶたんができるように01列に置き換える前処理をしたあと、各クエリでにぶたんをし、判定問題をsegment treeで解く脳筋解法)で提案したのですが、hotman78,ponjuice様が今の想定解を考え付き、無事今の制約に引き上げられました。ありがとうございました。あのクソ長Editorialは私が書いたのですが死ぬほど大変でした(コンテストが始まる30分ぐらい前にようやく完成した)。

無駄にlogを付けたりなどの、想定より計算量が悪い解法を落としつつ、pypyの想定解法はある程度余裕をもって通すように頑張ってパラメータなどを調整したつもりでしたが、定数倍を頑張ると O(Q(log N)^2)がギリギリ通るみたいです。うーーん、まあ仕方ないか...あと、普通に答えが間違っていないだろうかとドキドキしていたので、potatoさんが結構すぐ通しているのを見てそんなすぐ解ける問題だっけ???と思いつつ安心しました。

あと本当にこれはどうでもいいのですが、この問題名を略すとMMDになってMikuMikuDanceと同じになるな～と思いました。でも他の人に話してもあまり共感を得られませんでした。悲しい。

Reversible tile

$N$ 枚の表裏が区別できるタイルがあり、タイル $1, 2, ..., N$ と呼びます。はじめタイルは全て表向きです。
これから $M$ 回以下の操作を行います。

$1 \leq L \leq R \leq N$ を満たす正の整数 $L, R$ を選び、タイル $i (L \leq i \leq R)$ を全てひっくり返す。

操作列は $(\frac{N ( N + 1 )}{2})^{M}$ 通りありますが、そのうち、タイルの状態が $A_{1}, A_{2}, ..., A_{N}$ になっているような操作列の数を $998244353$ で割ったあまりを求めてください。ここで、 $A_{i} = 1$ の時タイル $i$ が表、 $A_{i} = 0$ の時、タイル $i$ が裏であることを表します。

$1 \leq N, M \leq 2000$

これ以降の問題は私は原案のみ出して、他の人に主に準備をしてもらった問題になります。kenken,Nzt3,ponjuice様に大土下座。ちなみに解説読むまで自分はこの問題がO(NM)で解けませんでした。バカすぎる。普通に中度典型(典型90に出てた)なのに…ちなみに、FPSを使うとO(N^2 + N log N log M) でも解けるらしいです。すごいですね。

コンテストの提出を見ていると、おそらく初心者は切れ目を考える典型を知らなくて解けない一方で、その典型を知っている上位陣にとっては休憩ポイントになっていたようです。それはそう。あと、chatgpt o4-mini-high でも解ける様です。まあ、でしょうね。

あと、なんかこの問題、ちょっと工夫すれば通りますが、何も考えずにACLのmodint使うとなぜかTLEになるんですよね。なんでかはよくわかりません。多分除算の処理が遅いのか？これは知ってて出したのですが、まああんまりいい気持ちはしないで出していました。ちょっと高度典型問すぎるし、これは出さないほうがよかったかな...と少し思っています。

Inversion

$(1, 2, ..., N)$ の順列 $P$ のスコア $f (P)$ を以下のどちらかの操作を好きなだけ行って出来うる順列の数とします。

$P$ を $P$ の逆順列、すなわちすべての $i = 1, 2, ..., N$ に対して $P_{R_{i}} = i$ を満たす $(1, 2, ..., N)$ の順列 $R$ で置き換える。
$P$ を $P$ を逆順にした順列、すなわちすべての $i = 1, 2, ..., N$ に対して $R_{i} = P_{N - i + 1}$ を満たす $(1, 2, ..., N)$ の順列 $R$ で置き換える。

$(1, 2, ..., N)$ の順列 $P$ は全部で $N!$ 通りありますが、そのすべてについての $f (P)$ の総和を998244353で割ったあまりを求めてください。

テストケースは全部で $T$ ケースあります。

$1 \leq T \leq 1 0^{6}$
$1 \leq N \leq 1 0^{7}$

今回のコンテストのボス問題でした。もともと、f(P)を求めさせるつもりだったのですが、実験してみたら2か4か8しかなくて、愚直に求めればいいだけだったので、じゃあ数え上げにするか～として適当に数え上げにしたら、天才kenken様がなんと数え上げてしまいました。すげ～。問題選定の時にみんなこれ解けるのすごいと言っていました。私は全然何もしてないんですけど、ちょっといい気分になりました。

コンテスト中の提出を見ていると、M,N = 1の場合に答えが0になるのを1と出力している場合が非常に多かったです。実は、writerのkenkenさんが初めに実装した解法もこのミスをしているのを、コンテスト直前にponjuiceさんが発見し急遽ケースを追加したので、本当にこのミスが見つかってよかったです。危うく問題不備になるところでした。あと、OEISに場合分けのパターンがいくつかあることは知ってたんですけど、全部あるっぽくて流石にびっくりしました。

Bucket Brigade

長さ $N$ の数列 $A = (A_{1}, A_{2}, ..., A_{N})$ が与えられます。この数列に対して以下の操作を $K$ 回行います。

$A_{i} > 0$ を満たす $i (1 \leq i \leq N)$ を一つ選ぶ。 $A_{i}$ に $- 1$ を、 $A_{i + 1}$ に $1$ を足す。ここで、 $A_{N + 1}$ は $A_{1}$ のことを表す。

操作によって得られる数列としてあり得るものの数を $998244353$ で割ったあまりを求めてください。

ここから先は没問題になります。途中で作問会があったので、その時に作った問題です。解けたと思って出したら、大嘘を書いていました。(iに操作した回数の階差数列がなぜかAと1対1対応すると思っており、これを良い感じに整理すると分割数の要領でFPSを用いて計算できる...と、そう思っていた時期が私にもありました。)結局解法が思いつかず、改題しても面白い問題にならなかったため没となりました。誰か答えわかったら書いといてください。

Stalin

長さ $N$ の整数列 $X = (X_{1}, X_{2}, ..., X_{N})$ に対して、 $X$ のスコア $f (X_{1}, X_{2}, ..., X_{N})$ を、以下で定義します。ここで、 $δ (i, j)$ はクロネッカーのデルタ関数です。

$i = 1 \sum N X_{i} δ (X_{i}, j \leq i max X_{j})$

長さ $N$ の整数列 $A$ が与えられます。 $(1, 2, ..., N)$ の順列 $P$ は $N!$ 個ありますが、その全てについての $f (A_{P_{1}}, A_{P_{2}}, ..., A_{P_{N}})$ の総和を求めてください。ただし、答えは非常に大きくなることがあるので、 $998244353$ で割った余りを出力してください。

$1 \leq N \leq 2 \times 1 0^{5}$
$1 \leq A_{i} \leq 1 0^{18}$

この問題は、Increment or Multiplyと似た問題だったので、天秤にかけられて(というより自分が天秤にかけて)没となりました。ちなみに問題名は、問題文で定義されるスコアが、その数列をスターリンソートして残った要素の総和であるところからきています。想定解法がゴリゴリ数学の式変形だったのでまあInc or Mulにしてよかったかな...

Delayed Airplane

21XX年、東京科学大学の敷地内には $N$ 個の空港があり、順に空港 $1, 2, ..., N$ と呼ばれています。今、この空港の間を結ぶ便が $M$ 本予定されており、 $i$ 番目の便は時刻 $S_{i}$ に空港 $U_{i}$ を出発し、時刻 $S_{i} + T_{i}$ に空港 $V_{i}$ に到着する予定です。しかし、今日は天候が悪く、飛行機は遅延する可能性があります。具体的には、 $i$ 番目の便は出発が $d_{i}$ だけ遅延する可能性があります。ここで、出発が遅れても移動するのにかかる時間は変わらないものとします。
Naru820君は、時刻 $0$ に空港 $1$ にいます。ここからNaru820君が空港 $i (2 \leq i \leq N)$ にたどり着けるかどうか判定し、たどり着ける場合は、たどり着くまでにかかる時間の最小値が最大になるような遅延のしかたをした時のたどり着くまでにかかる時間の最小値を求めてください。より正確には、以下で定義される値 $g (i)$ を求めてください。

$j$ 番目の便の遅延が $e_{j}$ だった時に空港 $i$ にたどり着くのにかかる時間の最小値を $f (i, e)$ と表します。ただし、空港 $i$ に辿りつけない場合は $f (i, e) = \infty$ と定めます。
この時、 $g (i) = e \in \prod_{j = 1}^{M} [0, d_{j}] max f (i, e)$ です。

$1 \leq N, M \leq 2 \times 1 0^{5}$
$1 \leq U_{i}, V_{i} \leq N$
$1 \leq S_{i}, T_{i}, d_{i} \leq 1 0^{9}$

問題として何かクソというわけではないんですが、没になった理由は前にtraQ(部内のコミュニケーションツール)でぽろっと話したことがある問題だからです。改題して出そうかなーとも思ったのですがそこまでやる体力がなく没となりました。

Combination GCD

正の整数 $N$ が与えられます。 $N - 1$ 個の整数 $\{} _ {N} \mathrm{C} _ {j} (j = 1,2,\cdots ,N - 1)$ の最大公約数、
$\gcd( \{}_ {N}\mathrm{C} _ {1}, \{}_ {N}\mathrm{C} _ {2}, \cdots ,\{}_ {N}\mathrm{C} _ {N - 1})$ を求めてください。
テストケースは全部で $T$ 個あります。

$2 \leq N \leq 1 0^{6}$
$1 \leq T \leq 1 0^{5}$

TeXがバグるんだけど、直し方がわからんのでこのままで(おい)。実験エスパーする問題だったので没に。ちなみに答えはNが素べきのときその素数、そうでないとき1です。元ネタは、高校時代に友達から出された問題です。

Replace XOR

長さ $N$ の数列 $A = (A_{1}, A_{2}, ..., A_{N})$ , $B = (B_{1}, B_{2}, ..., B_{N})$ が与えられます。以下の操作を好きなだけ繰り返すことでAをBに一致させられるか判定してください。

(操作)整数 $i, j (1 \leq i, j \leq N)$ を選ぶ。 $A_{i}, A_{j}$ を $A_{i} \oplus A_{j}$ で置き換える。

ここから先は、解けていないので没となった、真の没問です。もし解けたらコメントにでも答えを書いといてください。列を列に一致させられるか判定する問題が作りたかったのですが、普通に無理だった。なんかよさそうな性質があるっぽいんだけどな...

Unique Width Swap

$(1, 2, ..., N)$ の順列 $P$ があります。また、黒板に $1$ から $N - 1$ までの整数が一つずつ書かれています。あなたは以下の操作をちょうど $N - 1$ 回行えます。
・黒板に書かれている整数を一つ選ぶ。選んだ整数を $i$ として、 $1 \leq j \leq N - i$ を満たす整数 $j$ も選ぶ。 $P_{j}, P_{i + j}$ を入れ替えて、黒板から $i$ を消す。
$P$ を昇順に並び替えられるか判定し、可能な場合は操作列も一つ示してください。

解けたと思ったら解けていませんでしたpart2(おい) j = 1の場合を解いていました。作者が問題文を誤読するなよ。

CTF

PPC分野の問題が決まって、くぅ～疲れましたwこれにて僕のCPCTF作問は完結です！としようと思ったのですが、CTFの問題が足りないということで急遽作りました。CTFは数回しかやったことがないガチ初心者なので、クオリティ低くて、ごめん...

Heroic Code(Crypto)

Pmttw ivl bpivs gwc nwz rwqvqvo bpm KXKBN! Bpm ntio qa KXKBN{Bpm ewzl lqkbibwz qa kwwt,qav'b qb?}

問題文からもわかると思いますが、シーザー暗号です。去年とかはこの枠は換字式暗号だったのですが、普通に頻度分析とかをするの、Newbieなのにめんどくさくないですか？ということでシーザー暗号にしました。

コンテストでは、なぜかSanity check(問題文にフラグが書いてある)よりも通されました。どうして？？？？？？？？？？？？？？？？？？？？？

Painting Break(misc)

psdファイルが与えられるので、フラグを探しましょうという問題です。普通のCTFだと画像とかにフラグやファイルとかを埋め込んだりするのですが、そこはCTF初心者の作った問題、そんなCTFっぽいことはしないで、レイヤーの設定をいじれば解けます。少しmiscすぎたかもしれません。

コンテストでは、他のLv.2に比べて圧倒的に通されませんでした。割とLv.2にしても簡単かな～と思っていたのですが、ヒント2まで開けて通している人がかなり多いことを見ると、ペイントソフトに始めて触れた人が結構多かったのかもしれません。

Bench(OSINT)

単純に、写真から場所を推定する問題です。初手は簡単ですが詳細を詰めるのがきついかもしれません。

あと、フラグを緯度経度小数点以下第5位で切り捨てるように指定したのですが、こちらの想定した場所との微妙なずれで落ちている人(google mapで解けるのですが、一クリックの移動で答えがずれます)が結構いたようです。申し訳ない...一応誤答が100回までできるので、近傍探索するだろうと思ってフラグを変えることはしなかったのですが、もしかしたら小数点以下第4位で切り捨てるようにした方がよかったかもしれません。

ちなみにこの場所は、現在アニメが絶賛大放送中のSummer Pocketsの原作ゲームでしろはがクレープを食べていたところです。(角度全然違うけど。)

皆さんもとりあえずこのwriteupを読み終わったらサマポケのアニメを見ましょう。

全体的な感想(PPC)

終わってから見ると、なんだかんだ結構問題を作ったんだなーと思います。まあ原案だけぶん投げて解かれたから出したのもありましたが。結局、今回のCPCTF2025で出題されたPPC分野の問題17問のうち、10問が私原案の問題ということになりました。皆さん楽しんでいただけたでしょうか？まあここに書いてある問題はある程度解ける見込みがあって提案したものなので実際はこの裏に多数の自明or不可能問題が眠っていますが...

前回のCPCTF2024には、当時AtCoder緑だった私も、参加者として参加していたのですが、まあEasy問題が全然解けないのなんの。結局easyはCPC to Fと、balanced choice しか解けませんでした。(前回までのCPCTFでは、難易度がNewbie,Easy,Medium,Hardと分かれていました。)

この反省を踏まえつつ、私が今回作問の際に意識したのは、Lv.3までの問題は、ある程度の経験者(緑色以降)なら解けるような難易度にするということ、高度典型はなるべく出さず、考察重視の問題にするということ、そして実装がなるべく簡単な問題にするということでした。

まず1つ目の項目について。普通に、緑コーダーってある程度の経験者のはずなんですが、その緑コーダーが全然解けない問題が初心者向けコンテストのeasyにおいてあったらダメじゃないですか？私はダメだと思います。なので、緑,水コーダーなら絶対解けるべきと思われる問題をLv.3までは配置したつもりでした。(私原案の問題の話です。木DPはちょっと緑コーダーにはむずいかも。)

次に、2つ目の項目の話です。高度典型がどこからを指すかはあいまいな気がしますが...現行ABCのG問題あたりを解くために必要な知識レベルぐらいだと思ってください。普通に、新入生向けコンテストを謳っているのに、解説を開いたら、謎のアルゴリズムが書いてあってこれで解けます！と言われても、huhcatが登場してしまいます。(ダイクストラ法も謎のアルゴリズム？そうですか...)少なくとも、私がLv.4までに配置した問題は、緑、水コーダーが解説を読んでなにこのアルゴリズム？みたいになるものは出していないはずです。

最後に、3つ目の項目の話です。これは人によると思うのですが、私は競技プログラミングの一番楽しい瞬間は、問題を解くアルゴリズムを考え付いた瞬間だと思っています。しかし、アルゴリズムを考え付いていざ実装しようとして、実装で詰まると、もう解けてんだけどな～なんでサンプル通んねえんだよ怒怒怒となってしまいます。で、サンプル通ったと思って出したら落ちるまでがワンセット。競プロerを怒らせる方法です。これは初心者の体験としてあまりよくないと思いました。なので、私のLv.4以下の問題の想定解は、全部素朴？なC++で、およそ2000byte以内で実装できるような問題にしました。というか、Toll Optimization,Lower Nim が1500byteぐらいというだけで、後は大体1000byte以下ですし、なんならToll Optimizationもダイクストラのライブラリが長いだけで本質部分は多分500byteぐらいです。少し長めの実装を要求している問題も、やることは明快で実装する方針に迷うような問題はあんまりないと思います。(強いて言えばToll Optimization,Lower Nimが面倒なぐらいか?)と、そう思っていました。ごめんなさい！まあでも詰まってたのが初心者じゃなかったから、いいか！笑Lv.5も、考察は難しいですが、実装はLv.4が解ける人なら多分できる程度の難易度に抑えられていると思います。

ただ後悔ももちろんあります。正直、真の初心者-friendlyにはできていないよな～というのはずっと思っていました。東京科学大学に入学できる地頭を持っていて、なおかつ初心者にも関わらず、入学早々こんな謎のコンテストに出ようと、少しでも思うような人間ということを加味しても、完全初心者の人がおそらく解ける問題はかなり少ないでしょう。多分私原案の問題だと、未経験者はLike CPCTF?,Swap,0→1,Decrement or Mod Gameぐらいしか解けなかったんじゃないかな...Toll Optimizationは、まあ検索能力があれば解けるかもしれませんが、競技数学などをやっていない限りIncrement or Multiply 以降の難易度の問題を解くのはしんどいと思います。かといって4問ABCの問題を増やしたコンテストにするのも、それはそれで今回かなりの数出てくれた上位勢にとって歯ごたえのないコンテストになってしまうので違うような気がします。(今回も歯ごたえはあったのでしょうか...)どうすればいいんでしょうね。

全体的な感想(CTF)

まあ見たらわかると思うのですが、CTFというよりはPPC分野の問題を主に出していたのでそんなに感想という程の物はないのですが...(そもそも自分がCTF激弱のため、語れることがあまりない)

それはさておき、本当にCTFは作るのが難しい...本当に。本当はCryptoとかのもっと難しい問題を作りたかったのですが、まーじでネタが何も思いつかない＆ちょっと調べたら既出のまあ多いこと多いこと。発狂ものです。Cryptoのメインwriterのkenkenさんは直前までずっと発狂していました。ちなみに他のCTFのwriterも発狂していました。どうしたらいいんでしょうね。

というか、CTFはPPC以上に初心者-friendlyにするのが難しそうです。例えばshellなんて、Unixがある程度でも使えないとお話にならない分野ですが、この大スマホ時代、大学入学時にPCをある程度まともに触ったことがある人すら少数派(情報理工学院でもです。ビビった。)なのに、cat,grepやcd,ls程度のコマンドが使える新入生は果たして何％いるのでしょうか。まあかくいう私も新入生の時、Unixの使い方が全然わからなくてCTFはOSINTばっかり解いていました。別に今でも真に何もわかりませんが。

Webはまあ開発の経験があればなんとかなるかもしれませんが、まあそもそも開発の経験がある人は少ないでしょうし、Cryptoも数学ができないやつは帰れと言われますし、PwnもRevもforensicsも初心者にとってはもう終わりだ...って感じですし、なかなか難しいところですね。

おわりに

来年はこんなには問題は出さないかな...今回のCPCTFに出てくれた25Bの皆さんが、きっと来年は最強になっていて、無限問作ってくれることでしょう。もし私が問題を出すにしても高難易度の問題を1,2問出すぐらいにしたいですね、というか多分それぐらいしかできません。実はいろいろ考えた結果このCPCTFを機に、私はいったん競技プログラミングを休止することにしました。なのでまあ最後ぐらい頑張るか～という気持ちで、今回準備を頑張れた節があります。(それでも他の人のほうが頑張ってたけどね...)でも自分のアルゴリズム人生(2年半ぐらい?意外に短いね)にいったん終止符を打つ仕事として、このコンテストに関わることができて満足です。~~なおこれからは大学でアルゴリズムを習うようですが。数理・計算科学系最高!~~

まあでも本当に本当に大変でした...というか、問題を作るよりも問題をコンテストで開催できるように準備するのがこれほどまでに面倒なことだとは思いもしませんでした。やっぱり自分でやってみないと人の苦労はわからないものですね...これでも、作問および問題準備以外の運営業務はやっていないので、運営の中枢にいた人はもっともっと大変そうでした。マジで。

でも、本当にめちゃめちゃ大変だったのですが、それ以上に、コンテストが始まってからは本当に楽しかったです。やっぱり自分の作った問題を解いてもらえるのは楽しいですね。来年もし実力があって余裕があったらまたちゃんと問題を作るかもしれません。

何はともあれ、CPCTF2025 および yukicoder上のコンテストに参加してくださったみなさま方には感謝してもしきれません。それでは、来年のCPCTF2026でまたお会いしましょう。

嘘です。多分今度皆様に会うのは2025夏のブログリレーです。では。