AtCoder Regular Contest 218 A,B,C問題メモ

AtCoder Regular Contest 218

A - Many Sets

• 長さ $M$ の正整数列が $N$ 個与えられます。$i$ 個目の正整数列は $A_i=(A_{i,1},A_{i,2},\dots,A_{i,M})$ です。
• これら $N$ 個の正整数列から $1$ 個ずつ要素を選ぶ方法は $M^N$ 通りあります。
• その全てに対する「選んだ要素に含まれる整数の種類数」の総和を $998244353$ で割った余りを求めてください。

• $1 \le N,M \le 500$
• $1 \le A_{i,j} \le NM$
• 入力は全て整数

以下のDPを定義する。ただし、各数列から $1$ 個ずつ要素を選ぶ際は一様ランダムに選ばれるものとする。

• $\mathrm{DP}[i,a]:=i$ 番目の数列までで、要素 $a$ が1回以上選ばれている確率

初期値 $\mathrm{DP}[0,*]$ は全て $0$ とする。

$i$ 番目の数列に $a$ が $c$ 個出現しているとすると、

• $\mathrm{DP}[i,a]+=(1-\mathrm{DP}[i-1,a]) \times \dfrac{c}{M}$

のように更新できる。 つまり、（$i-1$ までで $a$ が選ばれていない確率）×（$i$ で $a$ が選ばれる確率）だけ、$a$ の選ばれている確率が増える。

$i$ 番目の数列に出現しない要素に変化はないので、出現する箇所のみ更新すればよい。
また、実装の上では $i$ の次元は省略し、$\mathrm{DP}'[a]$ を直接更新していってよい。

最終的に期待値は $\sum_a \mathrm{DP}[N,a]$ となり、問題の答えはそれに $M^N$ をかけたものとなる。

計算量は $O(NM)$

Python3

from collections import Counter


def solve(n, m, aaas):
    MOD = 998244353
    INV_M = pow(m, MOD - 2, MOD)
    dp = [0] * (n * m + 1)
    for aaa in aaas:
        for a, c in Counter(aaa).items():
            dp[a] += (1 - dp[a]) * c * INV_M
            dp[a] %= MOD
    ans = sum(dp) * pow(m, n, MOD)
    ans %= MOD
    return ans


n, m = list(map(int, input().split()))
aaa = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, m, aaa)
print(ans)

B - All Minus

• 黒板に $N$ 個の非負整数 $A_1,A_2,\dots,A_N$ が書かれています。
• Alice と Bob がゲームをします。Alice から始めて以下の操作を交互に行い、黒板に書かれている整数を $0$ 個にした方が勝ちです。
  • 操作を行う時点で黒板に書かれている最小の非負整数を $m$ とする。
    • $m \gt 0$ のとき、$1$ 以上 $m$ 以下の正整数 $x$ を選ぶ。黒板に書かれている全ての整数をそれぞれ今の値から $x$ 引いた数に書き換える。
    • $m = 0$ のとき、黒板に書かれている $0$ のうち、$1$ 個以上を削除する。
• 両者が勝つために最善な行動をしたとき、勝つのがどちらか判定してください。

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

• $1 \le T \le 2 \times 10^5$
• $1 \le N \le 2 \times 10^5$
• $0 \le A_i \le 10^9$
• 全てのテストケースに対する $N$ の総和は $2 \times 10^5$ 以下
• 入力は全て整数

$A$ は昇順にソート済みとする。

棒グラフを描いてみると、ゲームで取れる行動の良い言い換えが見える。

A = (1, 2, 4, 4, 7)

→┝┓
  ├┻┓
  ├─┻━┓
  ├───┨
  ├───┻━━┓
  ├──────┛
                ↓

棒グラフの左上（矢印→の先）にコマを置き、以下のルールに沿って交互に動かし、右下↓に到達させた方が勝ちとなる。

• 太く示した、棒の上と右の線上のみ動ける
• 1回の移動の中で方向転換禁止
• 必ず1は進む

方向転換まで残り距離 $1$ なら、動かし方に選択の余地がない。
$A=(1,2,3,4,5,6)$ のような階段だと、両者とも選択の余地はないまま、交互に動かすだけになる。

しかし、$A=(1,2,4,4,7)$ のように、ヨコやタテに距離 $2$ 以上が発生すると、その手番のプレイヤーは

• その距離を全て消費しきる
• その距離を $1$ だけ残して消費しきる

を自由に選択することで、攻守（？）を交替できる。

つまり、「次に出現する、距離 $2$ 以上の辺」があるなら再びそれを自分の手番にするように、 ないなら最後に自分が勝つように選択できる。

最初からシミュレーションして、

• 最初に距離 $2$ 以上の辺に遭遇した手番のプレイヤーが勝利
• 最後まで1つも無いなら、動かし方は一意なのでシミュレーションの結果が答え

$A$ が $0$ を含む場合はAliceは初手↓方向に動かすので注意。

Python3

import random
from collections import Counter


def naive(n, aaa, debug_print=True):
    aaa = tuple(sorted(aaa))
    memo = {}

    def sub(aaa, i):
        if (aaa, i) in memo:
            return memo[aaa, i]
        if i == n:
            return False
        if aaa[i] == 0:
            l = i
            while l < n and aaa[l] == 0:
                res = sub(aaa, l + 1)
                if res == False:
                    memo[aaa, i] = True
                    return True
                l += 1
            memo[aaa, i] = False
            return False
        a = aaa[i]
        for x in range(1, a + 1):
            new_aaa = (0,) * i + tuple(a - x for a in aaa[i:])
            res = sub(new_aaa, i)
            if res == False:
                memo[aaa, i] = True
                return True
        memo[aaa, i] = False
        return False

    ans = sub(aaa, 0)

    if debug_print:
        print(f'{n=} {aaa=}')
        print(memo)

    return ans


def solve(n, aaa):
    ans = True
    cnt = Counter(aaa)

    if 0 in cnt:
        if cnt[0] >= 2:
            return True
        ans = False
        del cnt[0]

    p = 0
    for a in sorted(cnt.keys()):
        c = cnt[a]
        if a - p >= 2:
            return ans
        ans = not ans
        if c >= 2:
            return ans
        ans = not ans
        p = a

    ans = not ans
    return ans


def check():
    n = 6
    lim = 6
    for _ in range(100):
        aaa = random.choices(range(lim + 1), k=n)
        ans1 = solve(n, aaa)
        ans2 = naive(n, aaa, False)
        if ans1 == ans2:
            continue
        print(f'==== NG ==== {ans1=} {ans2=}')
        print(f'{n}')
        print(*aaa)
    print('FINISH')

# check()

t = int(input())
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    ans = solve(n, aaa)
    if ans:
        print('Alice')
    else:
        print('Bob')

C - Amidakuji

• この問題はインタラクティブな問題です。
• 正整数 $N$ が与えられます。
• 正整数 $m$ と $m$ 個の $(1,2,\dots,N)$ の順列を好きに決め、出力してください。
  • このうち $i$ 個目の順列を $P_i=(P_{i,1},P_{i,2},\dots,P_{i,N})$ とします。
  • これは「$k→P_{i,k}$ という置換」を表すとし、「置換 $i$」と呼ぶこととします。
• その後、$(1,2,\dots,N)$ の順列 $Q=(Q_1,Q_2,\dots,Q_N)$ が与えられます。
• 以下の条件を全て満たすような正整数列 $A=(A_1,A_2,\dots,A_k)$ を出力してください。
  • $0 \le k \le 2N^2$
  • $A$ の要素は全て $1$ 以上 $m$ 以下
  • 数列 $R=(1,2,\dots,N)$ に対して、$i = 1,2,\dots,k$ の順に置換 $A_i$ を行うと $R = Q$ となる。

• 上記の問題を $Q$ によらずに正解する上での最小の $m$ を $m_{\min}$ とします。あなたの出力する $m$ は $m_{\min}$ でなければなりません。

• $3 \le N \le 500$
• $Q$ は $(1,2,\dots,N)$ の順列
• 入力は全て整数

少し問題がややこしい。$Q$ が最初に分かってしまうと自明すぎるので、最初に使う置換を宣言させられる。

（言うて600点問題というメタ読みも含め） そこまで複雑な構築にはならず、ある程度 $m$ 個の数列は規則的なものになるはずと当たりを付ける。

$m$ をどこまで減らせるか考えたときに、 はじめ「$m=N-1$ とし、$i=1,2,...,N-1$ につき $i$ と $i+1$ のみをswapするもの」が思い浮かぶ。

だが、それを使った構築を考えだすと、よりよい $m=2$ が必ず達成可能であることに気付く。

1. $1～N-1$ をローリングし、$N$ はそのまま動かない置換
2. $N-1$ と $N$ をswapし、他は動かない置換

要は、$1～N-1$ をループ式のベルトコンベアと見なし、 要素を $N$ にストックしては好きな位置に戻すことを繰り返して、任意の並びを作れる。

1つの要素を好きな位置に持っていくために

• 最大 $N-1$ 回のローリングで、ターゲットを $N-1$ に持ってくる
• swapして $N$ にストック
• 最大 $N-1$ 回のローリングで、挿入したい位置に持ってくる
• swap

計 $2N$ で達成可能となる。全体で約 $2N^2$ と見積もれ、まさに問題の条件通りなので確信度が高まる。

まずは考えやすくするため、「$(1,2,...,N)→Q$ にする置換列」と「$S→(1,2,...,N)$ にする置換列」が 同じになる $S$ を特定し、後者で考える。$S$ は、$Q$ の逆順列（indexと値が逆転したもの）とすればよい。

その後、$i=2,3,...,N-1$ の順に、要素 $i$ を $i-1$ の直後に持ってこさせる。つまり、

• $i=2,3,...,N-1$ の順に、
  • 要素 $i$ がストック（位置 $N$）になければ、
    • 位置 $N-1$ までローリングする
    • swapする
  • 要素 $i-1$ を位置 $N-2$ までローリングする
  • swapする
• 最後に要素 $1$ が位置 $1$ に来るまでローリングする

とすることで構築できる。各操作は、実際に数列をその通りにシミュレーションして確かめて $O(N^3)$ なので十分間に合う。

なお、必要は無いが、工夫すれば最悪操作回数を約 $2N^2→N^2$ に減らせはする。
最初に $1$ の位置から $2～N-1$ の相対的な挿入位置は決められるので、$i=2,3,...$ の順ではなく、 現在ストックに入った順に挿入（その際のswapによって新たにストックに入った要素をまた挿入……）していくと、可能となる。

Python3

def solve(n):
    print(2)
    roller = list(range(2, n)) + [1, n]
    print(*roller)
    swapper = list(range(1, n - 1)) + [n, n - 1]
    print(*swapper)

    def roll(aaa):
        return aaa[1:-1] + [aaa[0], aaa[-1]]

    def swap(aaa):
        aaa[-2], aaa[-1] = aaa[-1], aaa[-2]
        return aaa

    qqq = list(map(int, input().split()))
    bbb = [0] * n
    for i, q in enumerate(qqq):
        bbb[q - 1] = i

    ans = []
    if bbb.index(0) == n - 1:
        ans.append(2)
        bbb = swap(bbb)

    for k in range(1, n - 1):
        i = bbb.index(k)

        if i < n - 1 and bbb[(i - 1) % (n - 1)] == k - 1:
            continue

        if i < n - 1:
            while bbb[-2] != k:
                ans.append(1)
                bbb = roll(bbb)
            ans.append(2)
            bbb = swap(bbb)

        while bbb[-3] != k - 1:
            ans.append(1)
            bbb = roll(bbb)
        ans.append(2)
        bbb = swap(bbb)

    while bbb[0] != 0:
        ans.append(1)
        bbb = roll(bbb)

    print(len(ans), *ans)


n = int(input())
solve(n)