目次
ExaWizards 2019 C,D,E 問題メモ
C - Snuke the Wizard
問題
- $N$ マスが横一列に並び、左から $i$ 番目のマスには英大文字 $s_i$ が書かれている
- はじめ、各マスにはゴーレムが1体ずついる
- 命令が $Q$ 個、順番に与えられる
- $i$ 個目の命令は $t_i,d_i$ で与えられる
- $t_i$ は英大文字、$d_i$ は'L'か'R'
- その時点で $t_i$ が書かれたマスにいるゴーレムは、一斉に $d_i$ が'L'なら1マス左に、'R'なら1マス右に移動する
- 左端のマスから左に、または右端のマスから右に移動したゴーレムは、落下する
- 最終的に落下せず残っているゴーレムは何体か求めよ
解法
「左に落ちる」「落ちない」「右に落ちる」ゴーレムの初期位置はこの順で連続しており、たとえば「落ちない」が「左に落ちる」より初期位置が左であることはない。
- 移動は1マスずつなので、仮に順番が入れ替わるなら途中で必ず同一マスに存在する必要がある
- 一度同一マスに入ったゴーレムは、その後の移動は全く同じになる（分離されることがない）
なので、「左に落ちる」最も初期位置が右のゴーレムと、「右に落ちる」最も初期位置が左のゴーレム（または存在しないかどうか）がわかれば、その間に挟まれたゴーレムが落ちないことになる。
実際に落下が断行せらるのは「左端の文字, L」「右端の文字, R」の2命令のみである。
それまでで左端や右端に集約されてると一度の命令で多くのゴーレムが落下してしまうが、その場合も上記の命令の前に「左から2番目, L」などがある必要がある。
すると、命令を逆順に辿って「その時点でここより左にいたら左に落ちちゃう」境界と「右にいたら右に落ちちゃう」境界を求めていく方法が考えられる。
S N C Z W
| |
6 S L | |
5 C L | |
4 N L | |
3 C L | |
2 N R | |
1 C R | |
左の境界を考える。同じことが左右逆転させて右の境界にも言える。命令を逆順に辿る上で、
- 「境界のすぐ右側の文字, L」という命令があると、現時点では生き残るとされている中で左端のゴーレムは、その命令（と後に続く命令）で落ちることになる
- 境界を右に移動する
- 「境界のすぐ左側の文字, R」という命令があると、さっき落ちると言った↑の命令が発効されたときにはそこに居たゴーレムは既に右に“避難”しており、生き残ることになる
- 境界を左に移動する
- 途中で左右の境界が重なったら、その時点でどこにゴーレムがいようとミナゴロシが確定する
import sys
n, q = map(int, input().split())
s = input()
commands = [line.rstrip().split() for line in sys.stdin]
commands.reverse()
l, r = 0, n - 1
for t, d in commands:
if s[l] == t and d == 'L':
l += 1
elif 0 < l and s[l - 1] == t and d == 'R':
l -= 1
if s[r] == t and d == 'R':
r -= 1
elif r < n - 1 and s[r + 1] == t and d == 'L':
r += 1
if l > r:
break
print(r - l + 1)
D - Modulo Operations
問題
- 正整数 $X$ が黒板に書かれている
- 互いに異なる $N$ 個の正整数の集合 $S=\{s_1,s_2,...,s_N\}$
- 以下を $N$ 回繰り返す
- $S$ から任意の数を1つ選ぶ。$s_i$ とする
- $s_i$ を $S$ から取り除く
- 黒板の数字を、$s_i$ で割った余りに書き換える
- このような操作において、$S$ から数字を取りだす順番のパターンは $N!$ 個存在する
- $N!$ 個の全てにおいて「最終的に黒板に書かれている数字」を合計した数を、$\mod{10^9+7}$ で求めよ
- $1 \le N \le 200$
- $1 \le X,s_i \le 10^5$
解法
基本的な事実
先に $s_i$ より小さな数字 $s_j$ が取り出されたら、$s_i$ が黒板の数字を変化させることはない。
X=19
取りだし順 7 9 3 5 2
黒板の数字 19 5 5 2 2 0
^ ^
5,9は自分より前に、より小さい数字で割られているため、黒板の数字は変化しない
- 例えば9が黒板の数字を変化させるということは、その時点の黒板の数字は9より大きい必要がある
- それより前に9より小さい数7で割られているが、7で割った余りは7より小さい
例えば、$S$ で一番大きい数字は、一番最初に取り出されない限り黒板の数字に対して影響を与える可能性はない。 「一番最初に取り出されて、影響するか」「それ以外で、影響しないか」の2通りである。
2番目に大きい数字は、以下の3通りが考えられる。
- 一番大きい数字で割られた後、他の小さい数字より前に取り出され、影響する
- 一番大きい数字で割られる前かつ他の小さい数字より前に取り出され、影響する
- 他の小さい数字より後に取り出され、影響しない
とすると、考えるべき条件の少ない、数字が大きい方から場合の数を確定させていくとよさそう。
問題の読み替え
こんな風に考える。
- 空き箱が $N$ 個、一列に並ぶ
- ボールが $N$ 個あり、各ボールには $s_1,s_2,...,s_N$ がかかれている
- 数字が大きいボールから順に、まだ空の箱を選んで入れていく
- この時「残っている中で最も左端の箱」を選んだときのみ、黒板の数字をボールに書かれた数字で割った余りに書き換える
こうすると、箱に入ったボールの左端からの順番と、元の問題における操作順が対応づけられ、最終的な黒板の数字が同じになる。
一番左以外は具体的にどの箱に入れたかの情報が必要ない（状態としてまとめてしまえる）ので、このような置き換えが可能となる。
パターン数も、$i$ 番目のボールを入れるときに残っている箱は $N-i+1$ 個なので、 一番左に入れるパターンは1通り、それ以外のパターンは $N-i$ 通りとなり、順次計算できる。
xx:yy = 今までの数字だけで考えると、黒板の数字がxxであるパターンがyy個ある、ということを表す
→分岐: スルーする（パターン数をN-i倍する）
↘分岐: 書き換える（パターン数は継承）
N=5 X=82
S: 22 13 11 6 5
i 0 1 2 3 4 5
si 22 13 11 6 5
82:1 --> 82:4 --> 82:12 --> 82:24 --> 82:24
| | | `-> 4:24 `-> 2:24
| `-> 4: 4 `-> 5:12 --> 5:24
| `-> 0:24
`-> 16:1 --> 16: 3 --> 16: 6 --> 16: 6
| | `-> 4: 6 `-> 1: 6
`-> 3: 1 `-> 5: 3 --> 5: 6
`-> 0: 6
ただし、最後の数字（最小の数字）は分けて考えた方がやりやすい。
まず、最後の数字はスルーする選択肢がない（そのまま計算してもパターン数が0になるだけで計算は合うのだが、無駄な計算になる）ので、 ラスト直前まで計算したら、その結果から割った場合のみのパターンを計算した方がよい。
また、計算途中で黒板の数字が最小の数字未満になった時点で、この先どういう順で操作しようともう書き換わることはないので、 （黒板の数字）×（その時点でのパターン数）×（残っている数字の並べ方の個数） を答えに加算して、その数字は除外してもよい。
$s_i$ ごとに状態が2倍になると $O(2^N)$ で多くなりすぎる気もするが、実際は $X$ より大きくなることはないので、 同じ数字が被ったりしたのをまとめたら $O(X)$ に収まる。よって計算量は全体で $O(NX)$ になる。
from collections import defaultdict
def prepare(n, MOD):
f = 1
factorials = [1]
for i in range(1, n + 1):
f = f * i % MOD
factorials.append(f)
return factorials
n, x = map(int, input().split())
sss = list(map(int, input().split()))
sss.sort(reverse=True)
ms = sss.pop()
MOD = 10 ** 9 + 7
factorials = prepare(n, MOD)
dp = {x: 1}
ans = 0
for i, s in enumerate(sss):
ndp = defaultdict(lambda: 0)
k = n - i
for y, c in dp.items():
if y < s:
ndp[y] = (ndp[y] + c * k) % MOD
else:
z = y % s
ndp[y] = (ndp[y] + c * (k - 1)) % MOD
if z < ms:
ans = (ans + z * c * factorials[k - 1]) % MOD
else:
ndp[z] = (ndp[z] + c) % MOD
dp = ndp
for y, c in dp.items():
ans = (ans + (y % ms) * c) % MOD
print(ans)
このような、順列に挿入することで遷移を進めるDPを挿入DPというらしい。数字の大小関係のみが重要であるような問題で一考すべし。
E - Black or White
問題
- 黒いチョコレート $B$ 枚と白いチョコレート $W$ 枚を、以下の法則に従って食べる
- 両方の色とも残っていれば、確率 $\frac{1}{2}$ で色を選んでどちらかを食べる
- 片方しか残っていなければ、残っている色のチョコレートを食べる
- $i$ 番目に黒いチョコレートを食べる確率を、$1 \le i \le B+W$ の全ての $i$ について求めよ
- ただし、解答は $\mod{10^9+7}$ で答えよ
- つまり、$x$ のモジュラ逆数を $x^{-1}$ として、答えが $\frac{y}{x}$ の形で表されるなら $x^{-1}y \mod{10^9+7}$ で答えよ
- $1 \le B,W \le 10^5$
解法
解説pdfに倣って、経路数えあげで考える。
以下のようなグリッドを左上から右下まで最短で移動する。下への移動が黒チョコを食べたことを表す。ある点から右に行くか下に行くかは 1/2 で決まる。
B=3 W=5 ・→・→・→・→・→・ ↓ ↓ ↓ ↓ ↓ ↓ ・→・→・→・→・→・ ↓ ↓ ↓ ↓ ↓ ↓ ・→・→・→・→・→・ ↓ ↓ ↓ ↓ ↓ ↓ ・→・→・→・→・→・
$i$ 回目の移動はナナメに位置する矢印のどれかになる。たとえば5回目の移動は太矢印のいずれかになり、この内の下矢印を通る確率の合計が、$i=5$ の時の答えとなる。
・→・→・→・→・⇒・ ↓ ↓ ↓ ↓ ⇓ ↓ ・→・→・→・⇒・→・ ↓ ↓ ↓ ⇓ ↓ ↓ ・→・→・⇒・→・→・ ↓ ↓ ⇓ ↓ ↓ ↓ ・→・⇒・→・→・→・
実際に確率を埋めると、以下の感じになる。 右と下の両方に行ける点は、流入する確率の和を、1/2ずつ右と下に振り分ける。片方にしか行けない点は、流入する確率がその方向に集約される。
わかりやすさのため、分母は $i$ 回目の移動の場合 $2^i$ となるよう揃えている。 ナナメに追っていくと、各回で確率の合計は1となっていることがわかる。
・→1/2 →・→ 1/4 →・→ 1/8 →・→ 1/16 →・→ 1/32 →・ 1/2 1/4 1/8 1/16 1/32 2/64 ・→1/4 →・→ 2/8 →・→ 3/16→・→ 4/32 →・→ 5/64 →・ 1/4 2/8 3/16 4/32 5/64 14/128 ・→1/8 →・→ 3/16→・→ 6/32→・→10/64 →・→ 15/128→・ 1/8 3/16 6/32 10/64 15/128 58/256 ・→2/16→・→10/32→・→32/64→・→84/128→・→198/256→・
さて、このような経路数えあげは、パスカルの三角形と親和性が高いことが知られている。
ただ、求めるのが経路数であればパスカルの三角形の一部であり二項係数で算出できるが、確率の場合は右端 or 下端で集約が発生する。
3/16 3/16
↓ ↓
下端 2/16→・→ 5/32→・ 2/16→・→10/32→・
~~~~~~~~~~~⇣⇣~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~
5/32 代わりに右移動に集約される
×こっちには行けない
集約が起こるタイミングは各回でたかだか2回（右端と下端）であり、新たに流入する確率も「二項係数/$2^i$」で求められるので、 集約結果は累積的に計算可能である。
端以外の点では、1つの点から流出する右移動と下移動は等確率なので、その中で下移動が占める割合も1/2である。
つまり、各回目で右端と下端だけを考えて、
- ベースは1/2
- 下端からさらに下に移動できるはずだった確率は、実際には移動できないので引く
- 右端からさらに右に移動できるはずだった確率は、実際には移動されず下移動に集約されるので、足す
というのを考えればよい。
def prepare(n, MOD):
f = 1
factorials = [1]
for m in range(1, n + 1):
f *= m
f %= MOD
factorials.append(f)
inv = pow(f, MOD - 2, MOD)
invs = [1] * (n + 1)
invs[n] = inv
for m in range(n, 1, -1):
inv *= m
inv %= MOD
invs[m - 1] = inv
return factorials, invs
b, w = map(int, input().split())
MOD = 10 ** 9 + 7
I2 = 500000004 # 2^(-1) mod MOD
factorials, inverses = prepare(b + w, MOD)
buf = []
denom = I2
pi, qi = 0, 0
for i in range(b + w):
if i >= b:
pi *= 2
pi += factorials[i - 1] * inverses[i - b] * inverses[b - 1]
pi %= MOD
if i >= w:
qi *= 2
qi += factorials[i - 1] * inverses[i - w] * inverses[w - 1]
qi %= MOD
buf.append((I2 - (pi - qi) * denom) % MOD)
denom = denom * I2 % MOD
print('\n'.join(map(str, buf)))
