AtCoder Regular Contest 157 D問題メモ

AtCoder Regular Contest 157

久々にひっどい誤読（思い込み）をB問題でやっちゃった。

D - YY Garden

問題

$H \times W$ のグリッドに 'X' または 'Y' が1つずつ書かれている
行と行の間、または列と列の間に一直線に区切りを入れることを繰り返して、複数の区画に区切る
- 区切りはグリッドの途中で止まったりせず、端から端まで貫通する
区切る場所は行方向に $H-1$、列方向に $W-1$ 箇所あるため、区切り方は $2^{H+W-2}$ 通りある
このうち、「どの区画にも、ちょうど2個の'Y'が含まれるような区切り方」の個数を $\mod{998244353}$ で求めよ
$1 \le H,W \le 2000$

解法

区切りは板チョコのように、行・列とも一直線に端から端まで入る。（明治のTHE・チョコレートは例外）

区切るべき区画の個数は、初期盤面にある 'Y' の個数で一意に決まる。
'Y' が奇数個なら不可能。偶数個なら、$2n$ とすると、$n$ 個の区画に分けることになる。

行方向に区切る数、列方向に区切る数をそれぞれ $R,C$ とすると、$n=RC$ なので、 $(R,C)$ の組は $n$ を2整数の積に分ける方法の数に限定される。
さらに $H \ge R,W \ge C$ という制約もある。

この $(R,C)$ を全探索する。

$R,C$ を固定した時にどうなっていればいいかというと、'Y' の個数の2次元累積和を取ったときに

    :     :     :         :
... 2 ... 4 ... 6 ... ...2C
    :     :     :         :
... 4 ... 8 .. 12 ... .. 4C
    :     :     :         :
    :     :     :         :
...2R .. 4R .. 6R ... ..2RC

このような条件を満たす $n$ 個のマスが存在していればよいことになる。
これらの各マスのすぐ右・すぐ下に区切りを入れることで、全ての区画の'Y'を2個ずつにできる。

途中の行・列はどこでもよいのだが、最終行・最終列は必ず使わなければならない点に注意。

ここで面倒なのが、上の条件を満たすマスの配置は複数出てきてしまうことがあり、それらは別の区切り方として数えなければならない点。

累積和の $i$ 行目の $j_1,j_2,...$ 列目を拾うと $2k,4k,...,2Ck$ の並びが現れるとする。
また、$i+1$ 行目でも同じ列を拾うと、同じ$2k,4k,...,2Ck$ の並びが現れるとする。
この時、グリッドの $i+1$ 行目は全て 'X' となっているはずである。
$i$ 行目の直後に区切りを入れるのと、$i+1$ 行目の直後に入れるのとの違いで、全体の可能不可能に影響はもたらさない。

よって、最初に全て 'X' である行・列を除いてやれば、$(R,C)$ を固定した時の $n$ 個のマスは必ず一意に定まる。
少なくとも最終行・最終列が続けて同じ数ということが無くなるので、最終行で $2R,4R,...,2RC$、最終列で $2C,4C,...,2RC$ の並びが現れる位置をそれぞれ調べ、現れるなら、他の箇所も満たされるか調べればよい。

除いた盤面で、ある行の直後に区切りを入れることになった場合、元の盤面に戻って区切りを実際に入れる箇所の候補は、「自身、および自身から次に除かない行が出てくるまでに除いた行」の直後となる。

     ... 2k ... 4k ..... 2Ck    __ ←除いた盤面でのこの行における
(除) ... 2k ... 4k ..... 2Ck    __   元の盤面での区切り位置候補は3箇所
(除) ... 2k ... 4k ..... 2Ck    __
     ... 2k ..4k+1 ... 2Ck+5

この候補は、区切りを入れる位置に対してそれぞれ独立に存在する。

よって一意に定まった区切り位置に対して、各位置の候補数の積が、$(R,C)$ を決め打ったときの答えとなる。
（※最終行・最終列に関しては候補数は1固定である点に注意）

前処理に $O(HW)$、その後1回の $(R,C)$ の決め打ちで $n$ 個（最大 $HW/2$）のマスを参照することになるが、

$n$ が最大に近いなら、$H \ge R,W \ge C$ という制約のため、$(R,C)$ の候補は多くない
$n$ が小～中程度なら、$(R,C)$ の候補は多少増えうるが、1回の探索にかかる負担は少ない

ため、正確な計算量解析は難しいが、2秒あれば十分通る計算量となる。

Python3

def compress_row(field):
    free = [1]
    new_field = []
    for row in field:
        if all(c == 'X' for c in row):
            free[-1] += 1
        else:
            new_field.append(row)
            free.append(1)
    return new_field, free[1:]


def check1(acc2d, n, m, a, b):
    row_step = b * 2
    col_step = a * 2

    row_idx = []
    tgt = row_step
    for i in range(n):
        if tgt == acc2d[i][-1]:
            row_idx.append(i)
            tgt += row_step
        elif tgt < acc2d[i][-1]:
            return None

    col_idx = []
    tgt = col_step
    for j in range(m):
        if tgt == acc2d[-1][j]:
            col_idx.append(j)
            tgt += col_step
        elif tgt < acc2d[-1][j]:
            return None

    return row_idx, col_idx


def check2(acc2d, a, b, row_idx, col_idx):
    for ri in range(a):
        i = row_idx[ri]
        for ci in range(b):
            j = col_idx[ci]
            if acc2d[i][j] != (ri + 1) * (ci + 1) * 2:
                return False
    return True


def solve(h, w, field):
    MOD = 998244353
    field, free_row = compress_row(field)
    field, free_col = compress_row(zip(*field))
    field = list(zip(*field))

    n = len(field)
    if n == 0:
        return 0
    m = len(field[0])

    acc2d = [[0] * m for _ in range(n)]
    acc2d[0][0] = int(field[0][0] == 'Y')
    for i in range(1, n):
        acc2d[i][0] = acc2d[i - 1][0] + (field[i][0] == 'Y')
    for j in range(1, m):
        acc2d[0][j] = acc2d[0][j - 1] + (field[0][j] == 'Y')
    for i in range(1, n):
        for j in range(1, m):
            acc2d[i][j] = acc2d[i - 1][j] + acc2d[i][j - 1] - acc2d[i - 1][j - 1] + (field[i][j] == 'Y')

    total = acc2d[-1][-1]
    if total % 2 == 1:
        return 0

    half = total // 2
    pairs = []
    for a in range(1, h + 1):
        if half % a == 0 and half // a <= w:
            pairs.append((a, half // a))

    ans = 0
    for a, b in pairs:
        result = check1(acc2d, n, m, a, b)
        if result is None:
            continue

        row_idx, col_idx = result

        if check2(acc2d, a, b, row_idx, col_idx):
            tmp = 1
            for i in row_idx[:-1]:
                tmp *= free_row[i]
                tmp %= MOD
            for j in col_idx[:-1]:
                tmp *= free_col[j]
                tmp %= MOD
            ans += tmp
            ans %= MOD

    return ans


h, w = map(int, input().split())
field = [input() for _ in range(h)]

ans = solve(h, w, field)
print(ans)

目次

AtCoder Regular Contest 157 D問題メモ

D - YY Garden

問題

解法