−目次

AtCoder Grand Contest 037 A～C問題メモ
- A - Dividing a String
  - 問題
  - 例
  - 解法
- B - RGB Balls
  - 問題
  - 解法
- C - Numbers on a Circle
  - 問題
  - 解法

AtCoder Grand Contest 037 A～C問題メモ

AtCoder Grand Contest 037

AtCoder Grand Contest 037 解説放送 - YouTube

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))

            

        
      