AtCoder Grand Contest 076 A問題メモ

AtCoder Grand Contest 076

A1完の速解き勝負になるのは難易度傾斜的にさもありなんだが、みんなA解くの早いねえ。

A - Hamming-Distant Arrays

問題文

整数 $N$ が与えられます．
$1$ 以上 $N$ 以下の整数からなる長さ $N^2$ の整数列 $a,b$ に対し，その距離 $d(a,b)$ を次のように定義します．
- $d(a,b)=$「$a_i \neq b_i$ を満たす $i$ ($1 \leq i \leq N^2$) の個数」

今から，$1$ 以上 $N$ 以下の整数からなる長さ $N^2$ の整数列を $N$ 個作り，それらを $x_1,x_2,\cdots,x_N$ とおきます（順番も区別します）．
以下の条件を満たす $(x_1,x_2,\cdots,x_N)$ の個数を $998244353$ で割ったあまりを求めてください．
- $1$ 以上 $N$ 以下の整数からなる長さ $N^2$ の整数列 $y$ をどのようにとっても，ある $1 \leq i \leq N$ が存在し，$d(x_i,y) \geq N^2-N$ を満たす．

制約

$1 \leq N \leq 50$
入力はすべて整数

解法

問題文の意味を飲み込むのが難しい。
なんか長さ $N^2$ の数列を $N$ 個作って、

N=3
x1: 1 2 3 1 2 3 1 2 3
x2: 1 1 2 2 3 3 1 1 2
x3: 3 3 1 1 1 1 2 2 1

都合のいい $y$ を持ってきたときに、どの $x$ との距離も $N^2-N$ 未満であるような $y$ があってはいけない。
そうではない $x=(x_1,...,x_N)$ の個数を数えろと言っている。

$x$ が所与で、「$y$ を、どの $x_i$ との距離も $N^2-N$ 未満とするように決める」側の視点に立って考えてみる。
この行為を、条件達成を「阻止する」と呼ぶことにする。

x1: 1 2 3 1 2 3 1 2 3
x2: 1 1 2 2 3 3 1 1 2
x3: 3 3 1 1 1 1 2 2 1

全てのxiについて、そいつと同じ値を N+1 個以上作ると、阻止できる。

y : 1 1 1 1 1 3 1 2 2    o: yと同じ値であることを表す
x1: o         o o o      
x2: o o       o o   o    どの列も、N+1=4 個以上 o があるので
x3:     o o o     o      このx=(x1,x2,x3)は y によって「阻止された」

基本的には、各位置に付きなるべく多くの $x_i$ で共通している数字を選ぶのがよさそうである。
ただ、「$x_1$ と $x_2$ ばかり被って $x_3$ が足りない」みたいな場合は、最頻値で無くても足りない方と共通した数字を優先して選ぶこともある。

x1: 1 2 3 1 2 3 1 2 3
x2: 1 2 3 1 2 3 1 2 3
x3: 2 3 1 2 3 1 2 3 1

y : 1 2 3 1 3 1 2 3 1
x1: o o o o          
x2: o o o o
x3:         o o o o o

いろいろなケースを試すと、どうも「“o” を $N^2+N$ 個以上付けることが可能な $x$」なら、阻止可能っぽい。
言い換えると、（1列に1個、計 $N^2$ 個は必ず付けられるので）余分に $N$ 個の “o” を付けられたら阻止可能。

この時の“o”は特定の $x_i$ に偏って付いていてもよい。残りを適当に決めることで、全ての $x_i$ に $N+1$ 個以上ずつの“o”を付けられる。

略証

よって、以下のようなDPをすれば答えが求められそうである。

$\mathrm{DP}[i,j]:=y$ の $i$ 項目までを、“o”の数が最大限多くなるように決めた時、余分な“o”の個数が $j$ 個であるような $(x_1,...,x_N)$ の各 $i$ 項目までの決め方の数

$j$ は $0 \le j \lt N$ の範囲を管理すればよく、$\mathrm{DP}[N^2,*]$ の総和が答えとなる。

ただし、遷移が少し難しい。
「$i$ 項目で新規に $k$ 個被らせる」遷移をおこなう際、以下の値が必要となる。

$T(N,k):=1～N$ の値からなる長さ $N$ の数列のうち、最頻値の出現回数が $k$ 回であるようなものの個数

単純に二項係数などの式一発では求められそうもないが、小さい方を愚直に回すと、A019575 - OEIS が見つかる。
ありがたいことに求め方も乗っているので、この通りに実装すると、各 $k$ についての $T(N,k)$ が $O(N^4)$ で求まる。

$f(n,k,b):=$ 区別できる $b$ 個のボールを $n$ 個の箱に入れ、1つの箱に入っているボールの最大個数が $k$ 個以下である方法の個数
$n=0$ の時、
- $b=0$ なら $f(n,k,b)=1$
- $b \gt 0$ なら $f(n,k,b)=0$
それ以外の時、新しい箱にいくつのボールを入れるかを全通り試して遷移
- $\displaystyle f(n,k,b)=\sum_{i=0}^{\min(k,b)} \binom{b}{i} \times f(n-1,k,b-i)$
$f$ を $0 \le n,k,b \le N$ の範囲まで求め終わったら、以下で求められる
- $T(N,k)=f(N,k,N)-f(N,k-1,N)$

これで、$i→i+1$ へは以下のように遷移ができる。

各 $0 \le j \lt N, 1 \le k \lt N+1-j$ につき
- $\mathrm{DP}[i+1,j+k-1]←\mathrm{DP}[i,j] \times T(N,k)$

状態数 $O(N^3)$、遷移 $O(N)$、計 $O(N^4)$ でDPが回り、答え、つまり「余分な“o”の個数が $N$ 未満の $x$」の個数が求められる。

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):
    MOD = 998244353
    facts, finvs = precompute_factorials(n, MOD)
    ncr = lambda n, r: facts[n] * finvs[r] * finvs[n - r] % MOD

    f = [[[-1] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]

    def precalc(n, k, b):
        if n == 0:
            if b == 0:
                f[n][k][b] = 1
                return 1
            else:
                f[n][k][b] = 0
                return 0
        if f[n][k][b] != -1:
            return f[n][k][b]
        res = 0
        for i in range(min(k, b) + 1):
            res += ncr(b, i) * precalc(n - 1, k, b - i)
        res %= MOD
        f[n][k][b] = res
        return res

    t = [0] + [precalc(n, k, n) - precalc(n, k - 1, n) for k in range(1, n + 1)]

    dp = [0] * n
    dp[0] = 1
    # 何個の被りがあったか

    for _ in range(n * n):
        ndp = [0] * n
        for i in range(n):
            # i: 遷移元, j: 新しく被らせる個数
            for j in range(1, n + 1):
                k = i + j - 1
                if k >= n:
                    break
                ndp[k] += dp[i] * t[j]
                ndp[k] %= MOD
        dp = ndp

    ans = sum(dp) % MOD
    return ans


n = int(input())
ans = solve(n)
print(ans)

目次

AtCoder Grand Contest 076 A問題メモ

A - Hamming-Distant Arrays

問題文

制約

解法