「左に落ちる」「落ちない」「右に落ちる」ゴーレムの初期位置はこの順で連続しており、たとえば「落ちない」が「左に落ちる」より初期位置が左であることはない。
なので、「左に落ちる」最も初期位置が右のゴーレムと、「右に落ちる」最も初期位置が左のゴーレム（または存在しないかどうか）がわかれば、その間に挟まれたゴーレムが落ちないことになる。
実際に落下が断行せらるのは「左端の文字, 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 | |
左の境界を考える。同じことが左右逆転させて右の境界にも言える。命令を逆順に辿る上で、
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)
先に $s_i$ より小さな数字 $s_j$ が取り出されたら、$s_i$ が黒板の数字を変化させることはない。
X=19
取りだし順 7 9 3 5 2
黒板の数字 19 5 5 2 2 0
^ ^
5,9は自分より前に、より小さい数字で割られているため、黒板の数字は変化しない
例えば、$S$ で一番大きい数字は、一番最初に取り出されない限り黒板の数字に対して影響を与える可能性はない。 「一番最初に取り出されて、影響するか」「それ以外で、影響しないか」の2通りである。
2番目に大きい数字は、以下の3通りが考えられる。
とすると、考えるべき条件の少ない、数字が大きい方から場合の数を確定させていくとよさそう。
こんな風に考える。
こうすると、箱に入ったボールの左端からの順番と、元の問題における操作順が対応づけられ、最終的な黒板の数字が同じになる。
一番左以外は具体的にどの箱に入れたかの情報が必要ない（状態としてまとめてしまえる）ので、このような置き換えが可能となる。
パターン数も、$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というらしい。数字の大小関係のみが重要であるような問題で一考すべし。
解説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である。
つまり、各回目で右端と下端だけを考えて、
というのを考えればよい。
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)))