AtCoder Beginner Contest 196 D,E,F問題メモ
D - Hanjo
問題
解法
「畳」と言ったときは $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
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(state, remaining):
if remaining == 0:
return 1
result = 0
for i in range(h - 1):
for j in range(w):
b = 1 << (i * w + j)
b |= 1 << ((i + 1) * w + j)
if state & b:
continue
result += solve(state | b, remaining - 1)
for i in range(h):
for j in range(w - 1):
b = 1 << (i * w + j)
b |= 1 << (i + 1 * w + j + 1)
if state & b:
continue
result += solve(state | b, remaining - 1)
return result
h, w, a, b = map(int, input().split())
ans = solve(0, a)
for d in range(1, a + 1):
ans //= d
print(ans)
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$ になり、以降の挙動は同じとなる。
以下を管理していけば、
$x_i+D$ が上限・下限を超えてしまうような $x_i$ の場合は、上限or下限。
超えていなければ答えは $x_i+D$。
Python3
n = int(input())
lower = -(1 << 60)
upper = 1 << 60
added = 0
for _ in range(n):
a, t = map(int, input().split())
if t == 1:
lower += a
upper += a
added += a
elif t == 2:
lower = max(lower, a)
upper = max(upper, a)
else:
lower = min(lower, a)
upper = min(upper, a)
q = int(input())
xxx = list(map(int, input().split()))
for x in xxx:
print(max(lower, min(upper, x + added)))
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ケース以外は全部通ったんだけど、まぁダメだったよね。
反例も比較的簡単に作れちゃうし。
