NECプログラミングコンテスト2021(AtCoder Beginner Contest 229) F,G,H問題メモ

NECプログラミングコンテスト2021(AtCoder Beginner Contest 229)

なぜかめっちゃ眠かった。

F - Make Bipartite

問題

$N+1$ 頂点の無向グラフ
辺は、以下の $2N$ 本
- $i=1,2,...,N$ について、頂点 $0$ と $i$ を結ぶ重み $A_i$ の辺
- $i=1,2,...,N$ について、頂点 $i$ と $i+1$ を結ぶ重み $B_i$ の辺
  - ただし頂点 $N+1$ は $1$ を表すとする
辺を削除して全体を二部グラフにしたい
削除する必要のある最小の辺の重みの総和を求めよ
$3 \le N \le 2 \times 10^5$

解法

グラフに見せかけたDP。

グラフは車輪のような形になる。

  ①--②
 / \  / \
⑥--⓪--③
 \ /  \ /
  ⑤--④

二部グラフは、頂点を2グループに分け「同じグループの間には辺が張られていない」状態ならよい。

グループAとBに分け、頂点0の入る方をグループAと決めてしまうとして、頂点 $0～i-1$ で成立している状態に $i$ を加えることを考える。

$i$ をAに入れるなら、$A_i$ は削除しないといけない
$i$ を $i-1$ と同じグループに入れるなら、$B_{i-1}$ は削除しないといけない
その他の辺は削除しなくてよい

ただし、$i=1$ のとき、2番目の条件は「$1$ と $N$ が同じグループなら $B_N$ は削除」となる。
このループ部分（$B_N$ の辺）がややこしいので、頂点1に関しては2番目の条件は一端無視する。

頂点 $i$ を加えるときの条件から、$i-1$ の入ったグループがどっちだったかさえわかれば、削除しなければならない辺が決まる。

（仮）$DP[i][g]=$ 頂点 $1～i$ を考え、$i$ の入ったグループが $g=A/B$ の時の、削除すべき辺のコストの最小値

また無視していた $B_N$ については、$DP[N]$ まで計算した後で「頂点 $1$ と $N$ をそれぞれどちらに入れたか」がわかれば、削除しなければならないかが決まる。

従って、そこでも場合分けしてやればよい。

$DP[i][f][g]=$ 頂点 $1～i$ を考え、頂点 $1$ は $f=A/B$ に入れ、$i$ の入ったグループが $g=A/B$ の時の、削除すべき辺のコストの最小値

最後に、$DP[N][A][A]$ および $DP[N][B][B]$ には $B_N$ を加算してやれば、全ての辺を考慮できたことになる。

$DP[N]$ の中の4つの値の最小値が答え。

Python3

n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))

dp00 = aaa[0]
dp01 = 1 << 60
dp10 = 1 << 60
dp11 = 0
for a, b in zip(aaa[1:], bbb):
    ndp00 = min(dp00 + a + b, dp01 + a)
    ndp01 = min(dp00, dp01 + b)
    ndp10 = min(dp10 + a + b, dp11 + a)
    ndp11 = min(dp10, dp11 + b)
    dp00 = ndp00
    dp01 = ndp01
    dp10 = ndp10
    dp11 = ndp11

dp00 += bbb[-1]
dp11 += bbb[-1]

ans = min(dp00, dp01, dp10, dp11)

print(ans)

G - Longest Y

問題

'.' と 'Y' からなる文字列 $S$ が与えられる
$K$ 回まで、隣接する文字をswapできる
'Y' をなるべく長く連続させたいとき、可能な最大長を求めよ
$2 \le |S| \le 2 \times 10^5$

解法

いくつかの気付きと前準備と、添字をバグらせない丁寧さが必要。

答えを二分探索できないか考える。
Yを $x$ 個連続させられるかどうかを $O(|S|)$ くらいで判定できれば可能そう。

$x$ を固定して考える。

Y同士を入れ替える操作は無駄なので、$S$ の中のYの並び順は最初から最後まで変わらないとしてよい。
$S$ の中で $i$ 番目に出現するYのことを $Y_i$ と表すとする。

連続させる一番左のYを $Y_i$ としたら、一番右は $Y_{i+x-1}$ に決まる。

この区間のYを連続させるためのswap回数を求めたい。

基準となるYを1個決める。 基準のYは動かさず、周囲のYを持ってくることを考える
Y..Y.YY....[Y].YY

基準Yから左右それぞれのYとの間にある'.'の個数を数えたら、その和がswap回数
Y..Y.YY....[Y].YY
7  5 44        11  →  7+5+4+4+1+1 = 22

ここで、たとえば基準を1個左にずらした時の変化量は、その間に'.'が $k$ 個あったとして

左にあるYの個数 $\times k$ だけ減る
右にあるYの個数 $\times k$ だけ増える

なので、最適な基準位置は、区間中央のYであることがわかる。偶数の場合はどちらでもよい。

Y..Y.Y[Y]....Y.YY
3  1 0       4 55  →  3+1+0+4+5+5 = 18

従って、以下が前計算によりパッと求められると嬉しい。

$R(i,j)=Y_i$ を基準として右側 $Y_{i+1}～Y_j$ のYを $Y_i$ に持ってくる回数
$L(i,j)=Y_i$ を基準として左側 $Y_j～Y_{i-1}$ のYを $Y_i$ に持ってくる回数

愚直には各 $Y_i$ から各 $Y_j$ の間にある'.'の個数を数えた上で累積和を取っておけばよいのだが、しかし2次元でテーブルを作ってしまうと $O(|S|^2)$ のためTLE or MLE。

そこで、基準を1個ずらしたときに法則性が無いかを確かめると、

      Y..Y.YY....Y.YY
基準     / | \   | | \
Y0   0  2  5  8 15 23 31
    (  -2 -4 -6 -8-10-12)
Y1      0  1  2  7 13 19
    (     -1 -2 -3 -4 -5)
Y2         0  0  4  9 14

Y3            0  4  9 14
    (           -4 -8-12)
Y4               0  1  2
...

ずらすごとに等差数列を引いた形になっている。
まぁ、ずらしたところから右にある各Yまでにある'.'の個数が一定数ずつ減るので、累積和を取ったら等差で減るのは当然っちゃ当然。

基準を $Y_i$ にする時に追加される等差数列の公差は、直前の $Y_{i-1}$ との間にある'.'の数であり、$R(i,i)$ が0になるように位置を揃える。

$R(0,:)$
基準を $i$ にするときの、$R(0,:)$ からの累積公差
基準を $i$ にするときの、$R(0,:)$ からの累積初項
- 初項＝このまま等差数列を左端まで延長した場合の $Y_0$ の箇所の値

以上の長さ $O(|S|)$ の3つの配列を前計算しておけば、差分計算で $R(i,j)$ を $O(1)$ で求められる。

$L(i,j)$ も同様にすればよい。

すると区間 $[l,l+x)$ のYを連続させるswap回数は、$m$ を区間中点、$r=l+x-1$ として、 $L(m,l)+R(m,r)$ で求められ、これが $K$ 以下なら可能となる。

$x$ ごとに $l$ を全通り試しても $O(|S|)$ で判定でき、全体で $O(|S|\log{|S|})$ となる。

Python3

from itertools import groupby, accumulate

s = input()
k = int(input())
s = s.strip('.')

if s == '':
    print(0)
    exit()

between = [0]

for c, itr in groupby(s):
    if c == 'Y':
        between.extend([0] * (len(list(itr)) - 1))
    else:
        between.append(len(list(itr)))

n = len(between)
dist_fwd = list(accumulate(between))
acc_fwd = list(accumulate(dist_fwd))

between_bwd = between.copy()
between_bwd.append(0)
between_bwd.reverse()
between_bwd.pop()
dist_bwd = list(accumulate(between_bwd))
acc_bwd = list(accumulate(dist_bwd))

# acc_fwd[i] = 左端を基準として、基準～i番目のYまでを基準に集める操作回数
#   基準を1つ右にずらす毎に、等差数列が減算される感じになる。
#   基準を j ずらしたときに減算される等差数列の初項と等差を管理したい。
#   ただし等差は dist_fwd[j] と一致するため、初項の方を求めておく。
#   これにより、j 番目のYを基準とし、j～i のYをjに集める操作回数が O(1) で得られる
first_fwd = [0]
for i in range(1, n):
    first_fwd.append(first_fwd[-1] - between[i] * (i - 1))
first_bwd = [0]
for i in range(1, n):
    first_bwd.append(first_bwd[-1] + between_bwd[i] * (n - i))

dist_bwd.reverse()
acc_bwd.reverse()
first_bwd.reverse()


def check(width):
    l = width // 2
    r = width - l - 1

    for i in range(l, n - r):
        swap = acc_fwd[i + r] - (first_fwd[i] + dist_fwd[i] * (i + r))
        swap += acc_bwd[i - l] - (first_bwd[i] - dist_bwd[i] * (i - l))

        if swap <= k:
            return True

    return False


lo = 1
hi = n + 1
while lo + 1 < hi:
    m = (lo + hi) // 2

    if check(m):
        lo = m
    else:
        hi = m

print(lo)

解法2

上記のような七面倒くさいことしなくても、ちょっと発想を変えればもっと楽に計算できる。

公式Editorialの解法。二分探索は一緒。

$S$ からYの箇所のindexを抜き出した配列を $A$ とすると、1回のswapは、どれか1個を±1する操作に対応する。
（Y同士のswapは行わない前提として、異なる $A_i$ が同じ値になる瞬間があってはいけない）

Y..Y.YY....Y.YY    A = (0  3  5  6 11 13 14)
      ×                        ↓+1
Y..Y.Y.Y...Y.YY    A = (0  3  5  7 11 13 14)

Yを連続させるというのは、$A$ に連番をなるべく長く発生させるという問題に言い換えられる。

さらにこれは、あらかじめ $A_i$ から $i$ を引いて $B_i$ とおくことで、「同じ値を」なるべく多く作る問題にできる。

Y....YYYY....YY    A = (0  5  6  7  8 13 14)
                   B = (0  4  4  4  4  8  8)

すると、$[l,r)$ の区間のYを揃えるには、中央 $m$ に揃えるのが最適となるので、

              ■■                 ↓↓      
Bm        ■■■■   →  ↑↑↑■■■■
        ■■■■■       ↑↑■■■■■
    ■■■■■■■       ■■■■■■■
    l     m       r      l     m       r

$B_m (m-l) - (B_l～B_{m-1}の和) + (B_m～B_{r-1}の和) - B_m (r-m)$

累積和を前計算しておけば操作回数を $O(1)$ で計算できる。

H - Advance or Eat

問題文

$N$ 行 $N$ 列のグリッドがあり、盤面の初期状態が与えられる
- 各マスには白い駒が $1$ 個置かれているか、黒い駒が $1$ 個置かれているか、何も置かれていないかのいずれか
高橋君とすぬけ君がゲームをする。高橋君からはじめて、交互にターンが回ってくる
高橋君のターンには、以下のいずれかの操作ができる
- $1$ つ上に空マスがあるような白い駒を $1$ つ選び、上に進める
- 好きな黒い駒を $1$ つ食べる
すぬけ君のターンには、以下のいずれかの操作ができる
- $1$ つ上に空マスがあるような黒い駒を $1$ つ選び、上に進める（※高橋君とすぬけ君の「上」は同じ方向を指す）
- 好きな白い駒を $1$ つ食べる
操作ができなくなった方が負け。どちらが必勝？

制約

$1 \leq N \leq 8$

解法

非不偏ゲームの解析。知ってないと自力で思いつくのは厳しい。公式Editorialを読んでの個人的なメモ。

盤面最大 $64$ マスにつき「白、黒、何も無い」の3通りの状態を持つ $3^{64}$ のDPは、初期盤面から遷移可能な状態に絞ったところで、さすがに状態数が多すぎて無理。

Nimのように「どちらのプレイヤーも同じ手を打てる」ゲーム（不偏ゲーム）の場合は、 Grundy数などを使って効率的に解けることがあるが、今回はそうではない。

もし不偏ゲームなら、今回の問題では「各列は互いに干渉しない」ので、1列1列をNimの山のように個別に考えられそうなのに。。。

ところが、非不偏ゲームでも一定の条件を満たす場合は、Grundy数ほど簡単ではないが、1列ずつを個別に考える方法がある。

条件
- 二人零和有限確定完全情報ゲームである
- 後述の「状態に対するスコア」を、上手く設定できる

超現実数

スコアには超現実数（Surreal Number）というのを用いる。

分母が2冪に限定された実数であり、特に「2つの数に挟まれた数」を特定の方法で一意に決められるのが特徴。

$\{L|R\}$ という表記は、以下の条件を満たす実数 $x$ を示す。この条件から一意に決まる。

$L \lt x \lt R$
そのような $x$ の中で、既約分数として表したとき、分母が2冪の中で最も小さい
分母が1の場合は可能な候補が複数生まれうるが、絶対値が $0$ に最も近いものとする
- 上記2条件は、「超現実数を二分木表現したとき、最も根に近い数」といえる（二分木表現は2番目のリンク参照）

ゲーム木の構築とスコアの設定

今回の場合、ゲーム木の1頂点は「1列」の状態とする。
頂点から頂点へ、先手が可能な遷移は「白い辺」、後手が可能な遷移は「黒い辺」を張るとする。

各頂点に「スコア（評価値）」を割り当てるのだが、ここに超現実数を用いる。
以下の条件でスコア付けすることを考える。

白い辺にしたがって遷移したらスコアは必ず減少する
黒い辺にしたがって遷移したらスコアは必ず増加する

そのためには、葉からスコアを決定する上で、以下ならよい。

ある頂点からの「全ての白い辺の遷移先のスコア最大値 $S_W$」＜「全ての黒い辺の遷移先のスコア最小値 $S_B$」

先ほどの超現実数を用いて、$\{S_W|S_B\}$ で表される実数を、その頂点のスコアとする。
（遷移できる白い辺が無い場合は、$S_W = -\infty$、黒い辺が無い場合は $S_B=\infty$ などとしておく）

全ての頂点でこの条件を満たすようにスコア付けすることができればよい。仮に、今はできたと仮定する。

列 $c$ の現在の状態を $v_c$ とし、そのスコアを $S_{v_c}$ で表す。
現在の盤面の全ての列のスコア合計 $\sum_c S_{v_c}$ を $T$ とする。
$T$ の正負は、以下のように推移する。

先手の手番で $T$ が正の時
- 先手操作後の $T$ も必ず正または0が保たれる（理由は後述）
- 後手は、$T$ が正か0の状態で回ってくると、操作後は必ず正になる
- 評価値が正の状態で、先手が操作できなくなることはない → 先手必勝
先手の手番で $T$ が0または負の時
- 先ほどの逆で、先手の操作後は必ず負になる
- 後手は、負で回ってくると、操作後は必ず負か0になる
- 評価値が負の状態で、後手が操作できなくなることはない → 後手必勝

よって、「初期状態の $T$ が正なら先手必勝、0か負なら後手必勝」となる。

（今回の問題では必要ないが）より細かく言うと、

$T$ が正なら、「白い辺を使う方」の必勝
$T$ が負なら、「黒い辺を使う方」の必勝
$T$ が0なら、「後手」の必勝

となり、「白黒辺」による勝利と、「先手後手」による勝利の2種類がある。

$T$ が正なら先手の操作後も必ず非負となる理由

たとえば「$T=0.125=\frac{1}{8}$」の時に、「どの列の、どの白い辺の遷移も、$S_v$ が $\frac{1}{8}$ より大きく減少してしまう」状態になったら、 0を飛び越して一気に負にならざるをえない。

逆に、「$T$ を既約分数にした時の分母が $2^d$（上例では8）なら、白い辺の遷移による減少は、必ず $\dfrac{1}{2^d}$ 以下である」ことが示せればよい。

で、これは必ず言える。

$T$ の分母が $8$ なら、個々の $S_v$ の中に、必ず分母が $8$ 以上（16,32等）のものがある
$S_v$ は $\{S_W|S_B\}$ のように、遷移先の白最大値と黒最小値に挟まれる値で決まっている
たとえば $S_v = \frac{3}{8}$ だとして、そこからの白い辺での遷移の減少幅が $\frac{1}{8}$ より大きいなら、$S_W \lt \frac{2}{8} = \frac{1}{4}$ である
しかし、それなら「分母が小さくなるように」$S_v$ は決まるので、$S_v=\frac{1}{4}$ となっていないとおかしい

$T$ が正なら先手は必ず操作できる理由

$T$ が正なら、当然、正である $S_v$ が1つは存在する。

白い辺が出ていない、$S_v \gt 0$ の頂点を考える。

$S_v = \{S_W|S_B\}$ という定義を考えたとき、白い辺が無いなら $S_W=-\infty$ である。
また、$S_v$ が正なら $S_B$ も正ということになる。

しかし、それなら超現実数のルール上、$S_v=0$ となっているはずであり、矛盾する。

$S_v$ が正なら、白い辺は必ず出ていることになる。

全ての頂点でスコアの条件を満たせる証明

どのようなゲームでもスコアを上手く設定できるわけではなく、今回のゲーム設定がたまたま性質を満たしているので効率的に解ける、ということになる。

いま、状態 $v$ のスコア $S_v$ を決めるとして、そこから遷移できる全ての状態は既にスコアが矛盾なく求まっているとする。

$v$ からの遷移先で、どのように白い辺 $v→a$ と黒い辺 $v→b$ のペアを持ってきても、遷移先のスコア $S_a \lt S_b$ であることが示せればよい。

操作には「ある駒を進める」「ある駒を食べる」の種類があるが、

先手は $v→a$ に相当する操作を、「後手が $v→b$ の操作を行った後」でもできる
後手は $v→b$ に相当する操作を、「先手が $v→a$ の操作を行った後」でもできる

この2つがともに成り立つことを、「互いに干渉しない」とする。

互いに干渉しない場合、ゲーム木は以下のようになっており、

 ,--> a ==,     -->: 白い辺
v          w    ==>: 黒い辺
 `==> b --'

$S_a \lt S_w \lt S_b$ なので、問題なく $S_v$ を設定できる。

「互いに干渉する」のは、「先に行動する方が駒を先に食べると、後に行動する方はその駒を動かせなくなる」のみである。

その場合、例えば先手が先に行動するなら

vの状態  aの状態  bの状態
  ・       ・       ●        ・: 空きマス
  ●       ・       ・        ●: 黒い駒

 ,--> a     -->: 白い辺
v     ↑    ==>: 黒い辺
 `==> b

このように、状態 $b$ からでも先手は黒を食べて $a$ に遷移することができ、$b→a$ にも白い辺が張られていることになる。

よって、$S_a \lt S_b$ が成り立ち、問題なく $S_v$ を設定できる。

Python3

n = int(input())
field = [input() for _ in range(n)]

pow3 = [1] * n
for i in range(1, n):
    pow3[i] = pow3[i - 1] * 3


def decode_state(key):
    result = []
    for i in range(n):
        key, m = divmod(key, 3)
        result.append(m)
    return result


n3 = 3 ** n
links_a = [[] for _ in range(n3)]
links_b = [[] for _ in range(n3)]
links_r = [[] for _ in range(n3)]
undefined_count = [0] * n3

for key in range(n3):
    state = decode_state(key)
    prev_row_is_empty = False
    for i in range(n):
        if state[i] == 0:
            prev_row_is_empty = True
        elif state[i] == 1:
            to_key = key - pow3[i]
            links_b[key].append(to_key)
            links_r[to_key].append(key)
            undefined_count[key] += 1
            if prev_row_is_empty:
                to_key = key - pow3[i] + pow3[i - 1]
                links_a[key].append(to_key)
                links_r[to_key].append(key)
                undefined_count[key] += 1
            prev_row_is_empty = False
        else:
            to_key = key - pow3[i] * 2
            links_a[key].append(to_key)
            links_r[to_key].append(key)
            undefined_count[key] += 1
            if prev_row_is_empty:
                to_key = key - pow3[i] * 2 + pow3[i - 1] * 2
                links_b[key].append(to_key)
                links_r[to_key].append(key)
                undefined_count[key] += 1
            prev_row_is_empty = False


def get_mid_value(a, b):
    assert a < b
    if a < 0 < b:
        return 0
    if a < b <= 0:
        return -get_mid_value(-b, -a)
    for shift in range(30, -1, -1):
        c = ((a >> shift) + 1) << shift
        if c < b:
            return c


evaluates = [0] * n3
q = [0]
while q:
    u = q.pop()
    max_a = -(1 << 60)
    min_b = 1 << 60
    for v in links_a[u]:
        max_a = max(max_a, evaluates[v])
    for v in links_b[u]:
        min_b = min(min_b, evaluates[v])
    evaluates[u] = get_mid_value(max_a, min_b)

    for w in links_r[u]:
        undefined_count[w] -= 1
        if undefined_count[w] == 0:
            q.append(w)

total = 0
for column in zip(*field):
    key = sum(pow3[i] * '.WB'.index(c) for i, c in enumerate(column))
    total += evaluates[key]

if total > 0:
    print('Takahashi')
else:
    print('Snuke')

目次

NECプログラミングコンテスト2021(AtCoder Beginner Contest 229) F,G,H問題メモ

F - Make Bipartite

問題

解法

G - Longest Y

問題

解法

解法2

H - Advance or Eat

問題文

制約

解法

超現実数

ゲーム木の構築とスコアの設定

$T$ が正なら先手の操作後も必ず非負となる理由

$T$ が正なら先手は必ず操作できる理由

全ての頂点でスコアの条件を満たせる証明