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

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

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

解法は、細かな点でいろいろな実装の違いがあるっぽい。

自分はTwitterで言及されていた箱根駅伝DPの考え方が一番理解しやすかった。

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

"損失"を数える

「あるランプについてコストが $1$ 減る機会があったが、既に $0$ だったので減らされなかった」ことを、1回の「損失」とする。

ランプを付ける順番を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-(理想的なコスト)$ が、“機会を無駄にしてよい最大数”（＝許容損失）となる。
全てのランプの損失の合計が許容損失以下ならよい。

(例)  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なので、この並べ方は条件を満たさない。

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

損失は、コストが1減る機会の回数 $\frac{N(N-1)}{2}$ が上限となる。
損失をキーとして「損失○○以下」というパターン数をDPで数える。

DP

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

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

数 $A_j$ が書かれたランプ側頂点は、順番側頂点の $j$ と対応する位置にまとまって配置されているものとする。

N = 6
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,許容損失以下]$ の値の合計が、答えとなる。

$k$ はDPを進める上で減らないので、許容損失までの値を管理すればよい。

遷移

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

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

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

「順番側頂点 $i$」と「ランプ側の未マッチング頂点」のマッチング
- $w$ を、ランプ側の「$i$ 未満の未マッチング頂点」および「先ほど使用されなかった $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$ とマッチングする際にランプ側の未マッチング頂点が残っていない場合など、細かな場合分けが多少あるので注意。

このDPは、$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$ 偶数

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

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

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

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

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

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

$N$ 奇数

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

⑤   ⑥   ⑦   ⑧

頂点 $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))

C - Combine to Make Non-decreasing

問題文

長さ $N$ の整数列 $A=(A_1, A_2, \cdots, A_N)$ が与えられます。
すぬけ君は $A$ が広義単調増加列になるようにしたいです。
すぬけ君は $0$ 回以上、以下の操作を行うことができます。
- $A$ の隣接する $2$ つの要素を選ぶ
- この $2$ つの要素を取り除き、代わりにこの $2$ つのビット単位 $\mathrm{OR}$ を取った値を元の位置に挿入する

$A$ が広義単調増加列となったときの長さとしてありうる値の最大値を求めてください。

制約

$1 \le N \le 2 \times 10^5$
$1 \le A_i \lt2^{30}$
入力される値は全て整数

解法

計算量および正当性の十分な証明はできてないため、もしかしたら反例があるかも。

ORをとる要素は区間になる。
公式Editorialにある通り、$f(l,r)=A_l \ \mathrm{OR} \ ... \ \mathrm{OR} A_r$ としたとき、 $f(l,r)$ の取り得る値の種類数はそんなに多くない。

$r$ を固定すると、$l$ が左に動く中で新しいbitが立つ回数は高々 $O(\log{\max(A)})$ となる。
よって、全体では $O(N\log{\max(A)})$ である。

以下のDPを考える。

$\mathrm{DP}[i,prev,curr]:=A_i$ まで考慮して、前の区間の総ORが $prev$、$i$ を右端とした今の暫定区間の総ORが $curr$ である状態における広義単調増加列の最大長

更新は単純で、

$prev \le curr$ なら、そこで区間を切って新しい区間を開始できる。
- $\mathrm{DP}[i,curr,A_{i}] ← \mathrm{DP}[i-1,prev,curr]+1$
常に、今の区間を延長できる。
- $\mathrm{DP}[i,prev,curr \ \mathrm{OR} \ A_{i}] ← \mathrm{DP}[i-1,prev,curr]$
- ※←はchmax操作

最終的に、$prev \le curr$ であるような $\mathrm{DP}[N,prev,curr]$ の中での最大値が答えとなる。

ただし、このDPは計算量が問題となる。
$i$ は $O(N)$、$curr$ は $O(\log{\max(A)})$ 種類の値を持つ。
$prev$ の評価がよく分からないが、ここがちょっと多くなりそう。

$(prev,curr)$ の組の個数はランダムテストでは $20～30$ 程度に収まり十分に高速に動くのだが、例えば $A=(1,2,4,8,16,...,2^{29},1,2,4,8,16,...)$ など、 $f(l,r)$ の取り得る種類数を意図的に多くすると $900～1250$ などとなりTLEする。
（高速な言語ではこれでも通りそうだがPyPyの計算では厳しい & より計算量の悪い例があるかも）

ここで枝刈りをし、「$i$ の時点でのDPの最大値 $\max(\mathrm{DP}[i,*,*])$ を $B_i$ とすると、 $B_i-2$ 以下の要素は保持しない」ようにする。

これだと、一時的に $O(\log{\max(A)}^2)$ 程度まで上がることはあるものの、平均的には個数が大幅に減り、間に合うようになる。
ただ、2以上の差を逆転するのは難しそうではあるが、絶対できないかと言われると？正当性が未証明。

Python3

import sys
from collections import defaultdict


def solve(n, aaa):
    def encode(p, c):
        return p << 30 | c

    def decode(key, mask=(1 << 30) - 1):
        p = key >> 30
        c = key & mask
        return p, c

    dp = {0: 0}
    for a in aaa:
        ndp = defaultdict(int)
        best_len = 0
        for key, l in dp.items():
            prev, curr = decode(key)
            if prev <= curr:
                key = encode(curr, a)
                ndp[key] = max(ndp[key], l + 1)
                best_len = max(best_len, l + 1)
            key = encode(prev, curr | a)
            ndp[key] = max(ndp[key], l)
            best_len = max(best_len, l)
        dp = {key: l for key, l in ndp.items() if l + 1 >= best_len}

    ans = 0
    for key, l in dp.items():
        prev, curr = decode(key)
        if prev <= curr:
            ans = max(ans, l)
    return ans

input = sys.stdin.buffer.readline
n = int(input())
aaa = list(map(int, input().split()))
ans = solve(n, aaa)
print(ans)

D - Devourers and Cake

問題文

先手太郎君と後手次郎君はお母さんへのプレゼントに長方形のケーキを買ってきました。
先手太郎君と後手次郎君はおなかが空いたので、お母さん用の $1$ ピースを残して全て食べてしまうことにしました。

$N$ 行 $M$ 列に並ぶピースからなるケーキがあります。
上から $i$ 行目、左から $j$ 列目のピースには、$s_{i,j}$ が '1' のときイチゴが載っており、'0' のときイチゴが載っていません。
先手太郎君からはじめて、二人は残りのピースが $1$ 個になるまで交互にケーキに操作を行います。
二人が行うことができる操作は以下の通りです。ただし、残りの全てのピースを食べてしまうような操作を行うことはできません。
- 上から $1$ 行目に並ぶピースを全て食べる
- 下から $1$ 行目に並ぶピースを全て食べる
- 左から $1$ 列目に並ぶピースを全て食べる
- 右から $1$ 列目に並ぶピースを全て食べる

先手太郎君はイチゴが載っているピースを、後手次郎君はイチゴが載っていないピースを残したいです。
先手太郎君が適切に操作を行ったとき、後手次郎君がどのように操作を行ったとしてもイチゴが載っているピースを残すことができるかどうかを判定してください。
$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1 \le T \le 10^5$
$1 \le N,M \le 10^{3}$
$1\lt NM$
$s_{i}$ は '0' と '1' のみからなる長さ $M$ の文字列
全てのテストケースにおける $NM$ の総和は $10^6$ 以下

解法

問題は以下のように言い換えられる。

グリッドの中心（$N,M$ 偶数の場合はマスの境界線上もあり得る）にコマを置く
交互に、$0.5$ マス分だけ上下左右のいずれかにコマを動かす。
- この時、上下に動かせる回数はあわせて $N-1$ 回まで、左右に動かせる回数はあわせて $M-1$ 回まで
$N+M-2$ 回の操作後、コマはいずれかのマスの中央にある。
先手は“1”が書かれたマスに、後手は“0”が書かれたマスにコマがある状態なら勝ち。

$N$ 奇数で1次元の場合

後手は“まねっこ戦略”が使える。

コマの初期位置が“0”なら、先手がどちらへ動かそうと、元に戻して後手必勝。

      v
1|1|1|0|1|1|1

コマの初期位置が“1”でも、両端が“0”なら、初手で先手がどちらに動かしてもそれに追従すれば“0”に移せ、以降は“0”に保て後手必勝。

      v
1|1|0|1|0|1|1

それ以外の場合は“1”が連続している箇所にコマがあるので、先手は“1”に隣り合う方向に動かし続ければ、“11”上にある状態を保て、先手必勝。

      v
1|1|0|1|1|0|1

$N,M$ 奇数で2次元の場合

1次元の場合で先手必勝の行を“先手行”、後手必勝の行を“後手行”とする。

まずは「上下移動をおこない尽くしてから、左右移動をおこなう」場合に限定して考える。
この場合、1次元の場合と似た形になる。

初期位置で後手行上にコマがある場合は、上下移動は元に戻すことで後手必勝。

        v
  1|1|1|1|1|1|1  先手行
> 1|1|0|1|0|1|1  後手行
  1|1|1|1|1|1|1  先手行

先手行上にあっても、後手行に挟まれていれば、1回だけ先手に追従することで後手必勝。それ以外は先手必勝。

        v
  1|1|0|1|0|1|1  後手行
> 1|1|1|1|1|1|1  先手行
  1|1|0|1|0|1|1  後手行

限定をなくして上下左右に動ける場合でも、行・列のいずれの方向でも後手必勝条件が満たされていれば後手必勝となる。

奇数×奇数の場合は、中央の $3 \times 3$ マスで勝敗が決定されることがわかった。

$N,M$ のいずれか一方が奇数の場合

$N$ 奇数とする。コマは初期位置で、グリッドの2マスの境界線上にある。

       v
  0|1|1|0|0|0
> 1|0|0|0|1|0
  1|0|1|0|0|0

先手太郎が初手で左右のいずれかに動かすと奇数×奇数となり、「先手太郎が後手番となった形」に帰着される。
ただし、今度は先手太郎＝後手が、コマが“1”にある状態を目指すので、盤面の0と1の意味合いが反転する。

よって、「中央2マスのいずれかを中心とした $3 \times 3$ マスの、$0,1$ を反転させたもの」の、どちらかが後手必勝であれば、先手太郎が必勝。

   ,-①--,      ①反転  ②反転
  0|1|1|0|0|0    0|0|1   0|1|1  ①が後手必勝盤面なので、
  1|0|0|0|1|0    1|1|1   1|1|0  先手太郎は初手左に動けば勝ち。
  1|0|1|0|0|0    1|0|1   0|1|1
     `--②-'

そうでない場合、先手太郎は初期位置から左右に動かすと、どちらに動かしても「先手必勝盤面を、後手次郎が先手の状態で渡す」ことになるため負ける。
しかし、上下に動かしても後手次郎によって中央に戻され、いつかは左右に動かさざるを得なくなる。
よって後手次郎の必勝。

この場合は中央の $3 \times 4$ マスで勝敗が決定される。

$N,M$ が偶数の場合

先手太郎の初手を4通り全て試すと、「$N,M$ のいずれか一方が奇数」に帰着される。

まとめ

盤面全体の勝敗と、中央の $3 \times 3$、$3 \times 4$、$4 \times 4$（$N,M$ の偶奇による）部分の勝敗は一致する。

このサイズなら、愚直に全探索で調べられる。

Python3

def next_field(i, j, field):
    mask = (1 << j) - 1
    xor_field = tuple(row ^ mask for row in field)

    if i > 1:
        yield i - 1, j, xor_field[1:]
        yield i - 1, j, xor_field[:-1]
    if j > 1:
        yield i, j - 1, tuple(row >> 1 for row in xor_field)
        mask = (1 << (j - 1)) - 1
        yield i, j - 1, tuple(row & mask for row in xor_field)


def recursive(n, m, field, memo={}):
    if n == 1 and m == 1:
        assert len(field) == 1 and field[0] in (0, 1)
        return field[0]

    if (n, m, field) in memo:
        return memo[n, m, field]

    if any(recursive(*key) == 0 for key in next_field(n, m, field)):
        memo[n, m, field] = 1
        return 1

    memo[n, m, field] = 0
    return 0


def solve(n, m, field):
    if n >= 7:
        if n % 2 == 0:
            trim = (n - 6) // 2
            n = 6
        else:
            trim = (n - 5) // 2
            n = 5
        field = field[trim:-trim]
    if m >= 7:
        if m % 2 == 0:
            trim = (m - 6) // 2
            m = 6
        else:
            trim = (m - 5) // 2
            m = 5
        field = [row[trim:-trim] for row in field]

    field = tuple(int(row, base=2) for row in field)

    return recursive(n, m, field)


t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    field = [input() for _ in range(n)]
    ans = solve(n, m, field)
    if ans:
        print('First')
    else:
        print('Second')

目次

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

A - Affinity for Artifacts

問題文

制約

解法

"損失"を数える

DP

遷移

B - Balanced Neighbors 2

問題文

制約

解法

$N$ 偶数

$N$ 奇数

C - Combine to Make Non-decreasing

問題文

制約

解法

D - Devourers and Cake

問題文

制約

解法

$N$ 奇数で1次元の場合

$N,M$ 奇数で2次元の場合

$N,M$ のいずれか一方が奇数の場合

$N,M$ が偶数の場合

まとめ