AtCoder Japan Open -予選- (AtCoder Regular Contest 207 (Div.1)) A,B問題メモ

AtCoder Japan Open -予選- (AtCoder Regular Contest 207 (Div.1))

全ての問題が800点というフラット配点。
傾斜がある場合は「今更、配点の低い問題を解いても仕方ないので高い問題に賭けるか」みたいな 駆け引きがあるが、そういうのを気にせず解けそうな問題に注力すればよいのである意味、気が楽？

とはいえ、難しい問題しか無いのはきびちい。

A - Affinity for Artifacts

• 魔法使いのすぬけ君は $1$ から $N$ の番号がついた $N$ 個の魔法のランプを持っています。
  • $i$ 番目のランプのコストは $a_i$ です。
  • はじめ、どのランプも灯っていません。
• すぬけ君はMPという整数値を持っており、はじめは $X$ です。
  • すぬけ君がコスト $x$ のランプを灯すとMPが $x$ だけ減少します。
  • すぬけ君が $1$ つランプを灯すごとに、コストが $1$ 以上であるすべてのランプについてコストが $1$ 小さくなります。
• ランプを灯す順序は $N!$ 通りありますが、このうちMPが $0$ 未満になることがないような場合の数を $998244353$ で割ったあまりを求めてください。

• $1 \le N \le 100$
• $0 \le a_i \le 10^{9}$
• $0 \le X \le 10^9$
• 入力される値は全て整数

「DPで解くにしても “各コストのランプが何個ずつ残っているか” みたいな激重情報を持たないと遷移できなくない！？」 という考えから脱却できなかった。

でも、上手く持たせればできるんですねぇ。不思議。

似通いつつも、細かな点でいろいろな実装の違いがあるっぽい。

• 解説 - AtCoder Japan Open -予選- (AtCoder Regular Contest 207 (Div.1))
• Affinity for Artifacts (ARC207-A) - physics0523's 精進ログ
• AtCoder ARC #207 (AtCoder Japan Open -予選-) : A - Affinity for Artifacts - kmjp's blog

自分はTwitterで言及されていた箱根駅伝DPの考え方が一番理解しやすかった。 （理解しやすかっただけで、次にこのような問題が出たときに上手く解ける自信は無い）

• AOJ 2439 箱根駅伝 (JAG 夏合宿 2012 day3a-F) (600 点) - けんちょんの競プロ精進記録

ランプを付ける順番を0-indexedとし、「$0,1,2,...,N-1$ 番目に付ける」と表現するとする。

$i$ 番目に付けたランプは、その前に $i$ 個のランプを付けているので、$i$ 回、コストが $1$ 減る機会があった。
全体では、$\frac{N(N-1)}{2}$ 回、コストが $1$ 減る機会があったことになる。

この機会を全てのランプがフルに活かすのが最も総コストが低くなり、 （そもそも実現可能かはともかく）$\mathrm{sum}(A)-\frac{N(N-1)}{2}$ が理想的な最小コストとなる。
これが $X$ を上回っていたらそもそも無理なので0通り。

コストが減る機会を無駄にすることを「損失」と表現する。
$X-(理想的なコスト)$ が、“機会を無駄にしてよい最大数”（＝許容損失）となる。

「あるランプについてコストが $1$ 減る機会があったが、既に $0$ だったので減らされなかった」 ということが、全てのランプで延べて許容損失以下ならよい。

(例)  N=6 X=8
A = 2 1 4 8 1 4
↓
[sum(A) = 20]  -  [N(N-1)/2 = 15] = 5  が理想的な最小コスト。
X - 5 = 3  が許容損失。


順番  0 1 2 3 4 5
      4 2 1 1 8 4   例えばこのような順番で付けた場合、、、

損失  0 0 1 2 0 1   損失は合計4なので、この並べ方は条件を満たさない。

「損失が許容損失以内に収まるような並べ方」を数えることにする。

全てのランプの初期コストが $0$ だったとき、損失の合計は $\frac{N(N-1)}{2}$ が上限となる。
許容損失がこれ以上の場合は $N!$ が答えとなる。

中途半端な値の場合は、損失をDPのキーとする上で、「この損失以下」というパターン数をDPで数える。

「順番」を表す $N$ 頂点と、「ランプ」を表す $N$ 頂点のマッチングを考える。
両者の頂点番号は 0-indexed とする。

ランプの頂点 $j$ には、$A_j$ が書かれているとする。
$A_j$ は、$N-1$ 以上であれば「損失が発生し得ない」という点で同質なので、事前に $\min(N-1,A_i)$ としておく。

ランプ側頂点は、順番側頂点のうち、「自身に書かれた数」の $i$ の位置にまとまってあるものとする。

A = 2 1 4 8 1 4
↓
順番     0    1    2    3    4    5    （数字は頂点番号）
ランプ       1 1   2        4 4   5    （数字は頂点に書かれた数）

箱根駅伝DPの考え方を用いて、 $i=0,1,2,...$ と1つずつ進めていき、 「順番側頂点のうち、$i$ 以下のもの」と 「ランプ側の頂点のうち、書かれた数が $i$ 以下のもの」のみとのマッチングのさせ方を決めていく。

この時、「ランプ側の頂点 $j$ 個を未マッチングの状態で $i$ を1つ進めると、損失が $j$ 増加する」といえる。
（$A_j$ が書かれたランプ頂点は、$A_j+1$ 番目以降、順番が1つ後になるたびに損失が1ずつ増加する）

よって、以下のDPで状態を管理できる。

• $\mathrm{DP}[i,j,k]:=$
  • $i$ 以下の順番側頂点と、書かれた数が $i$ 以下のランプ側頂点のマッチングを決め、
  • ランプ側の未マッチング頂点が $j$ 個で、
  • これまでに確定した損失が $k$ の場合のパターン数

$\mathrm{DP}[-1,0,0]=1$ からはじまり（便宜上、$i=0$ の更に1つ前を $i=-1$ と表現）、 $\mathrm{DP}[N-1,0,許容損失以下]$ の値の合計が、答えとなる。

$(i-1,j,k)$ から $(i,*,*)$ への遷移では、 新しく「順番側の頂点 $i$」と「$A_j=i$ であるいくつかのランプ側頂点」が追加される。 これらのマッチングを考える。

順番   ○    ○    ○   |    i     ┐
         ＼   ,---'     |          ├追加された頂点
ランプ     ○○○  ○   | i i i i  ┘
       <----------------|
    ここより前の頂点同士の
    マッチングは決定済み

• 「$i$ 未満の未マッチングの順番側頂点」と「いま追加されたランプ側頂点」のマッチング
  • $x$ を、「$A_j=i$ であるランプ側頂点の個数」とする。
  • $y$ を、「i未満の未マッチング順番側頂点の個数」とする。
  • $r=0,1,...,\min(x,y)$ の範囲で、マッチングするペア数を固定する。
  • ${}_x\mathrm{C}_r \times {}_y\mathrm{C}_r \times r!$ のペアの作り方がある。

• 「順番側頂点 $i$」と「ランプ側の未マッチング頂点」のマッチング
  • $w$ を、ランプ側の「$i-1$ 以下の未マッチング頂点」および「先ほどマッチングに使用されなかった $i$ の未マッチング頂点」の個数とする。
  • この中の1つを順番側頂点 $i$ とマッチングする場合、$w$ 通りの選び方がある。

よって、$(i-1,j,k)$ および $r$ を固定すると、

• 順番側頂点 $i$ をマッチングする場合
  • $\mathrm{DP}[i,j+x-r-1,k+j+x-r-1] += \mathrm{DP}[i-1,j,k] \times {}_x\mathrm{C}_r \times {}_y\mathrm{C}_r \times r! \times w$
• しない場合
  • $\mathrm{DP}[i,j+x-r,k+j+x-r] += \mathrm{DP}[i-1,j,k] \times {}_x\mathrm{C}_r \times {}_y\mathrm{C}_r \times r!$

このように遷移する。

これは、$i,j$ が $O(N)$、$k$ が $O(N^2)$ の範囲を動き、 遷移は $r$ をイテレートするものの「全ての $i$ を通して $O(N)$」なので、 全体としては$O(N^4)$ で求められる。

Python3

import os
import sys

import numpy as np


def solve(inp):
    n, x = inp[:2]
    aaa = inp[2:]
    MOD = 998244353

    # 許容される損失の最大値
    ideal_cost = aaa.sum() - n * (n - 1) // 2
    allowable_loss = x - ideal_cost
    if allowable_loss < 0:
        return 0

    count = np.zeros(n, np.int64)
    for a in aaa:
        count[min(a, n - 1)] += 1

    pascal = np.zeros((n + 1, n + 1), np.int64)
    permutations = np.zeros(n + 1, np.int64)
    pascal[0, 0] = 1
    permutations[0] = 1
    for i in range(n):
        permutations[i + 1] = permutations[i] * (i + 1) % MOD
        for j in range(i + 1):
            pascal[i + 1, j] += pascal[i, j]
            pascal[i + 1, j] %= MOD
            pascal[i + 1, j + 1] += pascal[i, j]
            pascal[i + 1, j + 1] %= MOD

    max_k = n * (n - 1) // 2 + 1
    dp = np.zeros((n + 1, max_k), np.int64)

    under_i = 0
    dp[0, 0] = 1
    for i in range(n):
        ndp = np.zeros_like(dp)
        for j in range(max(0, under_i - i), under_i + 1):
            for k in range(max_k):
                if dp[j, k] == 0:
                    continue
                # 順番側の未マッチング数
                rem = i - (under_i - j)
                for l in range(min(rem, count[i]) + 1):
                    # l: i 番目より前とマッチングする、ちょうどコスト i のランプの個数
                    # 選び方
                    ch = pascal[count[i], l] * pascal[rem, l] % MOD * permutations[l] % MOD
                    # さらにコスト i 以下のランプを、ちょうどi番目とマッチングさせるかどうかで場合分け。
                    # コスト i 未満の未マッチングおよびちょうどコスト i から1つ選んでマッチングさせる
                    nj = j + count[i] - l - 1
                    if nj >= 0 and k + nj < max_k:
                        ndp[nj, k + nj] += dp[j, k] * ch % MOD * (nj + 1)
                        ndp[nj, k + nj] %= MOD
                    # マッチングさせない
                    nj = j + count[i] - l
                    if nj >= 0 and k + nj < max_k:
                        ndp[nj, k + nj] += dp[j, k] * ch
                        ndp[nj, k + nj] %= MOD
                        # print('not i (', nj, ',', k + nj, ') add', dp[j, k], '*', ch)
        under_i += count[i]
        dp = ndp

    ans = dp[0, :allowable_loss + 1].sum()
    ans %= MOD
    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 - Balanced Neighbors 2

• 整数 $N$ が与えられます。
• 頂点に $1$ から $N$ の番号がついた $N$ 頂点の単純連結無向グラフであって、以下の条件を満たすものが存在するかどうかを判定し、存在するならばその例を $1$ つ示してください。
  • ある整数 $X$ が存在して、任意の頂点 $v$ について、$v$ から $1$ 回または $2$ 回辺を辿ることで到達できる $v$ 以外の頂点の番号の総和は $X$ となる

• $2 \le N \le 200$
• 入力される値は全て整数

このような構築問題はとっとと愚直解法で実験して法則性をエスパーするのが速い、気がする。
まぁ、愚直解法が難しく少し $N$ が大きくなると求めきれなかったり、 そもそも法則が複雑でエスパーできない可能性もあるので絶対ではないが、、、

すぐ思いつく愚直解法としては、

• $N$ 頂点の完全グラフの $N(N-1)/2$ 本の辺集合の、全ての部分集合 $2^{N(N-1)/2}$ を順に調べる。
• 全体が連結か確認する。
• Froyd-Warshall を使って、辺1本を距離1とした各頂点間最短距離を求める。
• 各 $i$ につき、最短距離が $1$ または $2$ の頂点番号を合計する。
• 全ての頂点で合計が同じになるか確認する。

という、$O(2^{N(N-1)/2}N^3)$ の解法がある。
これを実装すると、$N=7$ まではなんとか、$N=8$ も考察中に回し続けておけば1つくらいは見つかる。

すると、$N \le 5$ の場合は解が存在しないことがわかる。

$N \ge 6$ の場合、二部グラフをベースとした構築方法がある。

①   ②   ③   ④    ←N/2 以下の頂点を上に

⑤   ⑥   ⑦   ⑧    ←N/2 より大きい頂点を下に

これの完全二部グラフの辺のうち、「合計が N+1 になる辺」だけ除外する。
①と⑧、②と⑦、③と⑥、④と⑤

①を考えると、以下で辿り着ける。

• ⑤⑥⑦へは直接辺があるため距離1
• ②③④へは、⑤⑥⑦のいずれかを経由すれば距離2
• ⑧へは距離3かかる（二部グラフなので、相手側頂点への距離は奇数だが、1ではないので3以上は確定する）

よってどの頂点も、全ての頂点番号 $1～N$ の総和のうち「自身」と「自身と足して $N+1$ になる頂点」だけが加算されないので、 全ての頂点で $X=\frac{N(N+1)}{2}-(N+1)$ と等しくなる。

   ,---⑨----,
  /   /  \    \
①   ②   ③   ④

⑤   ⑥   ⑦   ⑧

頂点 $N$ を上に君臨させ、$1～(N-1)/2$ へと辺を張る。

下側は、さっきと同様に完全二部グラフから、今度は「合計が $N$ になる辺」だけ除外する。

こうすると、$X=\frac{N(N+1)}{2}-N$ が成立する。

Python3

def naive(n):
    from atcoder.dsu import DSU

    print(f'Start: {n=}')

    edges = [(i, j) for i in range(n) for j in range(i + 1, n)]
    m = len(edges)
    INF = 1 << 60
    for bitset in range(1 << m):
        dsu = DSU(n)
        dists = [[INF] * n for _ in range(n)]
        for i in range(n):
            dists[i][i] = 0
        li = 0
        while bitset:
            if bitset & 1 == 1:
                u, v = edges[li]
                dsu.merge(u, v)
                dists[u][v] = 1
                dists[v][u] = 1
            bitset >>= 1
            li += 1
        if dsu.size(0) != n:
            continue
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j])
        costs = [0] * n
        for i in range(n):
            for j in range(n):
                if i != j and dists[i][j] <= 2:
                    costs[i] += j + 1
        c0 = costs[0]
        if all(c0 == c for c in costs):
            print(f'Found: {dists=}')
            print(f'       {costs=}')


def solve(n):
    if n <= 5:
        return None
    if n % 2 == 0:
        ans = []
        h = n // 2
        banned = 1 + n
        for i in range(1, h + 1):
            for j in range(h + 1, n + 1):
                if i + j == banned:
                    continue
                ans.append((i, j))
        return ans
    else:
        ans = []
        h = n // 2
        banned = n
        for i in range(1, h + 1):
            for j in range(h + 1, n + 1):
                if i + j == banned:
                    continue
                ans.append((i, j))
        return ans


n = int(input())
ans = solve(n)
if ans is None:
    print(-1)
else:
    print(len(ans))
    print('\n'.join(f'{i} {j}' for i, j in ans))