AtCoder Grand Contest 071 A,B 問題メモ

AtCoder Grand Contest 071

A - XOR Cross Over

• 非負整数列が書かれている黒板があります。はじめ、黒板には長さ $N$ の非負整数列 $A=(A_1,A_2,\dots,A_N)$ のみが書かれています。
• 黒板に書かれている非負整数列の長さがすべて $1$ になるまで以下の一連の操作を行い続けます。
  • 黒板に書かれている非負整数列のうち、長さ $2$ 以上の非負整数列を $1$ つ選び、黒板から消去する。
    • 選んだ非負整数列を $B=(B_1,B_2,\dots,B_n)$ とする。
  • 続けて $1 \leq k \lt n$ を満たす整数 $k$ を $1$ つ選び、以下の $X,Y$ を求める。
    • $X = B_1 \oplus B_2 \oplus \dots \oplus B_k$
    • $Y=B_{k+1} \oplus B_{k+2} \oplus \dots \oplus B_n$
  • 最後に黒板に以下の $2$ つの非負整数列を書き込む。
    • $(B_1 \oplus Y, B_2 \oplus Y,\dots,B_k \oplus Y)$
    • $(B_{k+1} \oplus X,\ B_{k+2} \oplus X,\dots,B_n \oplus X)$
  • ただしここで、 $\oplus$ はビット単位 $\mathrm{XOR}$ 演算を表します。

• 最終的に黒板に書かれている $N$ 個の長さ $1$ の非負整数列を $(C_1),(C_2),\dots,(C_N)$ としたとき、 $\sum_{i=1}^{N}C_i$ として考えられる値の最小値を求めてください。

• $1 \leq N \leq 500$
• $0 \leq A_i \lt 2^{40}$
• 入力される値はすべて整数

問題文の理解に少しかかる。数列を2つに分割していき、分割の際、相手の総XORが自身の各要素にかかる。
元の $A$ で同じ区間に由来する数列であっても、そこに至るまでの操作によって値が変わりうるので、素直な区間DPは使えない。

だが、実験するとほとんどは打ち消され、まぁ…単純とはいわないが、頑張れば求められる形になることが分かる。

各時点で黒板に書かれている数列は、元の $(A_l,A_{l+1},...,A_{r})$ に 何らかの共通の値 $z$ がXORされた形であり、$(A_l \oplus z, ..., A_r \oplus z)$ と表せる。

この「外部から数列全体にXORされる共通の値」をとりあえず変数 $z$ としておいて、 分割したときにどうなるか、幅が小さい区間で考える。

※(a XOR b) を、単に ab と表すとする。

幅2                   分割候補            各XORの和
[ az  bz ]        →  [ az / bz ]         2 * ab

幅3
[ az  bz  cz ]    →  [ az / bz  cz ]     abcz + 2*bc
                  →  [ az  bz / cz ]     abcz + 2*ab
                                         ----------------
                                  最適値  abcz + 2*min(ab, bc)

幅4
[ az  bz  cz  dz] →  [ az / bz cz dz]    abcd + (z=aの時の[bz,cz,dz]の最適値)
                                        = 2*abcd + 2*min(bc,cd)
                                        
                  →  [ az bz / cz dz]    2*ab + 2*cd
                  
                  →  [ az bz cz / dz]    (z=dの時の[az,bz,cz]の最適値) + abcd
                                        = 2*abcd + 2*min(ab,bc)
                                        -------------------------
                                  最適値  min( 2*abcd+2*min(ab,bc,cd), 2*ab+2*cd )

幅5
[ az bz cz dz ez ] → [az/bz cz dz ez]    abcdez + (z=aの時の[bz,cz,dz,ez])
                                          ~~~~~~
                   → [az bz/cz dz ez]    2*ab + (z=abzの時の[cz,dz,ez])
                                        = 2*ab + abcdez + 2*min(cd,de)
                                                 ~~~~~~
                   → [az bz cz/dz ez]    (z=dezの時の[az,bz,cz]) + 2*de
                                        = abcdez + 2*min(ab,bc) + 2*de
                                          ~~~~~~
                   → [az bz cz dz/ez]    (z=eの時の[az,bz,cz,dz]) + abcdez
                                                                     ~~~~~~
                                        --------------------------------
                                  最適値  abcdez + (zに依らない値)

すると、以下の傾向があることに気付く。

• 幅が偶数の時、最適値は $z$ に依らない
• 幅が奇数の時、最適値は「$(数列の総XOR \oplus z) + (zに依らない値)$」

偶数の時は外部の影響を考えなくてよい。奇数の時も $z$ は分割に依らず決まった形でのみ影響するので、$z$ に依らない値のみで大小比較できる。
$z$ を含む項はとりあえず無視して、それ以外での最適値で区間DPをする。

• $\mathrm{DP}[l,r]:=$ 区間 $[l,r)$ における、$z$ を含む項を除いた最適値

$\mathrm{DP}[l,r]$ を求める時、区切り位置 $m=l+1,...,r-1$ を全て試す過程で、

• $[l,r)$ の幅が偶数で、(偶,偶) に分割する場合
  • 幅が偶数の区間のDP結果は、そのままの値を使えばよい。
  • $\mathrm{DP}[l,r] \underset{\min}{\leftarrow} \mathrm{DP}[l,m]+\mathrm{DP}[m,r]$

• $[l,r)$ の幅が偶数で、(奇,奇) に分割する場合
  • 幅が奇数の区間のDP結果は、$z$ を考慮する必要がある。
  • $(az,bz,cz,dz,ez,fz)$ を(3,3)に分割する場合、$(az,bz,cz)$ には $defz$ が、$(dz,ez,fz)$ には $abcz$ がXORされる。
    • ここで、$z$ は互いに打ち消しあい、全ての要素から消滅する。
    • つまり、双方に $abcdef$ の総XORがかかる。
  • $\mathrm{DP}[l,r] \underset{\min}{\leftarrow} \mathrm{DP}[l,m]+\mathrm{DP}[m,r] + 2 (A[l,r)の総XOR)$

• $[l,r)$ の幅が奇数で、(偶,奇) に分割する場合
  • 最適値は $\mathrm{DP}[l,m]+\mathrm{DP}[m,r] + (A[l,r)の総XOR \oplus z)$ となる。
  • $z$ を含む項は除くので、DPへ記録する値としては単純な足し合わせとなる。
  • $\mathrm{DP}[l,r] \underset{\min}{\leftarrow} \mathrm{DP}[l,m]+\mathrm{DP}[m,r]$

これで区間DPを埋めていき、$\mathrm{DP}[0,N]$ が答え。

ただし、$N$ が奇数の時は、最終結果でも $z$ を含む項が省略されている。
$A$ 全体に対する“外部”からの影響はないため、$z=0$ として、$A$ の総XORを足したものが最終的な答えとなる。

Python3

import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    aaa = inp[1:]

    xor_acc = np.zeros(n + 1, np.int64)
    for i in range(n):
        xor_acc[i + 1] = xor_acc[i] ^ aaa[i]

    tbl1 = np.full((n, n + 1), 1 << 20, np.int64)

    for i in range(n):
        tbl1[i, i] = 0
        tbl1[i, i + 1] = 0

    for w in range(2, n + 1):
        for l in range(n - w + 1):
            best = 1 << 60
            for k in range(1, w):
                tmp = tbl1[l, l + k] + tbl1[l + k, l + w]
                if w % 2 == 0 and k % 2 == 1:
                    tmp += 2 * (xor_acc[l + w] ^ xor_acc[l])
                best = min(best, tmp)
            tbl1[l, l + w] = best

    ans = tbl1[0, n]
    if n % 2 == 1:
        ans += xor_acc[-1]
    return ans


SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

B - Maximum Bracket Subsequence

• 整数 $N,K$ および (, ) からなる長さ $K$ の正しい括弧列 $S$ が与えられます。
• (, ) からなる長さ $N$ の文字列 $T$ のうち、以下の条件をすべて満たすものの数を $998244353$ で割った余りを求めてください。
  • $T$ の部分列であって、長さ $K$ の正しい括弧列であるものが存在する
  • $T$ の部分列であって、長さ $K$ の正しい括弧列であるもののうち、辞書順で最大のものは $S$ である

• なお、 (, ) からなる文字列の辞書順について、 ( は ) より小さい文字であるものとします。

• $K \leq N \leq 10^7$
• $2 \leq K \leq 5 \times 10^5$
• $N,K$ は整数
• $S$ は (, ) からなる長さ $K$ の正しい括弧列

あとちょっと。。。というところで時間切れ。C問題に浮気するんじゃなかった（結果論）。

サンプルが親切? で、ヒントを少しずつ出すように、サンプル1からサンプル4まで段階的に、 必要な考察ポイントを増やしながら用意してくれているような印象を受けた。

$S$ に、辞書順最大のものを変えない範囲で、合計 $N-K$ 文字を追加することを考える。
「先頭から、今、開いている括弧の数」を「深さ」として、深さ $0$ になる箇所で $S$ を分割する。
分割された（両端を含む）箇所を「隙間」とする。

   (())(()())()
        ↓
   (())   (()())   ()
 ^      ^        ^    ^   隙間

隙間以外に、文字は追加できない。（「(())」の2-3文字目の間に「)」を追加するなど、結果的に隙間に追加したのと同じと見なせるようなものは除く）

    ( ? ( ? ) ? ( ? ) ? )    どの ? に置くにしても（結果的に隙間に追加したのと同じのを除けば）
      _                      より階層を低くできる＝辞書順を大きくできる。
    ( ) (   )   (   )   )
→  ( ) (   )   (   )        どこに、どちらの向きで置いても、
                  _          置いた括弧を採用し、それと同じ向きの最も外の括弧を消した方が、
    (   (   )   ( ( )   )    必ず辞書順が大きくなる。
→      (   )   ( ( )   )

よって、隙間への追加のみを考える。

まず、例外から片付ける。
長さ $K$ のあらゆる正しい括弧列の中で辞書順最大のものは、「()()()()…」である。
もし $S$ がこれの場合、$T$ は「() が連続する箇所が $K/2$ 個以上ある文字列」であればなんでもよい。

重複を除いてこれを数えるには、$K/2+1$ 個ある隙間の、 前から $K/2$ 箇所には「()」を含まない文字列、 最後の隙間には任意の文字列を置くようなパターンを数えればよい。
「()」を含まない文字列とは、「)))(((」のように 閉じ括弧の連続→開き括弧の連続 という形となる。いずれかまたは両方が長さ0でもよい。 つまり、閉じ括弧の個数、開き括弧の個数、2つの値を決めることで文字列が決まる。

前から $K/2$ 箇所の隙間に合計何文字追加するか、を固定すると、

• $\displaystyle \sum_{x=0}^{N-K} {}_{K}H_{x} \times 2^{N-K-x}$

で、$O(N)$ で求められる。

$S$ のどこかには、深さ2以上の箇所が存在するとする。

隙間に「()」を含む文字列を追加することはできない。
もし追加すると、そちらを採用し、深さ2以上の箇所を1つ浅くした方が辞書順が大きくなる。
（辞書順最大にするためには、なるべく前の方にある深さ2以上の箇所を浅くすることになる）

S: (())    (()()) ()

T: (()) () (()()) ()
 → ()  () (()()) ()

T: (())    (()()) () ()   どこに () を追加しても、
 → ()     (()()) () ()   より辞書順の大きな部分列が作れてしまう。

各「隙間」におく文字列は、 必ず「)))(((」のように 閉じ括弧→開き括弧（いずれかまたは両方が長さ0でもよい）の文字列でなければならない。

さらに、先頭からはじめて深さが2以上になった箇所以降に追加する文字列は、全体でも部分列に「()」が含まれていてはいけない。

                はじめて深さ2以上になった箇所
                 ↓
S:   ()   ()   (()())   ()   (())
   ^    ^    ^        ^    ^      ^
                     ~~~~~~~~~~~~~~~
                     ここに追加する文字列は、全体でも () が含まれていてはいけない。

追加できる文字列の一例
S:   ()   ()   (()())   ()   (())
   ^    ^    ^        ^    ^      ^
  )(   ))(  )((      ))   ))(     ((((
  ~~   ~~~  ~~~      ~~~~~~~~~~~~~~~~~
  ↑   ↑   ↑       ↑ここは、全体が ))(( 型でないといけない
  ｜   ｜   ｜
  ここは、それぞれが ))(( 型ならよい

なぜなら、対応する括弧 (, ) が含まれていると、そちらを採用して深さ2以上の部分を1つ浅くした方が、辞書順が大きくなる。

S:   ()   ()   (()())   ()   (())
T:   ()   ()   (()()) ( ()   (()) )
                      ~           ~   正しい対応括弧を追加してしまうと
     ()   ()    ()()  ( ()   (()) )   こっちの方が辞書順が大きくなる。

以上が、$S$ に追加してよい文字の条件である。

「① $p=$はじめて深さ2以上になる箇所以前の隙間の個数」「② $q=$以降の隙間の個数」を調べる。

①は、$2p$ 箇所に置く文字数を決めれば良い。（$p$ 箇所それぞれに「)」と「(」2種類ずつ）

②は、$q+1$ 箇所に置く文字数を決めれば良い。（「)」と「(」が共存する隙間が1つ、あとは1種類ずつ）
ただし、どこで共存するかで $q$ 通りあるので $q$ 倍する。

さらに、それでは重複が発生するので除く。
隙間 $i$ では「)))」のみ、隙間 $i+1$ では「(((」のみ、というように共存する箇所がない場合、 「共存する箇所」を、$i$ としたものと $i+1$ としたもので、同じものが2回ずつ数えられてしまっている。

よって、以下が求める値となる。

• ${}_{2p+q+1}H_{N-K} \times q - {}_{2p+q}H_{N-K} \times (q-1)$

Python3

def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


def solve(n, k, s):
    MOD = 998244353
    facts, finvs = precompute_factorials(n, MOD)

    def nhr(n, r):
        return facts[n + r - 1] * finvs[r] % MOD * finvs[n - 1] % MOD

    if n == k:
        return 1

    k2 = k // 2
    if s == '()' * k2:
        pow2 = [1]
        for _ in range(n - k):
            pow2.append(pow2[-1] * 2 % MOD)

        ans = 0
        for x in range(n - k + 1):
            ans += nhr(k, x) * pow2[n - k - x]
            ans %= MOD
        return ans

    cum = [0]
    for c in s:
        if c == '(':
            cum.append(cum[-1] + 1)
        else:
            cum.append(cum[-1] - 1)
    m = cum.count(0) - 1

    p = 2
    for i in range(k2):
        if s[i * 2] == '(' and s[i * 2 + 1] == ')':
            p += 2
            m -= 1
        else:
            break

    ans = nhr(p + m + 1, n - k) * m - nhr(p + m, n - k) * (m - 1)
    ans %= MOD

    return ans


n, k = map(int, input().split())
s = input()
ans = solve(n, k, s)
print(ans)