こんにちは！アルゴリズム班の@noya2 @ebi @shobon @0214sh7 @Sotatsu です。

この記事は2023年4月26日に行われたCPCTF2023 のPPC部門の作問陣writeupです。

目次

Newbie

• Count Coins
• Transfer

Easy

• Find cpctf
• Floor Sqrt
• Geometric Progression Sum
• Whisper Sucu

Medium

• Digital Clock
• God Field
• Move Road
• Max Min GCD

Hard

• Hop Step Jump
• Lost Array
• Mex Max Matrix

おわりに

Newbie

Count Coins

作問者: @ebi

AC者数

問題文

すくくんは $10$ 枚のコインを格納できるコインケースを持っています。
始めに $X$ 枚のコインを持っています。
すくくんは次の $2$ つイベントのうちどちらかが $N$ 回連続で発生します。

• イベント $1$: コインを $1$ 枚得る。すでにコインを $10$ 枚持っている場合は $10$ 枚のままとなる。
• イベント $2$: コインを $3$ 枚失う。持っていたコインが $3$ 枚未満のときは $0$ 枚になる。

$i$ 回目のイベントが $A_i$ であるとき、すくくんは $N$ 回のイベント終了後にコインを何枚持っていますか？

制約

• $1\le N\le 2\times 10^5$
• $0\le X\le 10$
• $1\le A_i\le 2$
• 入力はすべて整数

解法

各イベントをシミュレーションすることで、 $N$ 回のイベント終了後のコインの数を求めることができます。
すくくんが持っているコインの数を $x$ としたときのシミュレーションの疑似コードは以下のようになります。

for i in range(n):
  if a[i] == 1:
    x = min(10, x + 1)
  else:
    x = max(0, x - 3)

作者感想

Count CoinsはもともとMario Kartという名前でした。別にレース要素もないし、混乱を招くので変更になりました。

Transfer

作問者: @ebi

AC者数

問題文

東工大に登校だい！するべく、田園都市線で二子玉川駅に来たあなたは大井町線で大岡山駅を目指します。
あなたは以下の $2$ つの電車を選べます。

• 各駅停車：今から $A$ 分後に来て、$B$ 分乗ると大岡山駅に着く
• 急行：今から $C$ 分後に来て、$D$ 分乗ると大岡山駅に着く

より早く登校だいするために、あなたは大岡山駅に着く最も早い時間が知りたいです。
大岡山駅に着く最も早い時間は何分後かを求めてください。

制約

• $1\le A,B,C,D\le 100$
• $A<C$
• $B>D$
• 入力に含まれる値は全て整数である

解法

$\min (A+B,C+D)$ が答えです。

作者感想

東京工業大学は大岡山駅にあるのでそれにちなんだ問題です。

Find cpctf

作問者: @shobon

AC者数

問題文

長さ $N$ の数列 $A=(A_1,A_2,\cdots ,A_N)$ と、英小文字からなる長さ $N$ の文字列 $S$ が与えられます。 $S$ の $i$ 番目 $(1\le i\le N)$ の文字を $S_i$ と表します。
あなたはちょうど $1$ 回だけ次の操作を順に行います。

1. $A$ を好きなように並び替える。厳密には、 $(1,2,\cdots ,N)$ の順列 $(P_1,P_2,\cdots ,P_N)$ を $1$ つ決め、 $A_1,A_2,\cdots ,A_N$ を $A_{P_1},A_{P_2},\cdots ,A_{P_N}$ に同時に置き換える。
2. すべての $i$ $(1\le i\le N)$ に対し、 $S_i$ のアルファベットを $1$ 文字右にシフトしたものに置き換えることを $A_i$ 回繰り返す。ただし、アルファベット a, b, c, ..., y を $1$ 文字分右にシフトしたものはそれぞれ b, c, d, ..., z であり、z を $1$ 文字分右にシフトしたものは a とする。

適切な操作をすることで、操作後の $S$ の部分文字列として cpctf を含むようにすることは出来るかどうか判定してください。

ただし、文字列 $T$ が文字列 $S$ の部分文字列であるとは、 $T$ が $S$ の先頭から $0$ 文字以上、 $S$ の末尾から $0$ 文字以上取り除くことで得られる文字列であることを言います。

制約

• $N,A_i$ は整数
• $5\le N\le 10^5$
• $0\le A_i<26$
• $S$ は英小文字からなる長さ $N$ の文字列

解法

連続部分列の位置が $N-4$ 通りしかないことに注目して、$i=1,2,\cdots ,N-4$ を固定してすべて調べます。
各 $i$ では $A$ を都合よく並べることで $S_i,S_{i+1},S_{i+2},S_{i+3},S_{i+4}$ をそれぞれ c, p, c, t, f に変えられるかどうかを判定すればよいです。
このときの実装はさまざまですが、$k=1,2,\cdots ,26$ に対して $A_i=k$ となる $i$ の個数を別の配列で管理すると楽です。

作者感想

この問題は PPC の Newbie 以外の最易のうちの 1 つでしたが、それでもかなり難易度に差があるように思いました。プログラミングに慣れていない方は実装が辛かったと思います。
この問題はシーザー暗号・ヴィジュネル暗号を見て思いつきました。

Floor Sqrt

作問者: @noya2

AC者数

問題文

正整数 $N$ が与えられます。
次の条件を満たす正整数 $n$ の個数を求めてください。

• $1\le n\le N$
• $\lfloor \sqrt{n}\rfloor =\lfloor \frac{n}{\lfloor \sqrt{n}\rfloor }\rfloor$

制約

• $N$ は整数
• $1\le N\le 10^{12}$

解法

実験して条件を満たす $n$ を列挙すると、 $n=k^2,k^2+1,\dots k^2+k-1$ の形の整数が条件を満たしていることが分かります。$k$ ごとにまとめて処理すると実行時間制限に間に合います。算数をすると $\Theta (1)$ 時間で解くこともできます。

作者感想

成り立つか怪しい見た目をしている恒等式っぽいものを探して、問題が出来上がりました。

Geometric Progression Sum

作問者: @noya2

AC者数

問題文

長さ $N$ の数列 $A=(A_1,A_2,\dots ,A_N)$ があり、はじめはすべての要素は $0$ です。
整数 $X$ が与えられます。今から $Q$ 回の操作を行なって $A$ を更新します。

$i$ 回目の操作では $B_i,L_i,R_i$ が与えられます。 $k=L_i,L_i+1,\dots ,R_i$ の順に次を行なってください。

• $A_k$ に $B_i{X}^{k-L_i}$ を加算する

$Q$ 回の操作が終了した後の $A$ の各要素を $998244353$ で割ったあまりを求めてください。

制約

• 入力はすべて整数
• $1\le N\le 2\times 10^5$
• $1\le X<998244353$
• $1\le Q\le 2\times 10^5$
• $1\le B_i<998244353(1\le i\le Q)$
• $1\le L_i\le R_i\le N(1\le i\le Q)$

解法

imos法の要領で遷移を $X$ 倍にすれば良いです。

作者感想

imos法の応用問題を目指して作りました。git を使って問題管理をしていたのですが、人々のミスが重なりに重なった結果、この問題のbranchが大変なことになりました。

Whisper Sucu

作問者: @0214sh7

AC者数

問題文

ウィスパーすく君は、人間とは思えないほどの低音ボイスとそこから繰り出すハスキーなささやきで有名な声優です。

待ちに待ったASMR音声収録日、なんとウィスパーすく君は寝坊をしてしまいました！これでは収録に遅刻してしまいます！子猫ちゃんたちにときめきを届けるべく、ウィスパーすく君は何としても収録スタジオに行かなくてはなりません！

ウィスパーすく君の住んでいる街は $N$ 頂点 $M$ 辺の無向グラフとして表され、 $i$ 番目の辺は頂点 $u_i$ と $v_i$ を結んでいます。ウィスパーすく君の家は頂点 $1$ にあり、スタジオは頂点 $N$ にあります。また辺には信号があることがあり、$i$ 番目の辺は以下の $3$ 通りのいずれかです。

• $s_i=1$ のとき、その辺には信号があり偶数分にのみ移動できる。
  • 正確には、時刻 $2n$ から時刻 $2n+1$ にかけて辺の一端から他端に移動できる ( $n$ は非負整数)
• $s_i=2$ のとき、その辺には信号があり奇数分にのみ移動できる。
  • 正確には、時刻 $2n+1$ から時刻 $2n+2$ にかけて辺の一端から他端に移動できる ( $n$ は非負整数)
• $s_i=3$ のとき、その辺には信号がなくいつでも移動できる。

ウィスパーすく君は今いる頂点から、辺で結ばれている別の頂点に $1$ 分かけて移動します(途中で引き返すことはありません)。ウィスパーすく君は急いでいるので、今いる頂点に留まることはありません。頂点 $N$ 以外の頂点において他の頂点に移動できないとき、ウィスパーすく君は爆散します。

ウィスパーすく君は時刻 $0$ に家を出発しました。ウィスパーすく君の検索アプリであるあなたは、最短で何分でスタジオにたどりつけるか、あるいは爆散するかを判定して下さい。

制約

• $2\le N\le 10^5$

• $1\le M\le \min (10^5,\frac{N(N-1)}{2})$

• $1\le u_i,v_i\le N$

• $s_i\in \{1,2,3\}$

• 与えられるグラフは単純である、すなわち

  • $u_i\ne v_i$
  • $i\ne j$ ならば $\{u_i,v_i\}\ne \{u_j,v_j\}$

• 与えられるグラフは連結である

  • すなわち、どの頂点からどの頂点にも $0$ 個以上の辺をたどって移動できる

• 入力はすべて整数

解法

$N$ 頂点グラフから、頂点番号と時刻の偶奇をもった頂点数 $2N$ の拡張グラフを作成し、そのグラフ上でBFSを行います。

作者感想

CPCTF22で出題したShout Sucuの続編がついに登場
Shout Sucuはストーリーができてから問題を作ったのですが、今回は問題を先に作ってからストーリーをつけました。このため問題設定が不完全燃焼でした。
解法や作者感想、答えとなるフラグを眺めてると作問者の性格がよくわかりますね。

Digital Clock

作問者: @shobon

AC者数

問題文

しょぼん君は不思議なデジタル時計を持っています。そのデジタル時計は「時間」と「分」をそれぞれ表示する機械で、「時間」は $0$ 以上 $H$ 未満の整数値、 「分」は $0$ 以上 $M$ 未満の整数値を取ります。

デジタル時計に表示されている「時間」「分」は最初ともに $0$ です。しょぼん君はそのデジタル時計の時刻を設定しようと思っています。

時刻の設定に使うボタンは $2$ 種類あり、それぞれ「時間ボタン」、「分ボタン」という名前です。

• 「時間ボタン」を $1$ 回押すと、「時間」の値が $H-1$ 未満なら「時間」の値を $1$ 増やし、「時間」の値がちょうど $H-1$ なら「時間」の値を $0$ にします。

• 「分ボタン」を $1$ 回押すと、「分」の値が $M-1$ 未満なら「分」の値を $1$ 増やし、「分」の値がちょうど $M-1$ なら「分」の値を $0$ にします。

それ以外で「時間」と「分」の値が変わることはありません。

しょぼん君が時刻の設定に使うボタンを合わせてちょうど $K$ 回押したとき、デジタル時計の表示、すなわち「時間」と「分」の組は全部で何通りありえますか？

制約

• $2\le H,M\le 10^9$
• $1\le K\le 10^{18}$
• 入力は全て整数

解法

到達可能な組は整数 $n(0\le n\le K)$ を用いて $(n\mathrm{mod}H,(K-n)\mathrm{mod}M)$ と表されます。

ここで $L=\mathrm{lcm}(H,M)$ とすると、 $(n\mathrm{mod}H,(K-n)\mathrm{mod}M)=(m\mathrm{mod}H,(K-m)\mathrm{mod}M)$ なら $m-n$ は $L$ の倍数です。

結局 $n=0,1,\cdots ,K$ の $L$ で割った余りの種類数を求めればよいので、到達可能な組は $\max (K+1,L)$ 種類であることが示されます。

作者感想

この前に noya2 さんとyukicoderで合同コンテストを開いたときに、ギリギリに出したので間に合わなかった問題です。もともと $O(H+W)$ 解法が想定でしたが、noya2 さんが $O(\log \min (H,W))$ 解を出してくれてびっくりしました。
実装が軽くてギャグですが、なかなか非自明だと思います。

God Field

作問者: @0214sh7

AC者数

問題文

預言者のあなたは乱闘界に迷い込んでしまいました。預言者たちの戦いが今始まる！

あなたの HP は最初 $X$ であり、あなたは $N$ 個の防具を持っています。$i$ 個目の防具の防御力は $A_i$ です。防具は使い捨てであり、一度使うと壊れてしまいます。

今からあなたは $M$ 回の攻撃を順番に受けます。
攻撃には攻撃力があり、$1$ 回の攻撃に対し $0$ 個以上の防具を使って対抗することができます。攻撃力を $B$ 、使う防具の防御力の総和を $S$ とするとあなたは $\max (0,B-S)$ のダメージを負い、その分だけ HP を失います。$i$ 番目の攻撃の攻撃力は $B_i$ です。

また、攻撃には「無属性」または「闇属性」の属性が付いています。$i$ 番目の攻撃の属性は $C_i$ で表され、$C_i=0$ のとき無属性で $C_i=1$ のとき闇属性です。

あなたは以下のいずれかを満たしたとき、昇天してしまいます。

• HP が $0$ 以下になる
• 闇属性の攻撃で $1$ 以上のダメージを負う

防具を適切な方法で使ったとき、あなたは昇天せずに生き残ることができますか？また生き残れる場合、HP は最大でいくつ残りますか？

制約

• 入力はすべて整数
• $1\le N,M\le 10$
• $1\le X\le 10^9$
• $1\le A_i\le 10^9$
• $1\le B_i\le 10^9$
• $C_i\in \{0,1\}$

解法

$dp[i][S]:=$ 受けた攻撃の回数が $i$ 、使った防具の集合が $S$ のとき残る HP の最大値、どうしても昇天するときは $0$

というDPを行うことで答えを得ます。

作者感想

問題設定がおぼろげながら浮かんできたので指数時間解法を与えて問題にしました。
ゴッドフィールドには無･闇属性の他に5つ属性があるのですが、実装が大変になるだけなのでオミットしました。
同じゲームを題材にした問題でもMario Kartは問題名が変更になったのにこっちはなんともありませんでした。どうして･･･

Move Road

作問者: @Sotatsu

AC者数

問題文

縦 $H$ マス、横 $W$ マスの $H\times W$ のマス目を考えます。マス目の各行は道路になっており、車が何台か走っています。
時刻 $t=0$ において、上から $i$ 行目、左から $j$ 列目のマス $(i,j)$ は、$S_{i,j}=$D のとき車があり、$S_{i,j}=$. のとき車がありません。

Sotatsu君は時刻 $t=0,1,2,\dots$ に、上下左右に隣接するマスに移動するまたはとどまることができます。
しかし、Sotatsu君は車のある道に移動すると車にぶつかってしまいます。
上から $1$ 行目の全てのマスはスタートマス、上から $H$ 行目の全てのマスはゴールマスであり、これらのマスの上に車はありません。
Sotatsu君は車にぶつかったり、轢かれたりせずにスタートマスのいずれかからゴールマスのいずれかに移動したいです。

時刻 $t=0.5,1.5,2.5,\dots$ に車は右に $1$ マス進みます。右端のマスにいた車は同じ行の左端のマスに移動します。このとき、すでにSotatsu君がいるマスに車が進んでしまうと、Sotatsu君は車に轢かれてしまいます。

Sotatsu君は、時刻 $t=0$ にスタートマスのいずれかから移動を開始します。車にぶつかったり、轢かれたりせずにゴールマスのいずれかまで移動できるか判定してください。

制約

• $3\le H,W\le 2000$
• $H,W$ は整数
• $S_{i,j}$ は . または D
• $i=1$ または $i=H$ のとき $S_{i,j}$ に D は存在しない

解法

整数時間における車の状態は周期性があり、それはW通りです。visit[t][i][j]:=時刻を $W$ で割ったあまりが $t$ のときに、マス $(i,j)$ に到達できるかという問題を考えます。
これは、BFSやDFSなどを用いて求められますが、このままでは状態数が多すぎます。

車を移動させる代わりに、時刻 $t$ が整数のとき常にSotatsu君は左に $1$ 移動すると考えます。また、Sotatsu君は左端から出ると同じ行の右端に移動するとします。このようにすることで、車は初期配置から移動させなくてよくなり、「visit[i][j]:= Sotatsu君はマス $(i,j)$ に到達することができるか」とすることができ、状態数を $O(HW)$ にすることができます。

Sotatsu君の移動に常に左に移動することを追加すると、左上 / 左下 / 左 への移動が可能であることがわかります。各移動が可能である条件は以下のようになります。

• 左上：上と左上に車がない
• 左下：下と左下に車がない
• 左　：左に車がない

よってBFSやDFSを用いて時間計算量 $O(HW)$ でこの問題を解くことができました。

作者感想

鳥が障害物をよけながらピョンピョン進むゲームから着想を得た問題です。

Max Min GCD

作問者: @noya2

AC者数

問題文

長さ $N$ の正整数列 $A=(A_1,A_2,\dots ,A_N),B=(B_1,B_2,\dots ,B_N)$ が与えられます。

$k=1,2,\dots ,N$ のそれぞれに対して、以下の値を求めてください。

• $C_k=\underset{k=\min (i,j)}{\max }\gcd (A_i,B_j)$

すなわち、$C_k$ は $1\le i,j\le N$ かつ $\min (i,j)=k$ を満たすすべての整数の組 $(i,j)$ に対する $\gcd (A_i,B_j)$ の最大値です。

制約

• $1\le N\le 10^5$
• $1\le A_i,B_i\le 10^5(1\le i\le N)$
• 入力はすべて整数

解法

最大値の最大値という典型テクの紹介です。$\max$ の順序を入れ替えることで見通しが良くなります。$A_i,B_j$ の約数を列挙し、条件を満たすindexにchmaxしていくと解けます。

作者感想

最大値の最大値、驚き度高めのテクだと思うので、布教を目指して作りました。

Hop Step Jump

作問者: @noya2

AC者数

問題文

東工大には $N+1$ 個のマスが一列に並んだマス目があり、マスには順に $0$ から $N$ までの番号がついています。Alice は東工大に新入生が入ってくるので嬉しくて飛び跳ねたい気持ちでいっぱいです。そこで、Alice は次の動作を $1$ 回以上行って、Alice のいるマス $0$ から traP の部室があることで知られるマス $N$ に行くことにしました。

• $1\le a<b<c$ なる整数 $a,b,c$ を選ぶ。
• 今いるマスから $a$ マス進み、さらに $b$ マス進み、さらに $c$ マス進む。

Alice はすべての動作を終えた後、マス $N$ にいなければなりません。
Alice が経由するマスの集合としてあり得るものは何通りありますか。答えを $998244353$ で割ったあまりを求めてください。

制約

• $6\le N\le 10^{18}$
• $N$ は整数

解法

母関数が多項式の有理関数になるので、行列累乗で解くことができます。

作者感想

母関数の記事をtatyamさんが書いているので、それの布教のために作りました。

数日前まで Alice の部分は noya だったのですが、noya というハンドルネームの後輩がtraPに加入したため、急遽 Alice に変更しました。

Lost Array

作問者: @shobon

AC者数

問題文

正整数 $X,K,M,Y$ と素数 $P$ が与えられます。

昨夜、しょぼん君は無限項からなる数列 $A$ で遊んでいました。しかし今日になって、しょぼん君はどうやって数列 $A$ を作ったかを忘れてしまいました。数列 $A$ について覚えていることは以下の $4$ つです。

1. $A_1=X$ である
2. すべての $n\ge 1$ に対し、 $A_{n+K}=A_n+A_{n+1}+\cdots +A_{n+K-1}$ を満たす
3. $A_2,\cdots ,A_K$ は負でない整数である
4. $A_M$ を $P$ で割った余りは $Y$ である

$(A_2,A_3,\cdots ,A_K)$ の組を定めると条件「2.」によって数列 $A$ がただ $1$ つ定まります。上の $4$ つの条件をすべて満たすような数列 $A$ は存在しますか？存在する場合は、数列 $(A_2,A_3,\cdots ,A_K)$ が辞書順最小になるようなものを求めてください。

なお、長さ $k$ の数列 $(x_1,x_2,\cdots ,x_k)$ が $(y_1,y_2,\cdots ,y_k)$ より辞書順で小さいとは、 $2$ つの列が異なって、$i$ を $x_i\ne y_i$ であるような最小の正整数としたときに $x_i<y_i$ であることを言います。
長さ $k$ の数列の集合 $S$ のうち、 $X=(x_1,x_2,\cdots ,x_k)$ が辞書順最小とは、 $X$ が $S$ に含まれており、 $S$ に含まれる $X$ でない任意の数列 $Y$ に対して $X$ は $Y$ より辞書順で小さいことを言います。

制約

• $3\le P<10^9$
• $P$ は素数
• $0\le X<P$
• $2\le K\le 30$
• $K+1\le M\le 10^{18}$
• $0\le Y<P$
• 入力はすべて整数

解法

数列 $A$ は線形方程式です。よって、 $A_1,A_2,\cdots ,A_K$ によらない定数 $c_1,c_2,\cdots ,c_K$ で、$A_M=c_1{A}_1+c_2{A}_2+\cdots +c_K{A}_K$ を表されます。また、4. の条件によって、$c_1,c_2,\cdots ,c_K$ は $P$ で割った余りのみを考えればよいです。
$c_1,c_2,\cdots ,c_K$ を $P$ で割った余りは、行列累乗と呼ばれるテクニックで時間計算量 $O(K^3\log M)$ で求められます。

その後は、$A_1=X$ により、方程式 $A_M-c_{1}X\equiv c_2{A}_2+c_3{A}_3+\cdots +c_K{A}_K(\mathrm{mod}P)$ を満たす非負整数 $A_2,A_3,\cdots ,A_K$ のうち、辞書順最小のものを求める問題に帰着されます。ここで、$c_i\not\equiv 0(\mathrm{mod}P)$ なら、$c_{i}y\equiv 1(\mathrm{mod}P)$ かつ $0\le y<P$ である整数 $y$ がただ 1 つ存在します。 $y$ は $c_i$ の逆元と呼ばれており、 $P$ が素数の場合はフェルマーの小定理により $y\equiv c_i^{P-2}(\mathrm{mod}P)$ であるので、 $y$ は時間計算量 $O(\log P)$ で求められます。

$A_M-c_{1}X\not\equiv 0(\mathrm{mod}P)$ なら、 $i$ を $i=2,3,\cdots ,K$ のうち $c_i\not\equiv 0(\mathrm{mod}P)$ となる最大のものとすると、$j=2,3,\cdots ,K$ に対して

$\{\begin{array}{ll}{A}_j=(A_M-c_{1}X)c_i^{P-2}\%P& (j=i)\\ A_j=0& (j\ne i)\end{array}$

とすればこれが辞書順最小になっています。 $i=2,3,\cdots ,K$ のうち $c_i\not\equiv 0(\mathrm{mod}P)$ となるものが存在しない場合、 $A_M-c_{1}X\equiv c_2{A}_2+c_3{A}_3+\cdots +c_K{A}_K(\mathrm{mod}P)$ の左辺は $0$ でなく、右辺は常に $0$ であるので条件を満たす $A$ が存在せず、答えは No です。

また、$A_M-c_{1}X\equiv 0(\mathrm{mod}P)$ なら、すべての $j=2,3,\cdots ,K$ に対して $A_j=0$ とすればよいです。

作者感想

この問題は二段階の考察に分かれ、知識も考察も実装も必要な問題でした。もともとは「 $0\le A_1,A_2,\cdots ,A_K<P$ のうち、条件を満たす数列 $A$ の個数を $998244353$ で割った余りを求める」という問題がありましたが、最小辞書順を求める方が美しかったのでこっちを推しました。
問題は自分が思ったより解かれませんでしたが、Hard の難易度としてはなかなかバランスがよかったと思います。

Mex Max Matrix

作問者: @noya2

AC者数

問題文

長さ $H$ の非負整数列 $A$ および長さ $W$ の非負整数列 $B$ が与えられます。次のようにして定まる $H\times W$ 行列 $M$ を考えます。

• $M_{i,j}=\mathrm{mex}(\{\max (A_x,B_y)\mid x=i\vee y=j\})$

ただし、添字の $i,x$ は $1,2,\dots ,H$ を、添字の $j,y$ は $1,2,\dots ,W$ を動くものとします。
また、非負整数の有限集合 $P$ に対し $\mathrm{mex}(P)$ は $P$ に含まれない最小の非負整数を表します。

$Q$ 個のクエリに答えてください。

$k$ 番目のクエリでは $l_k,r_k,d_k,u_k$ が与えられるので、$\sum _{i=l_k}^{r_k}\sum _{j=d_k}^{u_k}{M}_{i,j}$ を求めてください。

制約

• $1\le H,W\le 10^5$
• $0\le A_i,B_j\le 10^9$
• $1\le Q\le 10^5$
• $1\le l_k\le r_k\le H$
• $1\le d_k\le u_k\le W$
• 入力はすべて整数

解法

$M$ の要素は高々 $4$ 個であることがわかります。それらは $0,\mathrm{mex}(A),\mathrm{mex}(B),\mathrm{mex}(A+B)$ であること、また、それらが現れる条件を丁寧に整理すると、クエリ毎に $\Theta (1)$ で答えを求めることができます。

作者感想

問題名の響きが良さそうなものを目指して作りました。かなりギャグです。

おわりに

特に問題やテストケースの不備もなくコンテストを終えることができました。しかし、CPCTF全体としてはPPC部門の問題の割合が大きすぎるという意見が寄せられました。来年以降は全体のバランスをCTF班の方々と協力して整えていこうと思います。

それでは、また来年のCPCTFでお会いしましょう！