目次
鹿島建設プログラミングコンテスト2020（AtCoder Regular Contest 110）B,C,D,E問題メモ
B - Many 110
問題
- '110' を $10^{10}$ 回繰り返した文字列を $S$ とする
- 文字列 $T$ が与えられるので、$T$ が $S$ の中に連続する部分文字列として何回登場するか答えよ
- $1 \le |T| \le 2 \times 10^5$
解法
例外処理や、答えが1ずれたりしないようにする注意力が必要。
$S$ を実際に作るのはメモリ的に無理だが、$|T|$ よりちょっと長い'110'の繰り返しを作れば、$S$ に登場するかどうかをプログラム標準の文字列検索機能で調べるには十分。登場しなければ答えは0。
登場するなら3つごとに出現するので、$T$ がいくつの'110'に渡って存在するか調べる。
$T$ の先頭文字を調べるなどする。
- '110'から始まるなら、$\lceil \dfrac{|T|}{3} \rceil$ 回の'110'が必要
- '101'から始まるなら、$\lceil \dfrac{|T|+1}{3} \rceil$ 回の'110'が必要
- '011'から始まるなら、$\lceil \dfrac{|T|+2}{3} \rceil$ 回の'110'が必要
となる。$10^{10} - 必要な110の個数 + 1$ 回が答え。
ただし、$|T| \lt 3$ の時は上手くいかない。個数も少ないし全パターン場合分けする。
C - Exoswap
問題
- $1,2,3,...,N$ の順列 $P_1,P_2,...,P_N$ が与えられる
- 以下の操作を行って、$P$ を昇順にできるか判定し、できる場合は操作順の一例を示せ
- 操作
- 以下の全てを好きな順でそれぞれちょうど1回ずつ行う
- $P_1$ と $P_2$ をスワップ
- $P_2$ と $P_3$ をスワップ
- …
- $P_{N-1}$ と $P_N$ をスワップ
- $2 \le N \le 2 \times 10^5$
解法
i 1 2 3 4 5 Pi 2 5 1 3 4 操作 ① ② ③ ④
端っこの数から考える。最大の数 $P_2=5$は、操作②～④をこの順に1回ずつ使う以外に右端に持っていく方法はない。
すると、もう操作②～④は使えなくなる。 もともと5のあった位置 $i=2$ はまだ操作①によって入れ替わる可能性があるが、$P_3～P_5$ はもう動かせない。
i 1 2 3 4 5
Pi 2 1 3 4 5
操作 ① 済 済 済
~~~~~~~←FIXED
よって、この時点で $i=3,4$ について $i=P_i$ になっていないと、不可能となる。
なっている場合は、次に未確定で大きい数字、つまり $i=2$ に持ってくるべき数字、2について同じことをする。
ただし、この方針だと実装によっては「操作を使わなくても完成できてしまう」パターンで、不可能であることが見つけられない。
i 1 2 3 4 5 Pi 1 2 5 3 4 操作 ① ② ③ ④ ↓ Pi 1 2 3 4 5 既に完成している 操作 ① ② 済 済 ①②を使ったら逆に昇順達成が不可能となる
次に未確定で大きい数字を移動させようとしたら既に $i=P_i$ だった、という場合に不可能となるので、それを調べる。
または、最初に転倒数を調べて、$N-1$ 個ちょうどであることを確認してもよい。
D - Binomial Coefficient is Fun
問題
- 長さ $N$ の非負整数列 $A_1,A_2,...,A_N$ が与えられる
- 同じく長さ $N$ で、総和が $M$ 以下の非負整数列 $B_1,B_2,...,B_N$ を考える
- 考えられる全ての $B$ につき $\displaystyle \prod_{i=1}^{N} \binom{B_i}{A_i}$ を求め、その総和を $\mod{10^9+7}$ で求めよ
- $B_i \lt A_i$ のとき、$\displaystyle \binom{B_i}{A_i}=0$
- $1 \le N \le 2000$
- $1 \le M \le 10^9$
- $0 \le A_i \le 2000$
解法
天啓のような言い換えか、二項係数に慣れていないとちょっと難しい式変形が必要。小さいサンプルからの推測が現実的か。
まず、$A_i \gt B_i$ の $i$ が1つでもあると全体が0になるため、答えが正になるには全て $A_i \le B_i$ である必要がある。
なので、$A_i$ の総和を $S$ として、$M \ge S$ でないと、0。以降、$B_i$ を増やせる余地 $T=M-S \ge 0$ とする。
ここで、まずは $B_i=A_i$ として、そこからそれぞれ $k$ 増やしたときに $\displaystyle \binom{A_i+k}{A_i}$ がいくつになるかの表を作ると、
k\A 1 2 3 ------------ 0 1 1 1 1 2 3 4 2 3 6 10 3 4 10 20 ....
こんな感じになる。
で、$A_i$ を $k_i$ 増やしたとして $k_1+k_2+...+k_N \le M$ ならいいので、これは形式的冪級数の考え方でできそうな気になる。
- $f_1 = 1x^0+2x^1+3x^2+4x^3+...$
- $f_2 = 1x^0+3x^1+6x^2+10x^3+...$
- $f_3 = 1x^0+4x^1+10x^2+20x^3+...$
- →答えは、$f_1f_2f_3$ の、$x$ の指数が $T$ 以下の項の係数の和
ただ、$k$ の上限を考えると $M=10^9$ のオーダーなので、実際に表を全部埋めて、FFTでたたみ込んで、とかそういう解法では無さそう。
二項係数は競プロの解法でよく天才的な式変形をしていることがあるので、今回も単純な式に変形できるのだろう、というのは推測できる。
問題はそれをどうやって見つけるか。
実際に $A$ を適当に決めて、「各項に加えた $k_i$ の和がちょうど $0,1,2,...$ である時の $\displaystyle \prod\binom{A_i+k_i}{A_i}$」を手計算すると、
k\A 1 2 3 ------------ 0 1 1 1 1 1x1x1 1 2 3 4 9 2x1x1, 1x3x1, 1x1x4 2 3 6 10 45 3x1x1, 1x6x1, 1x1x10, 2x3x1, 2x1x4, 1x3x4 3 4 10 20 165 略
なんか出てくる。1,9,45,165 - OEIS
他にもサンプルを少し変えて試してみると、これは $\displaystyle \binom{S+N-1+k}{S+N-1}$ であると推測できる。
ならば、答えは $\displaystyle \sum_{k=0}^{T}\binom{S+N-1+k}{S+N-1}$ なので、これは $\displaystyle \binom{T+S+N}{S+N}=\binom{M+N}{S+N}$ で一発で求められることが分かる。
ちゃんとした考察
一気に考えようとせず、まず2つの二項係数を合成することを考える。
$\displaystyle \binom{A_1+k_1}{A_1} \binom{A_2+k_2}{A_2}$ で $k_1+k_2=k$ となるものは、 $\displaystyle \sum_{m=0}^{k} \binom{A_1+m}{A_1} \binom{A_2+(k-m)}{A_2}$ と表せる。
これ、（どうやって求めたらいいのか分からんが）WolframAlphaさんなどに投げると $\displaystyle \binom{A_1+A_2+k+1}{A_1+A_2+1}$ となる。
つまり、合成前と同じ形式の二項係数で表せるので、この結果を $A_3$ とマージ、さらにその結果を $A_4$ とマージ……としていくと、 最終的な式は $\displaystyle \binom{A_1+A_2+...+A_N+k+N-1}{A_1+A_2+...+A_N+N-1} = \binom{S+N-1+k}{S+N-1}$ となる。
これが「$k_1+k_2+...+k_N=k$ の時の $\displaystyle \prod\binom{A_i+k_i}{A_i}$ の値」を表す。
あとはこれを $k=0～T$ について合計する部分は上記と同じ。
答えの式の意味するところ
公式解説にもあるが、何故これで行けるのかをイメージしやすく考えると、$M+N$ 個のボールを並べて、
N=3 M=9
A = {1, 2, 3}
○○○○○○○○○○○○
左から $i$ 番目の区切りの長さが $A_i$ 未満にならないように $N$ 個のボールを選んで黒く塗り、各区間の長さを $B_i$（一番右は使わないあまり）とすると、
○○●○○●○○○○●○ B 2 2 4
$\displaystyle \prod\binom{B_i}{A_i}$ は、その意味からしても「各区切りから $A_i$ 個のボールを選ぶ選び方」と一致する。
ここで、「区切り」と「各区切りから $A_i$ 個」を区別せず、$N+S$ 個を一度に選んでみると、
●○●●●●○●●●●○ 黒いボールの内、 左からA1=1個目までは A1 で選ばれたボール A1+1 個目は区切りのボール その次からA2=2個目までは A2 で選ばれたボール A2+1 個目は区切りのボール ... ●○｜●●｜○●●●｜○
というように、$B_i$ の決め方とその中での選び方を一意に再現でき、1対1対応することがわかる。
この一度に選ぶ選び方が、今回の式 $\displaystyle \binom{M+N}{S+N}$ となる。
経路数えあげに例える方法もあるらしい。
E - Shorten ABC
問題
- 長さ $N$ の'A','B','C'からなる文字列 $S$ が与えられる
- 以下の操作を好きなだけ（0回でもよい）繰り返して作ることのできる文字列が何通りあるか、$\mod{10^9+7}$ で求めよ
- 操作
- 異なる文字が隣り合う部分を選び、その2文字を'A','B','C'のうちそのどちらでもない1文字に置き換える
- $1 \le N \le 10^6$
例
操作回数 0 ABAAC 1 CAAC ACAC ABAB 2 ABC ACB BAC CAB 3 AA BB CC
$S=ABAAC$ のとき、11通り
解法
若干の競プロテクニックの知識と、DP。
競プロテクニック
「ABCからなる文字列の異なる2文字を、そのどちらでもない1文字に置き換える」という操作をしたときに、不変量（操作前と操作後で変わらない指標）がある。
それは、$A=1,B=2,C=3$ としたときの、総XORである。
AB → 01 XOR 10 = 11 = C AC → 01 XOR 11 = 10 = B BC → 10 XOR 11 = 01 = A
これより、操作を行う箇所（縮約する文字の組み合わせ）が同じなら、その順番は影響しないことがわかる。
DP
操作順が関係ないので、「$S_{1～i}$ の部分文字列から作れる文字列は、$S_{1～i-1}$ から作れる文字列の末尾に $S_i$ を追加したものか、追加した上で末尾に対して1回操作を行ったもの」といえそう。
以下のようなDPを定義すると更新できる。
- $DP[i][k:A,B,C]=S_{1～i}$ の部分文字列に操作して作れる文字列で、末尾が $k$ であるものの個数
$S_i=A$ だったとすると、以下のようになる。
- 追加したままの場合
- $DP[i][A] = DP[i-1][A] + DP[i-1][B] + DP[i-1][C]$
- 追加して操作した場合
- $DP[i][B] = DP[i-1][C]$
- $DP[i][C] = DP[i-1][B]$
ABAAから ABAAC から
作れる → 作れる
ABAA ABAAC ABAB
ACA ACAC ACB
CAA CAAC CAB
AB ABC AA
BA BAC BB
C CC ↑
↑ 追加して1回操作
そのまま追加
末尾から遡って2回以上操作を行うことは考えなくてよい。
ABCA: S[1～i-1] から作れる文字の1つ C : S[i] ABCAC : 追加したまま ABCB : 追加して1回操作 ABA : 追加して2回操作したもの S[1～i-1] から作れる文字の中には、 ABB（ABCAの末尾に先に操作したもの）も同様に数えられているはず。 ABA は、ABBに対して C を追加して1回操作したものとして数え上げられる。
ただし、同じ文字に対しては操作を行えないことに起因して、例外的な挙動をすることがある。
例外1.最初の同じ文字の連続
S='AAAAB' の場合を考えると、'AAAA'までを考慮した場合は操作できないので1通りだが、新たに'B'が来たら突然、操作できる候補が増える。
AAAAB AAAC AAB AC B
DPの更新では末尾に追加した文字はその直前との操作しか考慮しないので、AAB,AC,Bを考慮から漏らしてしまう。
そのため、最初に同じ文字 $c_1$ が $p$ 文字連続するとすると、 異なる文字 $c_2$ が来た時点で「$c_2$ を末尾とするものが $p/2$ 個」「$c_3$ を末尾とするものが $(p-1)/2$ 個」増える。
これはあくまで最初の同じ文字の連続のみで、途中だったら、前の方から操作できるのでちゃんと考慮できている。
CAAAAAAAB
~~ ~~~~~ ←ここを縮約すると BAAB ができる。
末尾に追加したBは遡って4回操作していることになるが、考慮できてるのか？
~~~~ ~~~ 同じ文字が連続する箇所は、縮約箇所を2文字ずつずらしても作れる文字列は変わらない。
~~~~~~ ~ 「Bとの操作が必要な末尾のAは0個か1個」という状態まで右にずらしたものが既に考慮済。
例外2.直前がXOR=0のとき
（A,B,Cを1,2,3に置き換えて）先頭からの累積XORを取ったら0になる場合、 操作を可能な限り繰り返して最後に残るのは、'AA','BB','CC'のように同じ文字が2つ続くものとなる。ただしどれが可能かは $S$ による。
その場合、例外1.のミニバージョンのようなことがおこる。
AAB AC B
AAB,ACは考慮できているが、2回操作を行った'B'は考慮から漏れている。これを加算する。
「もし最後に残る可能性があるのが'AA'のみで、追加するのも'A'だったら操作できないじゃないか」となるが、 最初の同じ文字の連続以外（1回以上の操作を行っている）場合、'AA'の直前は'BCA'や'ABC'などであり、そしたら'BB'か'CC'の少なくとも片方は作れる。
う～ん、とりあえずサンプルは合致したが、例外がこれで全てであるという感覚がいまいちつかめないな。
