AtCoder Regular Contest 209 (Div. 1) A,B,D問題メモ

AtCoder Regular Contest 209 (Div. 1)

「こういう処理を実装すれば答えが求められる」と言葉で表現するところまでは考察できても、 それを正しく、手早く実装するのが難しい、という問題が多かった印象。

A - Bracket Game

• ( と ) のみからなる文字列 $S$ があります。
• 太郎君と次郎君はこの文字列を使って以下のゲームをします。
  • 太郎君が先手、次郎君が後手となり、以下の $3$ 種類の操作のうちいずれか $1$ つを選んで行うことを交互に繰り返します。
    • $S$ の先頭の文字を削除する。
    • $S$ の末尾の文字を削除する。
    • 終了宣言をする。
• $S$ の長さがちょうど $K$ になったとき、あるいはいずれかのプレイヤーが終了宣言をした時点で、ゲームが終了します。
• ゲームの終了時点で $S$ が正しい括弧列であるならば次郎君の勝利、そうでないならば太郎君の勝利となります。
• ゲーム開始前の $S$ が与えられるので、両者が最適に行動した場合の勝者を求めてください。

• $T$ 個のテストケースが与えられるので、それぞれについて解いてください。

• $1 \le T \le 10^5$
• $1 \le K \lt |S| \le 10^6$
• $S$ は ( と ) のみからなる文字列
• $T, K$ は整数
• すべてのテストケースにわたる $|S|$ の総和は $10^6$ 以下

何となく、競プロでのゲームは太郎（先手）が“正しい”（整っている）状態を目指し、次郎（後手）はそれを“崩そう”とする、 という設定が多いような勝手なイメージがあるが、この問題の場合は逆。
次郎が正しい括弧列を目指し、太郎がそれを崩す。

まず簡単に判定できるケースとして、

• $S$ が初期状態で正しい括弧列でない場合は、先手が即座に終了を宣言し、先手必勝

よって、後手が勝つには初期状態は正しい括弧列で無ければならない。
その場合、後手に手番が回ってきた時、$S$ は必ず奇数長である。
正しい括弧列は奇数長になり得ないので、後手から終了を宣言することはできない。

よって、後手が勝つには長さ $K$ になるまで耐え忍ぶ必要がある。
$K$ が奇数の場合はそれすらできないので、先手必勝。

以下、$K$ は偶数とする。

先手の行動に対し後手は常に正しい括弧列を維持するように先頭か末尾を選択しなければならない。
取れる手段は非常に少なく、ほとんど先手の意思によって決まる。

①外側の括弧を1つ取っても正しい括弧列の場合
  (  ((((()))))  )
  ~              ~

②深さ1の括弧 () が両端にある場合
  () (()(())) ()
  ~~          ~~

いずれも後手は、先手が取ったのと対になる括弧を取るしかない。
これ以外の場合は、正しい括弧列の維持は不可能である。

②の場合、片側のみに深さ1の括弧があっても、先手は反対側を取れば勝ちとなるので、両側に必要となる。

ゲームの流れは、①→②の順に進み、②から①に戻ることは無い。
以下のようにゲームをシミュレートし、判定できる。

• ① 正しい括弧列が維持される限り、$S$ の外側の括弧を剥がす。
• ② その後、両端それぞれから連なる深さ1の括弧 “()()()…()” の個数を数える。
  • 左右のうち、少ない方を削除する。（先手は少ない方から削除していこうとするので）
• この結果、残る文字列の長さが $K$ 以下なら後手の勝ち。

①で、正しい括弧列が維持されているかどうかを調べるのに少し迷うが、 「左で最初に閉じ括弧が出現してから、右で最後に開き括弧が出現するまでの、最小深さ」によって判定できる。

Python3

def solve(s, k):
    x = 0
    n = len(s)

    if n % 2 == 1 or k % 2 == 1:
        return 'First'

    depths = []
    for i in range(n):
        if s[i] == '(':
            x += 1
        else:
            x -= 1
        if x < 0:
            return 'First'
        depths.append(x)
    if x != 0:
        return 'First'

    acc_mins = [1 << 60] * n
    m = 1 << 60
    for i in range(n // 2, n):
        m = min(m, depths[i])
        acc_mins[i] = m
    m = 1 << 60
    for i in range(n // 2 - 1, -1, -1):
        m = min(m, depths[i])
        acc_mins[i] = m
    acc_mins.insert(0, 0)
    # print(depths)
    # print(acc_mins)

    l = 0
    r = n - 1
    while r - l > k:
        if min(acc_mins[l + 1], acc_mins[r]) < l + 1:
            break
        if s[l] == '(' and s[r] == ')':
            l += 1
            r -= 1
        else:
            break
    # print(f'{l=} {r=}')

    if r - l == k:
        return 'Second'

    i = l
    while i < r:
        if s[i] == '(' and s[i + 1] == ')':
            i += 2
        else:
            break
    j = r
    while l < j:
        if s[j - 1] == '(' and s[j] == ')':
            j -= 2
        else:
            break

    m = min(i - l, r - j)
    if r - l - m <= k:
        return 'Second'

    return 'First'


t = int(input())
for _ in range(t):
    s = input()
    k = int(input())
    ans = solve(s, k)
    print(ans)

B - Minimize Even Palindrome

• 英小文字からなる文字列 $s$ に対し、$s$ の部分文字列であって、偶数長の回文であるものの個数を $f(s)$ で表します。
• 英小文字からなる文字列 $S$ が与えられます。
• $S$ の文字を並べ替えて得られる文字列 $S'$ のうち、$f(S')$ が最小となるものを $1$ つ出力してください。

• $T$ 個のテストケースが与えられるので、それぞれについて解いてください。

• $1 \le T \le 10^5$
• $2 \le |S| \le 2 \times 10^5$
• $S$ は英小文字からなる
• 全てのテストケースにおける $|S|$ の総和は $2 \times 10^5$ 以下

最も多い文字を“a”だとする。次に多い文字（あれば）を“b”とし、それ以外の文字をまとめて“c”とする。
それぞれの個数を、$C_a,C_b,C_c$ とする。

同じ文字が連続しないようにすると、回文の中心とできる箇所が無いので、$f(S')=0$ を達成できる。

具体的な構築方法で少し迷うが、公式Editorialでは以下のような方法が紹介されている。

• $S$ に出てくる文字を多い順にソートする。[a, a, a, a, a, b, b, c, c]
• この順に、$S'$ の $0,2,4,6,...,\frac{|S|}{2},1,3,5,7,...$ 番目に配置していく。

“a”が多い場合、どうしても連続させねばならず、回文が発生する。

bとcで区切られる $C_b + C_c + 1$ 個のスペースにaを何個かずつ挟んでいくことになる。

aaa...   aaa...   aaa...   aaa...   aaa...
  ↓       ↓       ↓       ↓       ↓
       b        c        b        c

その時、区切られたそれぞれの“aaa…“から取れる回文の個数は、aの長さ $k$ に対し、$O(k^2)$ のオーダーとなる。
具体的には、以下のようになる。（参考: A002620 - OEIS）

偶数長の場合
  a a a a a a
   1 2 3 2 1     ←各位置を中心とした回文の個数,  p6 = 1+2+3+2+1 = 9

奇数長の場合
  a a a a a a a
   1 2 3 3 2 1   ←各位置を中心とした回文の個数,  p7 = 1+2+3+3+2+1 = 12

これを $p_k$ とする。

2乗のオーダーなので、1箇所に固めるよりなるべく均等に配置するのがよさそう。
つまり、$C_a / (C_b+C_c+1) = d あまり m$ の場合、$m$ 個のスペースに $d+1$ 個の”a”、残りに $d$ 個の“a”を入れればよい。

ただし、注意すべき事項がある。
「区切り文字が左右で同じで、かつそこに入れる“aaa…“が偶数長」の時、外側にも回文が広がってしまう。

      v         v        ←区切る文字が同じだと、、、
... a b a a a a b a ...
           ^             ←ここを中心とした回文が、bの外にも広がってしまう。

なるべく区切り文字は同じものが隣り合わないようにしたいが、 それでも $C_b$ と $C_c$ の差によっては隣り合わざるを得ない場合もある。

ところで、$k$ が偶数の時、$p_k+p_k=p_{k+1}+p_{k-1}$ が成り立つ。

1 2 3 2 1 + 1 2 3 2 1  =  1 2 3 3 2 1 + 1 2 2 1

よって、「区切り文字が同じ＆”a”が偶数長」の区間が複数ある時、 2個ずつペアにして1個移してしまえば、（“a”のみからなる）回文の個数を変えずに奇数長2つにできる。
偶数長のままだと、ここからさらに区間の外側に伸びる分が追加されてしまうので、奇数長にした方が必ずよくなる。

更に言うと、別に区切り文字が同じかどうかに関係なく、 偶数長の区間は2個ずつペアにして奇数長2つにして問題ない。
これにより、偶数長の区間は0個か1個にできる。

左右端のスペースは偶数長でも問題ないので、高々1個の偶数長はそこに割り当てるようにすれば、 区切り文字の配置は気にしなくてもよくなる。

Python3

from collections import Counter
from heapq import heapify, heappop, heappush, heapreplace


def not_consecutive_string(cnt):
    hq = [(-v, c) for c, v in cnt]

    heapify(hq)
    ans = []
    prev = ''
    while hq:
        v, c = heappop(hq)
        if c == prev:
            v2, c2 = hq[0]
            ans.append(c2)
            prev = c2
            if v2 == -1:
                heappop(hq)
            else:
                heapreplace(hq, (v2 + 1, c2))
            heappush(hq, (v, c))
        else:
            ans.append(c)
            prev = c
            if v < -1:
                heappush(hq, (v + 1, c))
    return ans


def solve(s):
    n = len(s)
    cnt = Counter(s)
    cnt = cnt.most_common()

    if len(cnt) == 1:
        return s

    mc = cnt[0][1]
    mcc = cnt[0][0]
    under_second = n - mc

    if mc <= under_second + 1:
        ans = not_consecutive_string(cnt)
        return ''.join(ans)

    sc = cnt[1][1]
    under_third = n - mc - sc
    total_space = under_second + 1

    if sc <= under_third + 1:
        res = not_consecutive_string(cnt[1:])
        d, m = divmod(mc, total_space)
        ans = [''] * (total_space * 2 - 1)
        for i in range(total_space - 1):
            ans[i * 2 + 1] = res[i]
        for i in range(total_space):
            ans[i * 2] = mcc * (d + int(i < m))
        return ''.join(ans)

    free_space = (under_third + 1) * 2
    odd_space = under_second + 1 - free_space
    res = not_consecutive_string([(cnt[1][0], under_third + 1)] + cnt[2:])
    res.extend([cnt[1][0]] * (sc - (under_third + 1)))

    d = (mc - total_space) // (total_space * 2)
    d = d * 2 + 1
    m = mc - d * total_space

    # dが奇数に限定した商、あまり

    def count_palindrome(n):
        h = n // 2
        if n % 2 == 1:
            return h * (h + 1)
        return h * h

    best = 1 << 60
    best_i = 0
    for i in range(odd_space + 1):
        tmp = count_palindrome(d) * i
        tmp += count_palindrome(d + 2) * (odd_space - i)
        free_total = mc - d * i - (d + 2) * (odd_space - i)
        if free_total < 0:
            continue
        dd, mm = divmod(free_total, free_space)
        tmp += count_palindrome(dd) * (free_space - mm)
        tmp += count_palindrome(dd + 1) * mm
        # print(f'{i=} {tmp=}')
        if tmp < best:
            best = tmp
            best_i = i

    ans = [''] * (total_space * 2 - 1)
    for i in range(total_space - 1):
        ans[i * 2 + 1] = res[i]
    odd_indices = list(range(-odd_space * 2 - 1, -1, 2))
    for i in range(odd_space):
        if i < best_i:
            ans[odd_indices[i]] = mcc * d
        else:
            ans[odd_indices[i]] = mcc * (d + 2)
    free_total = mc - d * best_i - (d + 2) * (odd_space - best_i)
    dd, mm = divmod(free_total, free_space)

    free_indices = list(range(0, (free_space - 1) * 2, 2)) + [-1]
    for i in range(free_space):
        if i < mm:
            ans[free_indices[i]] = mcc * (dd + 1)
        else:
            ans[free_indices[i]] = mcc * dd

    return ''.join(ans)


t = int(input())
for _ in range(t):
    s = input()
    ans = solve(s)
    print(ans)

D - A_A_i

• 長さ $N$ の数列 $A = (A_1, A_2, \ldots, A_N)$ が与えられます。
  • 各要素は $1$ 以上 $N$ 以下の整数もしくは $-1$ です。
• すぬけ君はこの数列 $A$ を用いて新しい数列を作ることにしました。
  • まず、この数列 $A$ に登場する $-1$ を全て $1$ 以上 $N$ 以下の整数に書き換えます。
  • 次に、以下の式に従って長さ $N$ の数列 $B = (B_1, B_2, \ldots, B_N)$ を作ります。
    • $B_i=A_{A_i}$
• $B$ としてありうるもののうち辞書順で最小のものを求めてください。

• $T$ 個のテストケースが与えられるので、それぞれについて解いてください。

• $1 \le T \le 10^5$
• $1 \le N \le 5 \times 10^5$
• $1 \le A_i \le N$ または $A_i = -1$
• すべてのテストケースにわたる $N$ の総和は $5\times 10^5$ 以下
• 入力はすべて整数

i   1   2   3   4
A   4  -1  -1   3
A'  4   3   1   3    ←-1を置き換えた一例
B   3   1   4   1    ←A'に従って、B[i] = A'[A'[i]] と置換した結果。
                       Bが辞書順最小となるようにする。

いろいろ条件が混在する。落ち着いて整理する。

この問題のポイントは、$A_i$ が「他の要素を参照するindex」であると同時に「他の要素から参照される値」である点。
$A_i=-1$ を置換するとき、

• $A_j=1$ である $j$ を指せば、$B_i$ を最小値“1”にできる。
• しかし、もし他の要素から $A_k=i$ のように指されていると、$B_k$ の方を最小値“1”にできなくなってしまう可能性がある。

$B_i$ と $B_k$ のどちらを優先すればいいか？の条件を見つけていくことが1つの大きな課題となる。

とりあえず、すぐに分かるケースを除いておく。

選択の余地無く、一意に決まる。問題文の通りの操作をするだけ。

この時、$A_1=1$ とし、他の $-1$ も全て $1$ を指すのが最適。

初期の $A$ で既に決まっている箇所（$A_i = j \neq -1$ かつ $A_j \neq -1$ の時の $B_i$）以外は、全て $B_i=1$ にできる。

上と同様。

すぐに全ては決まらなくても、部分的に決まる箇所がある。

辞書順最小は、先頭に近い値を優先して小さくすればよいので、

• 前から指されている $-1$
  • つまり、$A_j=i, A_i=-1, j \lt i$ となる $j$ があるような $i$

これは全て $A_i=1$ にするのが最適となる。部分的に決定してしまってよい。

部分的に決めた時点で、$-1$ が $0$ 個になった場合、これは一意に決まる。

$A_i=-1$ となる $i$ が $1$ 個の場合、以下の2つの選択肢がある。

• $A_i=i$ とする。
  • $B_i=i$ となる。
• $A$ における $-1$ 以外の最小値を $A_j$ とし、$A_i=j$ とする。
  • $B_i=A_j$ となる。

$B_i$ が小さくなる方を採用すればよい。
ただし $B_i$ が同じになる中ではなるべく $A_i$ を小さくする。

• $j$ は、同じ値がある場合は最も左のindexとする。
• $i = A_j$ の場合は、$A_i=\min(i,j)$ とする。

この時点で残っている $A_i=-1$ は、たとえ他から $A_j=i$ のように指されていたとしても、 $B_j$ より $B_i$ を小さくする方が優先順位が高い。

$A_j=1$ となるような $j$ があればそこを指せばいいし、 無くてもどれか1個の $-1$ を $1$ にすれば作り出せる（★）ので、 $A_i=-1$ となる $i$ は、★に使う高々1個を除いて $B_i=1$ にすることが可能となる。

★をするのかしないのか、する場合はどの $A_i$ を $1$ にすればよいのか、というのが次のポイントとなる。

要点となるのが、

• $x:=$「$-1$ を後ろから指す最初のindex」
  • つまり、$A_i=-1, A_j=i, i \lt j$ を満たす $i$ が存在するような $j$ の中での最小値
• $y:=$「$x$ 以降で最初に $A_i=-1$ となるような $i$」

ただし、$x,y$ は存在しないこともある。その場合分けは後述し、ひとまず存在するものとする。

$B_x$ は、以降に出てくる要素より値を小さくする優先順位が高い。

i  1  2  3  4  5  6  7  8  9
A  8 -1  6 -1 -1  4 -1  1 -1
                  x  y

$A_6$ から指されている $i=4$ は、それ自身は $B_4=1$ にすることを優先していいのだが、 その方法の中でも「最も $A_4$ が小さくなる」ような方法によって $1$ にしなければならない。
（$B_6$ をなるべく小さくするため）
そのためには $B_7$ や $B_9$ が大きくなっても構わない。

この例の場合、$A_7=1$ とし、 他の全ての $-1$ は $7$ を指すのが最適となる。

i   1  2  3  4  5  6  7  8  9
A   8 -1  6 -1 -1  4 -1  1 -1
A'  8  7  6  7  7  4  1  1  7
B   1  1  4  1  1  7  8  8  1    B2,B4,B5=1 とする中で、
                   ~             最もB6が小さい

ただし、既存で $1$ が既にあり、そのindexが $y$ より小さい場合は、それを使った方がよい。

i   1  2  3  4  5  6  7  8  9
A   8 -1 [1]-1 -1  4 -1  1 -1    ←最初から A3=1 が存在
A'  8  3  1  3  3  4  3  1  3    ←★はおこなわず、全ての -1 は 3 に置換するのが最適
B   1  1  8  1  1  3  1  8  1

つまり、「$y$」と「既存の $1$、複数ある場合は最初のindex」の小さい方を、各 $-1$ は指せばよい。

この2つがいずれも存在しない場合は、「最後の $-1$ を $1$ にし、他の $-1$ はそれを指す」。

まとめると、

• 上述の $x,y$ を求める。該当するものが無ければ $y=\infty$ とする。
• 最初に出現する $1$ のindexを $z$ とする。無ければ $z=\infty$ とする。
• 最後に出現する $-1$ のindex を $w$ とする。
• $p=\min(y,z)$ とする。
  • $p \lt \infty$ なら、$A_p=1$ とし、他の全ての $A_i=-1$ は $p$ に置換する。
  • $p = \infty$ なら、$A_w=1$ とし、他の全ての $A_i=-1$ は $w$ に置換する。

以上の場合分けで構築できる。

Python3

def solve(n, aaa):
    def make(aaa):
        assert -1 not in aaa
        bbb = [0] * n
        for i, a in enumerate(aaa):
            bbb[i] = aaa[aaa[i]] + 1
        return bbb

    aaa = [a - 1 if a != -1 else -1 for a in aaa]

    if aaa[0] == -1:
        aaa[0] = 0

    INF = 1 << 60
    first_rev_i = INF
    next_rev_i = INF
    last_m = INF
    min_val = INF
    for i, a in enumerate(aaa):
        if a == -1:
            if first_rev_i != INF and next_rev_i == INF:
                next_rev_i = i
            last_m = i
            continue
        min_val = min(min_val, a)
        if i > a and aaa[a] == -1:
            if first_rev_i == INF:
                first_rev_i = i
            continue
        if i < a and aaa[a] == -1:
            aaa[a] = 0

    if -1 not in aaa:
        return make(aaa)

    if aaa.count(-1) == 1:
        i = aaa.index(-1)
        if i < min_val:
            aaa[i] = i
        else:
            k = aaa.index(min_val)
            if i > min_val:
                aaa[i] = k
            else:
                aaa[i] = min(i, k)
        return make(aaa)

    try:
        first_1 = aaa.index(0)
    except:
        first_1 = INF
    first_1 = min(first_1, next_rev_i)

    if first_1 != INF:
        aaa[first_1] = 0
        for i in range(n):
            if aaa[i] == -1:
                aaa[i] = first_1
        return make(aaa)

    aaa[last_m] = 0
    for i in range(n):
        if aaa[i] == -1:
            aaa[i] = last_m
    return make(aaa)


t = int(input())
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    ans = solve(n, aaa)
    print(*ans)