CPCTF2024 ご参加ありがとうございました！
この記事は 2024/04/20 ~ 2024/04/21 にかけて行われた CPCTF2024 の PPC 分野の作問者 (Nzt3,Sotatsu,cho,ponjuice,kenken) による Writeup になります。
今回の CPCTF では PPC 分野は yukicoder 上で開催されました。まだ問題を見ていないという人はこの Writeup を読む前に解いてみてください！
https://yukicoder.me/contests/493

目次

Newbie

• About half
• Compound Word

Easy

• CPC To F
• Old Maid
• Balanced Choice
• Time is money

Medium

• Car Flow
• Power! or +1
• String Swap Battle
• Twisted Lattice

Hard

• Permutation Adjacent Sum
• Bicolor Pyramid
• Strange Clock

Newbie

About half

作問者: @cho

AC者数

問題文

飴が全部で $A+B$ 個あって、Aliceに $A$ 個、Bobに $B$ 個分けました。
AliceとBobは、相手の持っている飴の個数が、自分の持っている飴の個数の $2$ 倍より大きいとき、分け方に文句を言います。
この分け方にAliceもBobも文句を言わないかどうか判定をしてください。

制約

• 入力はすべて整数
• $1\le A,B\le 500$

解法

$2\times A<B$ か $2\times B<A$ のどちらかが成り立つときNoを出力し、それ以外ではYesを出力するとよいです。

作者感想

罠のある簡単枠です。

Compound Word

作問者: @Ponjuice

AC者数

問題文

$N$ 個の文字列 $S_1,S_2,\cdots ,S_N$ が与えられる。
これらの文字列のうち、異なる二つの文字列 $S_i,S_j(i\ne j)$ を選び、$S_i{S}_j$ の順につなげた文字列を $T$ をします。
この時、$T$ としてあり得る文字列は何通りあるか求めてください。

制約

• $N$ は整数
• $2\le N\le 50$
• $S_i$ は英小文字からなる文字列
• $1\le |S_i|\le 100$
• $S_i\ne S_j$ $(i\ne j)$
• ${\sum }_{i=1}^N|S_i|\le 300$

解法

$i,j$ としてありうるものの文字列を全て作りそれが今までにあった文字列と一致するかどうかを調べると良いです。
C++やpythonでいう set という集合型を使用するとより簡潔に実装することができ、高速に動作します。

作者感想

ponjuice って pon と juice をつなげた文字列だなってところから作りました。
$N\le 10^5$ の制約を僕が解けなかったので制約は$N\le 50$ になりました。

Easy

CPC To F

作問者: @Ponjuice

AC者数

問題文

C、P、T、F からなる長さ $N$ の文字列 $S$ が与えられる。
あなたはこの文字列に対して部分文字列 CPC を探し、選んだ CPC を F に変える力を持っている。
あなたは何回でもこの力を使うことができるとき、連続部分文字列 CPCTF を最大で何個含ませることができますか。

制約

• $N$ は整数
• $5\le N\le 5\times 10^5$
• $S$ は長さ $N$ の文字列
• $S$ は C、P、T、F からなる

解法

前から順にCPCTCPCをCPCTFにした時のCPCTFの個数を数えると良いです。
Python で書くとかなり簡潔に答えることができます。

input()
print(input().replace('CPCTCPC','CPCTF').count('CPCTF'))

作者感想

CPCTF っぽい名前の問題名を作りたいなって考えてたらこんな問題になりました。
python の想定解コードを書いたときにここまで短く書けるのかとびっくりしました。

Old Maid

作問者: @Sotatsu

AC者数

問題文

$N$ を正の偶数とします。

$(1,2,\dots N)$ の順列 $p=(p_1,p_2,\dots ,p_N)$ があります。とらお君は、次の手続きによって $(1,2,\dots ,N)$ の順列 $q$ を作ろうとしています。

まず、空の数列 $q$ を用意します。 $p$ が空になるまで、次の操作を繰り返します。

• $p$ の隣り合う $2$ つの要素を選び、 $x,y$ とする。 $x,y$ を $p$ から取り除き (このとき、$p$ は $2$ だけ短くなる)、$x,y$ をこの順のまま $q$ の末尾へ追加する。

$p$ が空になったとき、$q$ は $(1,2,...,N)$ の順列になっています。

辞書順で最小の $q$ を求めてください。

制約

• $N$ は偶数である。
• $2\le N\le 2\times 10^5$
• $(p_1,p_2,\dots ,p_N)$ は $(1,2,\dots ,N)$ の順列である。

解法

操作をそのまま実装すると、最小値を見つける・数列から要素を削除するのにそれぞれ $O(N)$ かかり、それを $N$ 回繰り返すので全体の計算量が $O(N^2)$ になってしまいます。

例えば、最小値取得は、

• std:set を使う ($O(\log N)$)
• 最小値が単調に増えていくことを利用して、最小値がどれだけ増えるかを愚直に求める (ならし $O(1)$)

数列からの要素の削除は、

• 連結リストを使う ($O(1)$)
• $p$ の残っている要素のもともとのindexをstd:setで管理する ($O(\log N)$)

などで実装できます。

よって、全体で $O(N)$ や $O(N\log N)$ でこの問題を解くことができます。

作者感想

ARC080Eの逆です。元の問題より簡単になりました。Young Maidsの公式解説になぜかOld Maidって書いてあるの何でなんですかね。

Balanced Choice

作問者: @Nzt3

AC者数

問題文

$N$個の石があります。 $i$ 番目の石のタイプは $t_i$ であり、重量は $w_i$ 、 価値は $v_i$ です。ここで $t_i$ は $0$ か $1$ のどちらかです。

あなたは合計の重量が $W$ 以下になるようにいくつかの石を選んで箱に入れますが、タイプ $0$ の石の総重量とタイプ $1$ の石の総重量の差が $D$ 以下でなければなりません。

この条件を満たすように石を選ぶとき、価値の総和の最大値を求めてください。

制約

• $1\le N\le 5000$
• $1\le W\le 5000$
• $1\le D\le 5000$
• $1\le w_i\le 5000$
• $1\le v_i\le 5000$
• $t_i\in \{0,1\}$
• 入力は全て整数

解法

タイプ $0$ の石だけで総重量が $x$ となるときの価値の最大値 $v_{0,x}$を $0\le x\le W$ について求めておきます。
これはナップサックDPにより可能です。
どのようにタイプ $0$ の石を選んでも総重量 $x$ が達成できない場合は、 $v_{0,x}=-\inf$ とします。
同様にタイプ $1$ の石だけで総重量が $y$ となるときの価値の最大値 $v_{1,y}$ も $0\le y\le W$ について求めておきます。

最終的な答えを求めるには、タイプ $0$ の石の総重量と タイプ $1$ の石の総重量の組 $(x,y)$ を全探索します。
$|x-y|\le D$ を満たすようなもののうち、 $v_{0,x}+v_{1,y}$ が最大となるようなものを選べば良いです。

作者感想

ナップサックDPは「重さW 以下 で達成できる価値の最大値」で書くことが多いのですが、「ちょうど 重さW」で書く必要のある問題もありますね。問題に応じて使い分けましょう。

Time is money

作問者: @cho

AC者数

問題文

町が $N$ 個あり、 $M$ 本の道で結ばれています。
$i(1\le i\le M)$ 番目の道を使うことで町 $u_i$ と町 $v_i$ を双方向に移動することができます。
また、道を使うのに通行料が $C_i$ 円かかり、この道を使っての移動には $T_i$ 時間かかります。
町 $1$ では働くことができて、 $1$ 時間働くごとに $X$ 円手に入ります。
道を使っての移動と働くこと以外にかかる時間は $0$ とします。

あなたは今町 $1$ にいて、所持金は $0$ 円です。
町 $1$ から町 $N$ までなるべく早く移動するとき、町 $N$ にたどり着くのは最短で何時間後ですか？
ただし、町 $N$ まで移動することができないときは-1を出力してください。

制約

• 入力はすべて整数
• $2\le N\le 2\times 10^5$
• $1\le M\le 2\times 10^5$
• $1\le X\le 2\times 10^5$
• $1\le u_i,v_i\le N(1\le i\le M)$
• $1\le C_i,T_i\le 2\times 10^5(1\le i\le M)$

解法

働いたときの時給を$X$円とします。ある道を通るのに $c$ 円、 $t$ 時間かかっているとき、道のコストを $t\times X+c$ と表すことができます。
このコストは、通るのにかかる時間をその時間だけアルバイトしたときのお金に変換したものになります。
よってこのコストを最小化するようにダイクストラ法をおこない、町 $N$ にたどり着いたときのコストの最小値を $Y$ として、 $Y$ を $X$ で切り上げで割ったものが答えになります。
また、各頂点にたどり着くまでに必要な最短時間と残ったお金の2つの値を持ってダイクストラ法をすることでも正答することができます。

作者感想

問題のタイトルが答えになってるタイプの問題を作ろうとして生まれた問題です。
当初、yukicoderでの難易度を星1.5にしていましたが、ダイクストラ法が想定である問題の難易度として適切ではありませんでした、すいません……。コンテスト後に難易度を星2に更新しました。

Medium

Car Flow

作問者: @Sotatsu

AC者数

問題文

$0$ と $1$ のみからなる長さ $N$ の数列 $A=(A_0,A_1,\dots ,A_{N-1})$ が与えられる。

それぞれが長さ $N$ の数列 $B_0,B_1,B_2\dots$ が次のように定義されます。

• $B_{0,j}=A_j(0\le j<N)$

• $B_{i+1,j}=\{\begin{array}{ll}1& \text{if }(B_{i,(j-1)\text{ mod }N}=1\text{かつ}{B}_{i,j}=0)\text{または}(B_{i,j}=1\text{かつ}{B}_{i,(j+1)\text{ mod }N}=1)\\ 0& \text{それ以外}\end{array}$

以下の極限値が有理数に収束することが証明できるのでそれを求めて、$\text{ mod }998244353$ で出力してください。

${\lim }_{T\to \infty }\frac{{\sum }_{i=0}^{T-1}{B}_{i+1,0}\times (1-B_{i,0})}{T}$

制約

• 入力はすべて整数
• $3\le N\le 2\times 10^5$
• $A_i=0,1(i=0,1,\dots ,N-1)$

解法

$A$ の中の $1$ の個数を $M$ として答えは、

• $M\le N/2$ のとき、 $M/N$
• $M\ge N/2$ のとき、 $(N-M)/N$ です。

作者感想

中学生の頃知った車の渋滞シミュレーションをセルオートマトンでやるやつが元ネタです。一次元セルオートマトンのルール184っていうらしいですね。証明が大変でした。

Power! or +1

作問者: @Nzt3

AC者数

問題文

初め、 $X=1$ です。操作を $0$ 回以上行って $X$ を $N$ の倍数にするとき、コストの総和の最小値を求めてください。

毎回の操作では次の $3$ つの操作のうち $1$ つを選んで行います。

1. $X$ を $X+1$ に置き換える。コストは $A$ かかる。
2. 正整数 $k$ を選択し、 $X$ を $X^k$ で置き換える。コストは $B^k$ かかる。
3. $X$ を $X!$ に置き換える。コストは $C$ かかる。

制約

• $2\le N,A,B,C\le 2\times 10^5$
• 入力は全て整数

解法

$X$ を $N$ で割ったあまりと、 $X$ が $N$ 以上であるかどうかを管理すれば良いです。

$2N$ の状態それぞれについて $X$ をその状態にするためにかかる最小のコストを求めれば良いです。これは各状態を頂点とした最短経路問題を解けば良いです。

操作2で選択する $k$ は小さいものに限られ、操作3でも実際に階乗を計算する必要があるものは $N$ 未満に限られます。

各状態での遷移の数(= 最短経路を求めるグラフの頂点の次数)は $O(\log NA)$ であることがわかったため、ダイクストラ法を用いると全体の最短経路問題の時間計算量は $O(N\log NA\log N)$ となり十分高速です。

作者感想

実はグラフになる問題です。「Power」という感じのめっちゃ強い操作がある問題を生やしたくて生やしました。階乗が冪(power)より強くなってしまったのが残念。

String Swap Battle

作問者: @Nzt3

AC者数

問題文

$N$ 人のプレイヤーがいます。初め、人 $i$ は文字列 $S_i$ を持っています。それぞれのプレイヤーは誰がどのような文字列を持っているかを全て知っています。
次の2つの段階からなるゲームを行います。

段階1

• それぞれのプレイヤーが好きな正整数を宣言する
• 宣言された正整数のうち最小のものを $K$ とする

段階2

• それぞれのプレイヤー $i$ が丁度 $K$ 回次の操作を行う
  • 自分が持っている文字列 $S_i$ の異なる位置の2文字を選択し、入れ替える

最終的に作られた文字列のうち、辞書順で最小の文字列を持っていた人全員が勝ちです。また、勝者は勝者の人数を $X$ として $N+1-X$ 点が得られます。

全員が自身の得点を最大化する戦略をとったとき、全員の得点を求めてください。

制約

• $N\ge 2$
• $2\le |S_i|\le 10^5$
• $\sum |S_i|\le 2\times 10^5$
• $S_i$は英小文字のみからなる

解法

$K$ は $1$ またはそれと同等の結果が得られるような数になります。

$K=1$ のときに誰が勝利するかが分かれば良いです。これを求めるには、それぞれの文字列 $S_i$ について、「異なる位置の2文字を選択し入れ替える」という操作を $1$ 回だけ行ってできる辞書順最小の文字列を求めれば良いです。

文字列 $T$ に「異なる位置の2文字を選択し入れ替える」という操作を $1$ 回だけ行って辞書順最小の文字列を作るとき、選択する2文字の位置は

1. swapで辞書順で小さくできるならば、そのうち最も前のもの
2. swapで辞書順で小さくできないならば、同じ文字
3. swapで辞書順で大きくしかならないならば、影響の小さい末尾2文字

とわかります。これで各プレイヤーの操作後の文字列がわかりました。

この中から辞書順で最も小さい文字列を求め、それを持っているプレイヤーを全て求められれば良いです。これは愚直に行っても間に合います。

作者感想

ゲーム部分はギャグです。出題側はギャグを証明しないといけないのが難しいところ。
文字列部分は丁寧な仕事が求められます。丁寧じゃないやつ絶対落とすケースを頑張って作りました。

Twisted Lattice

作問者: @Nzt3

AC者数

問題文

縦 $H$ マス、横 $W$ マスのマス目があります。

上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表記します。

• $1\le i<H,1\le j\le W$ において、 $(i,j)$ と $(i+1,j)$ は時間 $1$ で相互に行き来可能です。
• $1\le i\le H,1\le j<W$ において、 $(i,j)$ と $(i,j+1)$ は時間 $i$ で相互に行き来可能です。

マス目上には $N$ 個の出口があり、 $i$ 個目の出口は $(A_i,B_i)$ にあります。

$x=1,2,\dots ,N$について次の問題を解いてください。

• 始め出口 $x$ にいます。別の出口までの移動にかかる時間のうち、最小のものを求めてください。

制約

• $1\le H\le 10^9$
• $1\le W\le 10^9$
• $2\le H\times W$
• $2\le N\le 2\times 10^5$
• $1\le A_i\le H$
• $1\le B_i\le W$
• $i\ne j$ のとき $(A_i,B_i)\ne (A_j,B_j)$

解法

このグラフ上において $(a,b)$ から $(c,d)$ の最短移動時間は $|b-d|=0,|b-d|=1,|b-d|\ge 2$ で式が変わります。

出口がある列について $(1,\ast )$ とその列以外の出口との最短移動時間を前計算しておきます。これは右からの最短移動時間と左からの最短移動時間に分けて計算するとそれぞれ累積minになります。
これにより$|b-d|\ge 2$の出口との最短移動時間は計算ができました。

それ以外の列の出口については、列ごとに出口をmap<int,vector>などで管理して同じ列の出口を行順にソートしておけば、二分探索で $O(\log N)$ で最短移動時間を計算可能です。

前計算の計算量が $O(N\log N)$ になり、各 $x$ について $O(\log N)$ で答えを出せるため全体でも $O(N\log N)$ となります。

作者感想

螺旋階段上の最短経路問題として作りました。3通りに分けるとまとめて処理できて面白いですね。実装がちょっと重いのが難点。

Hard

Permutation Adjacent Sum

作問者: @Sotatsu

AC者数

問題文

整数 $N$, $K$ が与えられます。

長さ $N$ の順列 $P$ に対して、 $f(P)={\sum }_{i=1}^{N-1}|P_i-P_{i+1}{|}^K$ と定めます。

$(1,2,\dots ,N)$ の順列 $N!$ 通りについて $f(P)$ を計算し、その総和を $998244353$ で割ったあまりを求めてください。

制約

• 入力はすべて整数
• $2\le N\le 10^9$
• $1\le K\le 10^6$

解法

答えは $2(N-1)!\times (N\times {\sum }_{i=1}^N{i}^K-{\sum }_{i=1}^N{i}^{K+1})$ なので階乗と $K$ 乗和 が高速に求まれば、この問題を解くことができます。

階乗 $N!\mathrm{mod}998244353$ を求めるには、埋め込みを利用します。
具体的には、適当なブロックサイズ $B$ を決めて $(iB)!\mathrm{mod}998244353$ を時間かけて計算し、その結果をソースコードに直接埋め込みます。そして、$(\lfloor \frac{N}{B}\rfloor B)!\times (\lfloor \frac{N}{B}\rfloor B+1)\times \cdots \times N$ を愚直に計算すればいいです。計算量は $O(B)$ です。

$K$ 乗和は、ラグランジュ補間を使います。ラグランジュ補間を用いると、 $y_0=f(0),y_1=f(1),\dots ,y_d=f(d)$ が既知である $d$ 次以下の多項式に対して、$f(N)$ は $O(d)$ で計算できます。
$K$ 乗和 $F(n)={\sum }_{i=1}^N{i}^K$ は $n$ の $K+1$ 次式であることが示せるので、$F(0),F(1),\dots ,F(K+1)$ を愚直に求めるのに $O(K\log K)$、ラグランジュ補間で$F(N)$ を求めるのに $O(K)$ で計算できます。

作者感想

式変形もそんなに難しくはないので、高度典型知っていますか問題なのかもしれない。固定modじゃなくもできるけど、埋め込みがCTFっぽくて良いかなと思って固定modにしました。

Bicolor Pyramid

作問者: @Nzt3

AC者数

問題文

赤のブロックが $R$ 個、青のブロックが $B$ 個あります。これら $R+B$ 個のブロックを使ってピラミッドを作ります。
ピラミッドの $k$ 段目は、同じ色のブロック $k^2$ 個を使用して作ります。
最大で何段のピラミッドを作れますか？

制約

• $1\le R,B\le 10^{18}$
• 入力は全て整数

解法

対称性より、 $B\le R$ としても問題ありません。そうでない場合は $B$ と $R$ を入れ替えてください。

$B<129$ のとき

「 $1$ 段目から $i$ 段目までを作るときに青のブロックを $j$ 個消費するような配置が可能か」というものをDPを用いて $10$ 段目まで求めます。このとき、 $i(1\le i\le 10)$ 段目までを作るときに可能な青のブロックの消費数の最大値を $X$ とします。
答えは ${\sum }_{k=1}^n{k}^2\le X+R$ を満たす最大の整数 $n$ です。

$B\ge 129$ のとき

答えは ${\sum }_{k=1}^n{k}^2\le B+R$ を満たす最大の整数 $n$ です。

$B$個のブロックを全て使い切るように配置すると自明な上界が達成可能なので、$129$以上の数は必ず異なる平方数の和で表せることを用いると$B\ge 85344$のときに自明な上界が達成可能であることが示せます。全探索を回すと$B\ge 129$なら自明な上界が達成可能であることまで示せます。

作者感想

謎定数により全てが解決する問題です。異なる平方数の和として表せない数が有限個で最大値が小さければ解けるな〜と思って調べたら解けてしまいました。びっくり。
四平方和定理とかからエスパーできるので証明難易度に対して多く通されましたね。

Strange Clock

作問者: @Nzt3

AC者数

問題文

$T3,T4,T6$ を次のようなタイマーとします。

• $T3$ : $3$ 進数を $N$ 桁表示するタイマー
• $T4$ : $4$ 進数を $N$ 桁表示するタイマー
• $T6$ : $6$ 進数を $N$ 桁表示するタイマー

これらのタイマーは、全て次の表示方法に従います。

1. スタート時、 $T3,T4,T6$ の表示は少なくとも1つは違っていた。
2. タイマーは、スタートした後表示される数が $1$ 秒ごとに $1$ ずつ増えていき、 $N$ 桁で表示できる最大の数が表示された $1$ 秒後に表示が $0$ になる。
3. タイマーは表示が $0$ になった後も $1$ 秒ごとに $1$ ずつ増えていくという動作を繰り返す。

スタートから $M$ 秒後に初めて $T3,T4,T6$ の全ての表示が一致しました。
スタート時の表示としてありうるものは何通りありますか。

制約

• $1\le N\le 15$
• $1\le M\le 10^{18}$
• 入力は全て整数

解法

$M$ 秒後に一致した表示として考えられるものは $3^N$ 通り存在します。

• $T3$ の表示を3進法で解釈した数値を $i3$
• $T4$ の表示を4進法で解釈した数値を $i4$
• $T6$ の表示を6進法で解釈した数値を $i6$

とします。

$i3=i4=0$ を $t=0$ とすると、3つのタイマーがある表示 $X$ で一致する時刻 $t$ は 合同方程式

• $t\equiv i3(\mathrm{mod}{3}^N)$
• $t\equiv i4(\mathrm{mod}{4}^N)$

の解として得られます。
合同方程式は中国剰余定理が使える形になっており、拡張ユークリッドの互助法などで高速に解けます。

この解 $t$ を $i3-i6\mathrm{mod}{3}^N$ と $i4-i6\mathrm{mod}{2}^N$ での分類ごとに分けてソートすると、各分類での表示が一致する時刻の一覧が得られます。あとは直前に一致する時刻との間隔が $M$ 秒より長くなるような表示を数えれば良いです。

計算量は $O(N{3}^N)$ です。

しかし、これを実行時間制限に間に合わせることは結構難しいです。
ここで、出力を観察すると「表示が一致する時刻の間隔の種類数は少ない」ということが分かります。
それぞれの $N$ について間隔としてありうる値とその間隔を持つ表示の数を計算し、コードに埋め込むことで高速に答えを求めることができます。

作者感想

新入生向けに共通テストモチーフの問題を作ろうとしたらボス問が生えました。定数倍バトルは罠のつもりだったんですが、勝利している人が(Tester含み)何人かいてすごいですね。

おわりに

本当にたくさんの人に参加していただいたようです。ありがとうございます。
30時間という競プロにしては長時間のコンテストでしたが、PPCは問題不備なく終えることができました。
難易度評価もそこまでずれていないようでよかったです。

また、来年のCPCTFでお会いしましょう。