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

programming_algorithm/contest_history/atcoder/2019/0817_agc037.txt · 最終更新: 2019/08/18 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0