estie プログラミングコンテスト2024 （AtCoder Regular Contest 188）A,B問題メモ

estie プログラミングコンテスト2024 （AtCoder Regular Contest 188）

ちゃんとした証明ができてないまま解いてるんだよな。

A - ABC Symmetry

問題文

A, B, C からなる空でない文字列 $T$ に対して、以下の $2$ 種類の操作を好きな順で好きな回数だけ行い、空文字列とすることができる時、これを「よい文字列」と呼びます。
- 操作 $1$ ：文字列に存在する同一の文字を $2$ つ選び、削除する（同一の文字が $2$ つ以上ない場合は行えない）
- 操作 $2$ ：文字列に存在する A, B, C を $1$ つずつ選び、削除する（A, B, C がそれぞれ $1$ つ以上ない場合は行えない）
例えば、ABACA は、次のように操作を行うことで空文字列にできるため、よい文字列です。
- $2,4,5$ 文字目を選んで削除する（操作 $2$）。文字列は AA になる。
- $1,2$ 文字目を選んで削除する（操作 $1$）。文字列は空文字列になる。

A, B, C, ? からなる長さ $N$ の文字列 $S$ が与えられます。
? をそれぞれ A, B, C のいずれかに置き換えてできる文字列であって、よい文字列を連続する部分文字列として $K$ 個以上含むものはいくつあるでしょうか。答えを $998244353$ で割った余りを求めてください。
ただし、同じ文字列であるような部分文字列であっても、元の文字列内での位置が異なる場合は別々に数えます。

制約

$1 \leq N \leq 50$
$0 \leq K \leq N(N+1)/2$
$N,K$ は整数である
$|S|=N$
$S$ は A, B, C, ? からなる文字列である

解法

「全ての置き換えに対する総和」とかだと主客転倒が使えそうだけど、今回は「1つ1つの置き換え方に $K$ 個以上含むかどうか」なので筋が悪い。

まずは単純に、文字列が ? を含まず「ABCからなる文字列に、良い部分文字列が何個含まれるか」を求める方法を考える。
$N$ が小さいので $O(N^3)$ かければそりゃいけるんだけど、 DPっぽく解く方法を探るため、先頭から1文字ずつ見ていくような方法でなるべく考える。

良い文字列は、言い換えると「含まれる A,B,C の個数の偶奇が一致する」である。

このため、途中で良い文字列が出現したら、貪欲に確定して問題ない。

A  B  C  A  A  B  ...   という文字列は、先頭から見ると
~~~~~~~  ~~~~           ABC, 続く AA の時点で良い文字列が現れる。

この時、「ABCAAB」までの状態を「(2つの良い文字列の連続) + 余り B」とまとめてしまって問題ない。

なので、「先頭から貪欲に確定した結果、いい文字列にならずに余っている文字片」で場合分けでき、その候補は (なし),A,B,C,AB,AC,BC の7通りしかない。

以下の2つ（8つ?）を状態に持てばよい。

右端を $r$、左端を $1 \le l \lt r$ とした文字列それぞれの内、余っている文字片が（上記の7通り）であるものがそれぞれ何個あるか
ここまでで確定した良い文字列の個数

A  B  C  A  B    余り文字片  状態
            ~       B
         ~~~~      AB
      ~~~~~~~    なし   →   {なし:1, B:2, AB:2}  確定:3
   ~~~~~~~~~~       B
~~~~~~~~~~~~~      AB

※確定した個数は、ここまでの過程で、
  ABCまで進めたときに1個、ABCAの時にBCAで1個、ABCABの時にCABで1個、
  計上されている


■次の文字がBのとき、このように更新できる

旧状態                                         新状態
なし:1  →     B:1
   B:2  →  なし:2, 2個追加で確定          →  {なし:2, A:2, B:2}  確定:5
  AB:2  →     A:2
            その文字(B)から始まるのを1つ追加

この「7通りの文字片の個数 + 確定文字列数」を1つの状態とすると、先頭から順に更新しながら良い部分文字列を数えられる。

この方法なら、? が入った時を考えてもDPしやすい。

$\mathrm{DP}[i,X]:=S_i$ まで見て、状態が $X$ であるものの個数

$S_i=$ ? である箇所は、? を A,B,C と仮定した3通りそれぞれに遷移すればよい。

最終的に、確定文字列数が $K$ 以上になるものを合計すれば答えとなる。

懸念点は状態数が多くなりすぎてTLEにならないか？ということ。
この正確な見積もりが難しくて二の足を踏んでいたが、結局、実装したら通った。

$S$ が50個の ? からなる場合が最も状態数が多くなる。
その場合の $(i,X)$ の組は実験すると約 $10^6$ 通り程度となった。
更新に「? の置き換え方3通り × 各文字片の遷移 7」程度の定数倍をかけても間に合うことがわかる。

「7通りの文字片の状態」は、雑に見積もれば ${}_7\mathrm{H}_N$ くらいあるはずだが、実際は極端に偏ることは起こりにくいこと、また「確定文字列数」も、$i$ が進むと全く確定しないことはあり得ないため、$i$ ごとにおよそ範囲は絞られてくることが、状態数が抑えられた理由かもしれない。

Python3

from collections import defaultdict


def encode(empty, a, b, c, ab, bc, ac, count):
    return empty | (a << 6) | (b << 12) | (c << 18) | (ab << 24) | (bc << 30) | (ac << 36) | (count << 42)


def decode(key, mask=0b111111):
    empty = key & mask
    a = (key >> 6) & mask
    b = (key >> 12) & mask
    c = (key >> 18) & mask
    ab = (key >> 24) & mask
    bc = (key >> 30) & mask
    ac = (key >> 36) & mask
    count = key >> 42
    return empty, a, b, c, ab, bc, ac, count


def solve(n, k, s):
    MOD = 998244353
    if k == 0:
        m = s.count(-1)
        return pow(3, m, MOD)

    dp = {0: 1}
    for ch in s:
        ndp = defaultdict(int)
        if ch == -1:
            cand = (1, 2, 4)
        else:
            cand = (1 << ch,)
        for key, pattern in dp.items():
            empty, a, b, c, ab, bc, ac, count = decode(key)
            for bit in cand:
                # print(f'{ch=} {cand=} {bit=} {empty=} {a=} {b=} {c=} {ab=} {bc=} {ac=} {count=}')
                ns = [0] * 8
                nc = count
                ns[0b000 ^ bit] += empty
                ns[0b001 ^ bit] += a
                ns[0b010 ^ bit] += b
                ns[0b100 ^ bit] += c
                ns[0b011 ^ bit] += ab
                ns[0b110 ^ bit] += bc
                ns[0b101 ^ bit] += ac
                ns[0b000] += ns[0b111]
                nc += ns[0b000]
                ns[bit] += 1
                # print(f'{ns=} {nc=}')
                new_key = encode(ns[0], ns[1], ns[2], ns[4], ns[3], ns[6], ns[5], nc)
                ndp[new_key] += pattern
                ndp[new_key] %= MOD
        dp = ndp

    ans = 0
    for key, pattern in dp.items():
        count = key >> 42
        if count >= k:
            ans += pattern
            ans %= MOD
    return ans


n, k = map(int, input().split())
s = input()
s = ['?ABC'.index(c) - 1 for c in s]
ans = solve(n, k, s)
print(ans)

状態数を節約した解法

解説 - estie プログラミングコンテスト2024 （AtCoder Regular Contest 188）

余っている文字片のうち、反転させた組（A と BC、B と AC、C と AB）はそれぞれ同一視できる。
これにより、文字片のパターンは 7通りでなく4通りの状態で管理できる。

さらに、良い文字列の確定は1文字毎におこなう必要は無い。
累積和のように、先頭から同じ文字が余った状態同士の組が良い文字列の個数と考えることができる。

（$S[1:l]$ ではAが余った状態、$S[1:r]$ でもAが余った状態だった場合、$S[l:r]$ は良い文字列）

   S     A  B  C  A  B  B
余り  -  A  C  -  A  C  A
        `-------|
              `-------|
                    `----|

よって、「余った文字片が（4通りそれぞれ）であった回数」を記録しておけば、最終結果から良い文字列の個数は計算できる。

この方法なら、状態数が $O(N^4)$ であると明確に見積もれる。

B - Symmetric Painting

問題文

円周上を $N$ 等分する位置に、点 $0,1, \ldots , N-1$ がこの順に並んでおり、Alice が点 $0$ に、Bob が点 $K$ にいます。
初め全ての点は白色に塗られています。
両者は、Alice から始めて交互に次のような操作を行います。
- その時点で白色である点を $1$ つ選び、黒色に塗る。ただし、操作後に、操作者と円の中心を結ぶ直線に対して、各点の色が線対称でなければいけない。

操作者が上記の条件を満たす操作ができなければ、そこで一連の操作を打ち切ります。
両者とも、最終的に最も多くの点を黒く塗ることができるように協力して最善の選択をします。一連の操作が全て終了したときに全ての点を黒く塗ることができているかどうかを求めてください。
$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

$1\leq T\leq 10^5$
$2\leq N\leq 2\times 10^5$
$1\leq K\leq N-1$
入力される値はすべて整数である

解法

シミュレーションを実装します。
結果を観察します。
- $N$ が4の倍数の時、NG
- $N$ が2x奇数の時、$\mathrm{GCD}(N/2,K)=1$ ならOK、それ以外はNG
- $N$ が奇数の時、$\mathrm{GCD}(N,K)=1$ ならOK、それ以外はNG
投げると通ります。

AC数もA問題より多いため、「証明は難しいけど、実験からそれらしき法則性を見つけるのは簡単」タイプの問題のように思う。

Aliceは、初手で $0$ か、$N$ 偶数の場合に $N/2$ を塗るしか方法がない。
対象なので、$0$ を塗るとする。

すると、Bobが塗れるのは一意に決まり、$2K$ となる。しばらくは両者選択肢がなく、

$0,2K,-2K,4K,-4K,...$（mod N）

と塗られていく。
この流れは $\mathrm{GCD}(N,2K)$ おきに点が塗られた状態で、次に塗られようとする頂点が既に塗られたものとなり、いったん終了する。

$\mathrm{GCD}(N,2K)=1$ なら全てが塗られているためOK。
それ以外の時は、まだ白い点が残っている。

$N$ が奇数の時
- 点 $K$ は既に塗られている。
- 奇数個の点が塗られるので、次はBobの番だが、操作できない。
- →NG

$N$ 偶数で、塗られた個数 $\dfrac{N}{\mathrm{GCD}(N,2K)}$ が偶数の時
- 次にAliceの手番だが、対称的に塗られているため、$0,N/2$ の両方が既に塗られている。
- →NG
$N$ 偶数で、塗られた個数 $\dfrac{N}{\mathrm{GCD}(N,2K)}$ が奇数の時
- 次Bobの手番
- 対象位置にある2点は、奇数個の点を等間隔に配置するので、「どちらも塗られていない」か、「一方が塗られて、もう一方は塗られていない」状態。
  - 特に $K$ は「一方が塗られて、もう一方は塗られていない」状態。
- 塗られていない頂点からもう1ループできる。
- 2ループ終了後、「一方のみ塗られていた頂点が、両方塗られた状態」になる。
  - 1ループ終了時点で「どちらも塗られていない」点はそのまま
- 次Aliceの手番ではもう操作できない。
- →2ループで全てが塗られた状態になっていないといけない
- →$\mathrm{GCD}(N,2K)=2$ ならOK

Python3

from math import gcd


def naive(n, k):
    state = [0] * n
    state[0] = 1
    turn = 1
    prev = 0
    for i in range(2, n + 1):
        if turn == 0:
            a = -prev % n
        else:
            prev -= k
            a = -prev % n
            a = (a + k) % n
        if state[a] == 0:
            state[a] = i
            prev = a
        elif n % 2 == 0 and state[(a + n // 2) % n] == 0:
            a = (a + n // 2) % n
            state[a] = i
            prev = a
        else:
            break

        turn ^= 1
        # print(n, k, state)
    print(n, k, not (0 in state), state)


# for n in range(3, 41):
#     for k in range(1, n):
#         naive(n, k)

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    if n % 4 == 0:
        print('No')
        continue
    if n % 2 == 0:
        n //= 2
    if gcd(n, k) == 1:
        print('Yes')
    else:
        print('No')

目次

estie プログラミングコンテスト2024 （AtCoder Regular Contest 188）A,B問題メモ

A - ABC Symmetry

問題文

制約

解法

状態数を節約した解法

B - Symmetric Painting

問題文

制約

解法