目次
AtCoder Grand Contest 037 A～C問題メモ
A - Dividing a String
問題
- 英小文字からなる文字列 $S$ を以下の条件に従って区切る
- 元の順で並べた時、全ての文字列は自身に隣接する文字列と異なる
- 最も多く区切った時、いくつの文字列に分割できるか
- $1 \le |S| \le 2 \times 10^5$
例
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)
B - RGB Balls
問題
- 'R','G','B'が$N$個ずつからなる長さ$3N$の文字列$S$が与えられる
- ここから('R','G','B')を1セットとして$N$人の子供に分配する。RGBはこの順で並んでなくてもよい
- 各組、$S$中で最も左の文字の位置を$i$、最も右の文字の位置を$j$ として、$j-i$ をその組のコストとする
- 全ての組のコストの総和が最小値を取るような分配の仕方の数を$\mod{998244353}$で求めよ
- 子供は区別する（同じ組の分け方でも、配る子供が違うと、別々に数える）
- $1 \le N \le 10^5$
解法
直接コストを求めるわけではないが、どういう分け方がコストを最小にできるかは考える必要がある。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文字目から順番に以下を繰り返すと、最小コストの組が実現できる
- 文字が'B'の場合（'R','G'の場合も入れ替えれば同様）
- 未確定の'RG'が存在したら、そのいずれか1つと組にし、確定させる
- 'RG'が存在せず、'R'または'G'が存在したら、そのいずれか1つを延伸して'RB'または'GB'にする
- この時、単独'R'と'G'の両方が未確定であることはない（そうなら'RG'になっている）
- いずれも存在しなければ、単独未確定の'B'とする
最小コストの実現の仕方が分かったので、それを数えあげる。
- 未確定の'RG'が $k$ 個ある状態で'B'が来た場合、そのどれと組にするかで、$k$ 通りある
- 'RG'が無くて'R'か'G'から延伸する場合も、それが $k$ 個なら、どれと組にするかで $k$ 通りある
総合的なパターン数は、上記のいずれかが発生した場合の $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)
C - Numbers on a Circle
問題
- 円形に $N$ 個の数 $A_1,A_2,...,A_N$ が並ぶ
- 以下の操作を好きな回数繰り返す
- 好きな $i$ を選び、$A_i$ を、それに両隣を加算した数に置き換える
- それぞれの数を $B_1,B_2,...,B_N$ にできるか判定し、できるなら必要な操作回数を求めよ
- $3 \le N \le 2 \times 10^5$
- $1 \le A_i,B_i \le 10^9$
解法
逆順に考える。
ある数から、その両隣の数の和を引く操作を「逆操作」とする。
... 3 4 5 ... 操作↓↑逆操作 ... 3 12 5 ...
出てくる数字は正整数なので、最後に操作した数（操作後）は、両隣を足しているためそのいずれとも大きいはず。逆にそうでない数は逆操作できない。
よって、$B_1,B_2,...$ からはじめて、その時に最も大きい数字から逆操作を繰り返して $A_1,A_2,...$ にできるか調べればよい。
こうすると、どの順番で操作を行えばよいかが明確になる。 優先付きキューを使えば、「その時に最も大きい数字」を取り出せる。
注意点としては、
- 操作回数が膨大になる可能性があるため、連続して操作を行えるなら行う
- 途中で $A_i$ より小さくならないようにする
たとえば、$B_i$ で
Ai ... 1 2 1 ... Bi ... 1 1000000000 1 ...
みたいな並びがあった場合、単純に毎回逆操作してたら約 $5 \times 10^8$ 回引くことになり、間に合わない。
中央の数が逆操作可能である間は、両隣の数は変化することはない。これは「両隣のいずれかより小さい数は逆操作できない」「その数自身に逆操作を行わない限り、その数は変化しない」ことから言える。よって、割り算で、連続して操作可能な回数を一括で求めてしまえる。
その際、たとえば
Ai ... 1 100000000 1 ... Bi ... 1 1000000000 1 ...
のように、$A_i$ の段階で大きく差が付いている場合も考えられるため、これを下回るまで逆操作をしてはいけない。
以下の手順で答えが求められる。
- 最初、$B_i \ne A_i$ である $B_i$ が操作を必要とするので、優先キューに入れる
- 最も大きい $B_i$ を取り出す
- $(B_i - A_i) / (B_{i-1} + B_{i+1})$ を計算
- 商が逆操作可能回数
- 余りが逆操作を行えるまで行った後の新しい $B_i - A_i$ の値
- 逆操作可能回数が0なら、矛盾なので一致させることは不可能
- 1以上なら、答えにその回数を加算すると共に、$B_i$ を更新
- $B_i \ne A_i$ なら、再度優先キューに $B_i$ を入れる
- 全ての $B_i = 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))
