aaabcbcc ↓ a/aa/b/c/b/cc 6個に分割できる a/a/a/bc/bc/c ×「a/a」や「bc/bc」などで、隣接する文字列が等しくなっているのでダメ
前から貪欲（でいいと思う）
基本的には1文字ずつに区切ることができて、同じ文字が続くところは、前か後のいずれかを他にくっつけないといけない。
bcdaabcd
↓
b/c/da/a/b/c/d
or b/c/d/a/ab/c/d
くっつけて2文字にしたら、次は何が来ようと1文字なら同じにはならない。よって3文字以上にする意味は無い。
同じ文字(a)に後続する文字(b)もまた連続するかも知れないことを考えると、後の文字をくっつけることにした方がよい。
bcdaabb ↓ b/c/da/a/bb →5分割 b/c/d/a/ab/b →6分割
よって、貪欲で基本的には1文字ずつに分割し、前の文字列と同じになったら次の1文字とくっつければよい。
最後に、もう1文字くっつけようとしたら足りなくなる場合がある。
bcdaaaaaaaa
↓
b/c/d/a/aa/a/aa/a a
↑区切りを入れても入れなくても同じ隣接文字列ができてしまう
その場合、同じ文字が $3n+2$ または $3n$ 個連続しているので、組み替えればよい。
b/c/d/a/aa/a/aa/a a ↓ b/c/d/aa/a/aa/a/aa b/c/d/da/a/aa/a/aa/a a ↓ b/c/d/daa/a/aa/a/aa/a
この場合、最後の矛盾を数えなければ、組み替えた後の分割数と等しくなる。
s = input()
prev = ''
k = 0
i = 0
while i < len(s):
c = s[i]
if prev == c:
i += 1
if i == len(s):
break
c += s[i]
prev = c
k += 1
i += 1
print(k)
直接コストを求めるわけではないが、どういう分け方がコストを最小にできるかは考える必要がある。ABC134-Fの解法がヒントになった。
先頭から1文字ずつ進む毎に、「まだ確定していない組」の数だけ、全体のコストは1ずつ増加する。
すると、コストを最小にするには、まだ確定していない組の数を最小にするのがよく、たとえば'B'が来た時に既に未確定の'RG'があれば、優先的にそれと組にした方がよい。
RRRGGGBBB
R → R → R → G → G → G → B → B → B
Cost +1 +2 +3 +3 +3 +3 +2 +1 = 18
未 Rx1 Rx2 Rx3 RG1 RG2 RG3 RG2 RG1
確 Rx2 Rx1
定
1文字目から順番に以下を繰り返すと、最小コストの組が実現できる
最小コストの実現の仕方が分かったので、それを数えあげる。
総合的なパターン数は、上記のいずれかが発生した場合の $k$ を全て掛け合わせればよい。
RRRGGGBBB
R → R → R → G → G → G → B → B → B
未 Rx1 Rx2 Rx3 RG1 RG2 RG3 RG2 RG1
確 Rx2 Rx1
定
x3 x2 x1 x3 x2 x1
Ans. 1 1 1 3 6 6 18 36 36
最後に、どの組をどの子供にあげるかで $N!$ 通りあるので、それをかければ答えとなる。
d = {'R': 1, 'G': 2, 'B': 4}
MOD = 998244353
n = int(input())
s = input()
dp = [0] * 8
ans = 1
for c in s:
m = d[c]
p = 0b111 ^ m
if dp[p]:
ans = ans * dp[p] % MOD
dp[p] -= 1
continue
for q in (1, 2, 4):
if m == q:
continue
if dp[q]:
ans = ans * dp[q] % MOD
dp[q] -= 1
dp[q + m] += 1
break
else:
dp[m] += 1
for i in range(2, n + 1):
ans = ans * i % MOD
print(ans)
逆順に考える。
ある数から、その両隣の数の和を引く操作を「逆操作」とする。
... 3 4 5 ... 操作↓↑逆操作 ... 3 12 5 ...
出てくる数字は正整数なので、最後に操作した数（操作後）は、両隣を足しているためそのいずれとも大きいはず。逆にそうでない数は逆操作できない。
よって、$B_1,B_2,...$ からはじめて、その時に最も大きい数字から逆操作を繰り返して $A_1,A_2,...$ にできるか調べればよい。
こうすると、どの順番で操作を行えばよいかが明確になる。 優先付きキューを使えば、「その時に最も大きい数字」を取り出せる。
注意点としては、
たとえば、$B_i$ で
Ai ... 1 2 1 ... Bi ... 1 1000000000 1 ...
みたいな並びがあった場合、単純に毎回逆操作してたら約 $5 \times 10^8$ 回引くことになり、間に合わない。
中央の数が逆操作可能である間は、両隣の数は変化することはない。これは「両隣のいずれかより小さい数は逆操作できない」「その数自身に逆操作を行わない限り、その数は変化しない」ことから言える。よって、割り算で、連続して操作可能な回数を一括で求めてしまえる。
その際、たとえば
Ai ... 1 100000000 1 ... Bi ... 1 1000000000 1 ...
のように、$A_i$ の段階で大きく差が付いている場合も考えられるため、これを下回るまで逆操作をしてはいけない。
以下の手順で答えが求められる。
from heapq import heapify, heappop, heappush
def solve(n, aaa, bbb):
q = [(-b, i) for i, b in enumerate(bbb) if b != aaa[i]]
heapify(q)
ans = 0
while q:
b, i = heappop(q)
b = -b - aaa[i]
d, b = divmod(b, bbb[(i - 1) % n] + bbb[(i + 1) % n])
if d == 0:
return -1
b += aaa[i]
bbb[i] = b
ans += d
if b != aaa[i]:
heappush(q, (-b, i))
return ans
n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
print(solve(n, aaa, bbb))