World Artificial Intelligence Programming Contest日本国内最終予選 A,B問題メモ

World Artificial Intelligence Programming Contest日本国内最終予選

他人の金¹⁾で行く東京旅行は楽しかった。主催者・運営に感謝。

A - Take Mod for All

• 長さ $N$ の非負整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます．
  • ここで，$2 \leq N$ および $A_1 \lt A_2 \lt \cdots \lt A_N$ が保証されます．
• あなたは今から以下の操作を $1$ 回以上行います．
  • 正整数 $x$ を選ぶ．そして，すべての $i$ ($1 \leq i \leq N$) について，$A_i$ の値を，$A_i$ を $x$ で割ったあまりで置き換える．

• ここで，操作列のスコアを，操作で使用した $x$ の最小値と定義します．
• あなたの目標は，$A$ のすべての要素が等しい状態にすることです．
• 目標を達成する操作列のスコアとしてあり得る最大値を求めてください．

• $1$ つの入力につき，$T$ ケースを解いてください．

• $1 \leq T \leq 125000$
• $2 \leq N \leq 250000$
• $0 \leq A_1 \lt A_2 \lt \cdots \lt A_N \leq 10^9$
• $T$ ケースにわたる $N$ の総和は $250000$ 以下
• 入力はすべて整数

サンプルにヒントがあって、答えは $A_1$ か $A_2-A_1$ のいずれかになっている。
ひとまず、この2つが答えとなる場面を考えてみる。

$A_1$ が答えとなるようなケースは、$A_N,A_{N-1},...$ と順に操作していく場合が該当し、全てが $0$ に揃う。

答えがそれ以上となる場合、$A_1$ は初期の $A_1$ のまま残る。よって、他を $A_1$ に合わせにいくことになる。

x\A  10  30  35  50  70

60   10  30  35  50  10  ←基本的に、大きい方から 
40   10  30  35  10  10  ←Ai-A1 で割っていくと良さそうだが、、、

25   10   5  10  10  10  ←A[i-1] と A[i] が近いと、
                           A[i]を揃えるとき、A[i-1]が巻き添えを食らう。

2数 $a,b$（$a \lt b$）を同じ数 $x$ で割ったときのあまり $a',b'$ を考えると、 商が同じなら差分 $b'-a'$ はそのまま維持される。
あまりを同じ数に揃えたければどこかで商が異なるような割り算をしなければならないが、 その時、$b'$ は $b-a$ 以上にはできない。

よって、全ての隣り合う要素の差分が $A_1$ より大きいときのみ、$A_2-A_1$ が達成できる。

Python3

def solve(n, aaa):
    ans = aaa[0]
    ans2_ok = True
    for i in range(1, n - 1):
        if aaa[i + 1] - aaa[i] <= aaa[0]:
            ans2_ok = False
            break
    if ans2_ok:
        ans = max(ans, aaa[1] - aaa[0])
    return ans


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

B - Prepare the Winning Game

• $1$ から $N$ までの番号のついた $N$ 頂点からなる重み付き完全無向グラフ $G$ があります．
• 頂点 $i$ と頂点 $j$ ($1 \leq i \lt j \leq N$) を結ぶ辺の重みは $C_{i,j}$ です．
• Alice と Bob はこれからゲームをします．
• まずゲームの準備として，Bob が以下の操作を行います．
  • $G$ から $0$ 本以上の辺を削除する．ここで削除した辺の重みの総和をコストと呼ぶことにする．
  • 頂点のうち好きな $A$ 個を選び，そこに A と書き込む．残りの $N-A$ 個に B と書き込む．
  • 好きな頂点を $1$ 個選び，そこに駒を $1$ つ置く．

• 準備が終了したらゲームを開始します．
• Alice から始めて二人のプレイヤーは交互に手番をプレイします．各手番では，次のいずれかの行動ができます．
  • ゲームを終了する．
  • 駒を隣接頂点へと動かす．ただし，今までに駒が置かれたことのある頂点へは動かせない（ゲーム開始時に駒が置かれていた頂点にも動かせない）．

• ゲームが終了した瞬間に駒が置かれていた頂点に書かれた文字が A なら Alice の勝ち，B なら Bob の勝ちです．
• Bob は自分に必勝法が存在するようにゲームを準備したいです．
• そのために必要なコストの最小値を求めてください．

• $1$ つの入力につき，$T$ ケースを解いてください．

• $1 \leq T \leq 100$
• $2 \leq N \leq 20$
• $1 \leq A \leq N-1$
• $0 \leq C_{i,j} \leq 10^9$
• $T$ ケースにわたる $N^2$ の総和は $20^2$ 以下
• 入力はすべて整数

サンプル（4つめのケース）がヒントになる。

答えが合うような辺の選び方を探索すると（候補は多いが、枝刈りもしやすい）、 削除している辺は $(1,3,9,10)$ と $(6,7,8)$ の完全二部グラフとなることが分かる。

つまり、以下のようになっている。この盤面から $B$ のいずれかにコマを置くと、Bobが勝てることが分かる。

    B           A         A       同じ(括弧)内は完全グラフ
(1,3,9,10)---(2,4,5)---(6,7,8)    ( )--( )で結ばれたグループ間は全頂点ペア間に辺がある

AliceもBobも、自ら相手の頂点に移動させたら、相手は即座にゲームを終了させて勝利してしまうので、常に自分の頂点に移動させなければならない。 ゲームはBにコマが置かれた状態から開始し、→A→B→A→… のように進むことになる。Aliceの手番でBにいる時に、そこから移動できるA頂点が尽きてしまうと、Bobは勝利できる。

上例では、左の島から開始し、Aliceはそこから繋がっている真ん中の島のいずれかにコマを進める。
しかしBobは次の手番で左の島に戻すので、最終的にAliceは移動できる頂点が無くなり、Bobが勝つ。

つまり、以下のような構造を作れたら、Bobは勝ちである。

(x個のB)---(x-1個のAと)---(残りのA)
           ( 残りのB  )

左の島に全てのBを置く必要は無く、$x$ 個以外の頂点がいずれも他との削除コストが高ければ、$x$ 個だけ左の島に置くのが最適になることもある。

よって、

• $x=1,2,...,N-A$ を固定
  • Bにする頂点 $x$ 個と、Aにする頂点 $N-B-x+1$ 個の完全二部グラフの辺を削除するコストを計算する。
• $N$ 個中 $x$ 個選ぶ組合せを全探索し、Bにする頂点の選び方を固定
  • 選ばれていない $A$ 個の頂点それぞれで、選ばれた $x$ 個の頂点とのコストの総和を計算
  • 総和が小さい方から $N-B-x+1$ 個を、$x$ 個との辺を削除する頂点として採用

以上の全探索で、$O(N^22^N)$ で答えを求められる。

$x \gt N-B-x+1$ なら、$N-B-x+1$ 個側の頂点の組を全探索するように切り替えれば少し高速になる。

Python3

def analyze(n, a, costs):
    ccc = []
    for i in range(n):
        for j in range(i + 1, n):
            ccc.append((costs[i][j - i - 1], i, j))
    ccc.sort()

    def sub(ci, rem):
        if rem == 0:
            return []
        c, i, j = ccc[ci]
        if c > rem:
            return None
        result = sub(ci + 1, rem - c)
        if result is not None:
            result.append((c, i, j))
            return result
        result = sub(ci + 1, rem)
        if result is not None:
            return result
        return None

    result = sub(0, 137097802)
    print(result)


def solve(n, a, costs):
    b = n - a
    if b > a:
        return 0

    INF = 1 << 60
    matrix = [[INF] * n for _ in range(n)]
    vvv = [[] for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            c = costs[i][j - i - 1]
            matrix[i][j] = matrix[j][i] = c
            vvv[i].append((c, j))
            vvv[j].append((c, i))
    for i in range(n):
        vvv[i].sort()

    # (B1個)-(残りB)-(A)
    ans1 = INF
    for i in range(n):
        ans1 = min(ans1, sum(sorted(matrix[i])[:a]))

    # x<=B として
    # (x個のB)-(x-1個のAと残りB)-(残りA)
    def bit_combination(n, k):
        """ n bit中、k bit が立った整数をイテレート """
        limit = 1 << n
        v = (1 << k) - 1
        while v < limit:
            yield v
            x = v & -v
            y = v + x
            v = (v & ~y) // x >> 1 | y

    def iter_bit(bitset):
        while bitset:
            lsb = bitset & -bitset
            yield lsb
            bitset ^= lsb

    full_bit = (1 << n) - 1
    ans2 = INF
    for x in range(2, b + 1):
        y = x - 1
        z = n - y - b
        if z <= 0:
            continue
        if x > z:
            x, z = z, x
        for bitset in bit_combination(n, x):
            bbb = [ib.bit_length() - 1 for ib in iter_bit(bitset)]
            aaa = [0] * n
            for i in bbb:
                aaa[i] = INF
            for ib in iter_bit(bitset ^ full_bit):
                i = ib.bit_length() - 1
                for j in bbb:
                    aaa[i] += matrix[i][j]
            aaa.sort()
            tmp = sum(aaa[:z])
            ans2 = min(ans2, tmp)

    ans = min(ans1, ans2)

    return ans


t = int(input())
for _ in range(t):
    n, a = list(map(int, input().split()))
    costs = list(list(map(int, input().split())) for _ in range(n - 1))
    ans = solve(n, a, costs)
    print(ans)