AtCoder Beginner Contest 196 D,E,F問題メモ

AtCoder Beginner Contest 196

D - Hanjo

問題

$H \times W$ のグリッドがある
この中に $A$ 枚の $1 \times 2$ の畳と $B$ 枚の $1 \times 1$ の半畳を敷き詰める方法のパターン数を求めよ
畳は縦にも横にも使うことができる
回転や反転して初めて同じになるものは区別する
$HW = 2A+B \le 16$

解法

「畳」と言ったときは $1 \times 2$ の畳を指すものとする。

制約から敷き詰め方を全探索するのだろうとは思うが、実装の仕方にちょっと迷う。

$A$ 枚の畳を敷き詰めると、余ったスペースへの半畳の敷き詰め方は勝手に決まるので、半畳は無視して畳の置き方をDFSなどで探索すればよい。

既に各マスに畳が置かれた・置かれていないだけが重要で、畳の種類や縦横などは関係ないので、 $2^{HW}$ の情報量で状態を管理できる。

置き方の表現方法としては、 $H \times W$ の二次元配列でもよいが、以下のようにすると1つの数字で表現できる。

0-indexでの $i$ 行 $j$ 列目を $(i,j)$ として、 $i \times W + j$ とすることで各マスを $0～HW-1$ の連番に対応させられるので、これのbit集合で「畳を置いたマス」を表現する。

<>.      012      876543210
^..  ↔  345  →  001001011  =  75
v..      678

Python3

E - Filters

問題

$N$ 個の関数が与えられる
$i$ 番目の関数は $a_i,t_i$ からなり、
- $t_i=1$ のとき、 $f_i(x)=x+a_i$
- $t_i=2$ のとき、 $f_i(x)=\max(x,a_i)$
- $t_i=3$ のとき、 $f_i(x)=\min(x,a_i)$
$Q$ 個の整数 $x_1,x_2,...,x_Q$ が与えられる
それぞれについて、 $f_N( ... f_2(f_1(x_i)))$ を求めよ
$1 \le N,Q \le 2 \times 10^5$
$|a_i|,|x_i| \le 10^9$

解法

たとえば $\infty,0,-\infty$ などから始めたときにどうなるかを考えると、

 ∞  ------
  :       |
 20       |      ,------------,
  :       |    ,'              `,
 10       ----'  ,------------,  `----  ----
  :            ,'              `,        ↑
  0  ---------'                  `----  答えの
  :                                    取り得る
-10                     ------,          範囲
  :                     |      `,        ↓
-20                     |        `----  ----
  :                     |
-∞  -------------------
       min(10)  +10  max(-10)  -10

最初に $\min(10)$ が来たら、 $10～ \infty$ の数は全て $10$ になり、以降の挙動は同じとなる。

以下を管理していけば、

答えの取り得る上限と下限
上限にも下限にもタッチしなかったら初期値からどれだけずれるか
- つまり全ての $t_i=1$ であるような $a_i$ の合計 $D$

$x_i+D$ が上限・下限を超えてしまうような $x_i$ の場合は、上限or下限。超えていなければ答えは $x_i+D$ 。

Python3

F - Substring 2

問題

'0'と'1'からなる2つの文字列 $S,T$ が与えられる
$T$ のいくつかの文字を変更して、 $S$ の部分文字列としたい
変更する必要のある最小個数を求めよ
$1 \le |T| \le |S| \le 10^6$

解法

フーリエ変換によるたたみ込み。知っていることが前提になると思われる。

たたみ込みは、原理は何やってるか理解が難しいが、とりあえず以下のことができるアルゴリズム。

$a_0,a_1,a_2,...,a_{N-1}$ と $b_0,b_1,b_2,...,b_{M-1}$ がある
そこから以下のような $c_0,c_1,...,c_{N+M-2}$ を作る
- $c_k$ は、 $i+j=k$ となるような $a_i \times b_j$ の和
- つまり、 $\displaystyle c_k = \sum_{i=0}^{N-1} a_i \times b_{k-i}$ （ただし範囲外の添字については $a_i,b_j=0$ ）

フーリエ展開による畳み込み積分の高速化

愚直には $O(NM)$ かかりそうな所、 $L=N+M$ として、 $O(L \log{L})$ で行える。すごい。

C++ なら、ACLに既存の実装があるので自前で実装せずとも利用できる。
Pythonなら、オーバーフローするものは無理だが、今回のように答えが64bitに収まることがわかっている場合は numpy.fft などを利用できる。

さてこれを今回の問題にどう使うか。

$T$ を $S$ のどの位置に一致させるか決めたら、0か1しか出てこないので、各桁ずつのXORで1となった個数がそのまま答えとなる。

S    10101000010011011110
T        0010011111
XOR      1010001100       合計 4

S    10101000010011011110
T           0010011111
XOR         0000000100    合計 1

$S$ の全ての開始位置について求め、その中の最小を取れば答え。

ここで、 $T$ の各文字に逆からindexを振ってみる。

i    01234567890123456789
S    10101000010011011110
T        0010011111
j        9876543210

すると、合わせる位置が同じ $|T|$ 個のペアは $i+j$ が全て等しくなる。

ここにたたみ込みを利用できる。
$(i,j)=(4,9),(5,8),...,(13,0)$ のそれぞれで $S_i \oplus T_j$ を計算して合計した値は、まさしく $S$ の $4$ 文字目を開始位置としたときの答えとなる。

ただし、高速なたたみ込みができるのはかけ算だが、今必要な演算はXORなので、何らかの変換が必要になる。

「 $0,1$ 間のXOR」を「 $1,-1$ 間のかけ算」に変換してやると、結果が見事に対応するので、これを利用する。

たたみ込みで求められる値 $c_k$ は $|T|$ 個の $-1,1$ の和で、今回はこの中で $-1$ の個数を求めたい。
よって、 $\dfrac{|T|-c_k}{2}$ が $-1$ の個数、ひいては元のXORの演算での1の個数となる。

$c_k$ の先頭と末尾の各 $|T|-1$ 項は、 $T$ が $S$ からはみだすような置き方となってしまうため、除いて考える。

Python3

        
          
          
              
              import os
import sys
 
import numpy as np
 
 
def solve(sss, ttt):
    def bit_length(n):
        x = 0
        while 1 << x < n:
            x += 1
        return x
 
    def bit_scan_forward(n):
        x = 0
        while n & 1 == 0:
            n >>= 1
            x += 1
        return x
 
    def pow_mod(x, n, m):
        r = 1
        y = x % m
        while n:
            if n & 1:
                r = (r * y) % m
            y = y * y % m
            n >>= 1
        return r
 
    def get_primitive_root(m):
        if m == 2: return 1
        if m == 167772161: return 3
        if m == 469762049: return 3
        if m == 754974721: return 11
        if m == 998244353: return 3
        divs = [2]
        x = (m - 1) // 2
        while x & 1 == 0:
            x >>= 1
        i = 3
        while i * i <= x:
            if x % i == 0:
                divs.append(i)
                x //= i
                while x % i == 0:
                    x //= i
            i += 2
        if x > 1:
            divs.append(x)
        g = 2
        while True:
            ok = True
            for d in divs:
                if pow_mod(g, (m - 1) // d, m) == 1:
                    ok = False
                    break
            if ok:
                return g
 
    def butterfly_prepare(mod, primitive_root):
        sum_e = np.zeros(30, np.int64)
        sum_ie = np.zeros(30, np.int64)
        es = np.zeros(30, np.int64)
        ies = np.zeros(30, np.int64)
        cnt2 = bit_scan_forward(mod - 1)
        e = pow_mod(primitive_root, (mod - 1) >> cnt2, mod)
        ie = pow_mod(e, mod - 2, mod)
        for i in range(cnt2, 1, -1):
            es[i - 2] = e
            ies[i - 2] = ie
            e = e * e % mod
            ie = ie * ie % mod
        now_e = 1
        now_ie = 1
        for i in range(cnt2 - 1):
            sum_e[i] = es[i] * now_e % mod
            sum_ie[i] = ies[i] * now_ie % mod
            now_e = now_e * ies[i] % mod
            now_ie = now_ie * es[i] % mod
        return sum_e, sum_ie
 
    def butterfly(aaa, mod, sum_e):
        n = aaa.size
        h = bit_length(n)
 
        for ph in range(1, h + 1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            now = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = aaa[i + offset]
                    r = aaa[i + offset + p] * now % mod
                    aaa[i + offset] = (l + r) % mod
                    aaa[i + offset + p] = (l - r) % mod
                now = now * sum_e[bit_scan_forward(~s)] % mod
 
    def butterfly_inv(aaa, mod, sum_ie):
        n = aaa.size
        h = bit_length(n)
 
        for ph in range(h, 0, -1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            inow = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = aaa[i + offset]
                    r = aaa[i + offset + p]
                    aaa[i + offset] = (l + r) % mod
                    aaa[i + offset + p] = ((l - r) * inow) % mod
                inow = inow * sum_ie[bit_scan_forward(~s)] % mod
 
    def convolution(aaa, bbb, MOD):
        n = aaa.size
        m = bbb.size
        k = n + m - 1
        z = 1 << bit_length(k)
        raaa = np.zeros(z, np.int64)
        rbbb = np.zeros(z, np.int64)
        raaa[:n] = aaa
        rbbb[:m] = bbb
        primitive_root = get_primitive_root(MOD)
        sum_e, sum_ie = butterfly_prepare(MOD, primitive_root)
        butterfly(raaa, MOD, sum_e)
        butterfly(rbbb, MOD, sum_e)
        for i in range(z):
            raaa[i] = raaa[i] * rbbb[i] % MOD
        butterfly_inv(raaa, MOD, sum_ie)
        iz = pow_mod(z, MOD - 2, MOD)
        for i in range(k):
            raaa[i] = raaa[i] * iz % MOD
        return raaa[:k]
 
    MOD = 998244353
    sss %= MOD
    ttt %= MOD
    n = sss.size
    m = ttt.size
    return ((m - convolution(sss, ttt, MOD)[m - 1:n]) % MOD // 2).min()
 
 
SIGNATURE = '(i8[:],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)
 
s = input()
t = input()
sss = np.fromiter((1 if c == '1' else -1 for c in s), np.int64)
ttt = np.fromiter((1 if c == '1' else -1 for c in t), np.int64)[::-1]
ans = solve(sss, ttt)
print(ans)

            

        
      

暫定コストの小さい方から経路探索的に1文字ずつ合わせていく0-1BFSで、1ケース以外は全部通ったんだけど、まぁダメだったよね。反例も比較的簡単に作れちゃうし。