目次
AtCoder Beginner Contest 179 D,E,F問題メモ
モノポリーは刑務所過ぎたオレンジあたりの土地が強い。知らんけど。
D - Leaping Tak
問題
- 一列に並んだ $N$ マスを、1から $N$ まで移動する
- 移動の方法は、以下の通り
- 共通部分を持たない $K$ 個の区間 $[L_1,R_1],[L_2,R_2],...,[L_K,R_K]$ が与えられる
- 1回に進めるマスの数は、このどれかに含まれる数に限られる
- $d$ を選んだ場合、現在地が $i$ なら $i+d$ に移動する
- 1から $N$ まで移動する方法の個数を $\mod{998244353}$ で求めよ
- $2 \le N \le 2 \times 10^5$
- $1 \le K \le 10$
解法
累積和DP。
- $DP[i]=$ マス $i$ への行き方の通り数
として、$i$ の小さい方から順次更新していく。
進めるマスの数の集合を $S$ とすると、一般的なDPでは骨子は以下のようになる。
for i in range(1, N): # 移動元
for d in S: # 何マス進むか
DP[i+d] += DP[i]
しかし今回の場合、$|S|$ は最大 $N$ 通りになるため、そのままやると $O(N^2)$ となり不可能。
$S$ の要素がある程度連続していることを利用する。
配列 $DC$ を用意し、これの累積和を $DP$ とする。
つまり $DP[i] = DC[1]+DC[2]+...+DC[i]$ となるように、$DC$ の方を管理する。
すると、たとえば「$DP[4]～DP[7]$ に一律に $x$ を足す」操作は、「$DC[4]$ に $x$、$DC[8]$ に $-x$ を足す」操作に置き換えられる。
これを用いて何マス進むかの遷移を高速化する。
Fenwick Treeを用いると累積和の更新・取得を $O(\log{N})$ で管理できるので、$K \le 10$ 通りの区間で1回の取得と2回の更新を行っても、たかだか定数倍。 全体で $O(NK\log{N})$ となる。
import sys
class BinaryIndexedTree:
def __init__(self, n, MOD):
self.size = n
self.tree = [0] * (n + 1)
self.depth = n.bit_length()
self.MOD = MOD
def sum(self, i):
s = 0
while i > 0:
s += self.tree[i]
i -= i & -i
return s % self.MOD
def add(self, i, x):
mod = self.MOD
while i <= self.size:
self.tree[i] = (self.tree[i] + x) % mod
i += i & -i
def lower_bound(self, x):
sum_ = 0
pos = 0
for i in range(self.depth, -1, -1):
k = pos + (1 << i)
if k <= self.size and sum_ + self.tree[k] < x:
sum_ += self.tree[k]
pos += 1 << i
return pos + 1, sum_
n, k, *lr = map(int, sys.stdin.buffer.read().split())
lr = list(zip(lr[0::2], lr[1::2]))
MOD = 998244353
bit = BinaryIndexedTree(n + 2, MOD)
bit.add(1, 1)
bit.add(2, -1)
for i in range(1, n):
v = bit.sum(i)
for l, r in lr:
bit.add(i + l, v)
bit.add(min(i + r + 1, n + 1), -v)
print(bit.sum(n))
E - Sequence Sum
問題
- $A_1=X$、$A_{i+1}=A_i^2 \% M$ である数列について、$\displaystyle \sum_{i=1}^{N}A_i$ を求めよ
- $A_i$ の要素は $M$ で割った余りをとるが、和を求める部分では割らないことに注意
- $1 \le N \le 10^{10}$
- $0 \le X \le M \le 10^5$
解法
$A_i$ はループする性質を利用する。
$A_i$ の要素は最大でも $M$ 通りの値しか取らないし、一度同じ値を取ったらそこからの操作は全く一緒なので全く同じ値が繰り返される。
よって、まずはそのまま $A_1,A_2,...$ を求めていく。
過去に出現した値が再出現したら、ループ位置と長さを求める。
X=2, M=55
2, 4, 16, 36, 31, 26, 16, 36, 31, ...
|------||--------------|
ループ前 ループ
A B
ループは $(N-A)/B$（切り捨て）回繰り返され、残り $(N-A)\%B$ 個余る。
たとえば $N=20$ なら、4回ループして2個余るので、以下のように求められる。
- $(2+4) + (16+36+31+26) \times 4 + (16+36)$
他には、ダブリングで1個先、2個先、4個先、8個先、…の要素を求めていく方法でも解ける。
def solve(n, x, m):
result = [x]
checked = [0] * m
checked[x] = 1
while len(result) < n:
x = x * x % m
if checked[x] > 0:
break
result.append(x)
checked[x] = len(result)
else:
return sum(result)
l = len(result)
i = checked[x]
before_len = i - 1
loop_len = l - i + 1
loop_sum = sum(result[before_len:])
d, e = divmod(n - before_len, loop_len)
ans = sum(result[:before_len]) + loop_sum * d + sum(result[before_len:before_len + e])
return ans
n, x, m = map(int, input().split())
print(solve(n, x, m))
F - Simplified Reversi
問題
- $N \times N$ の盤面で、単純化されたリバーシをする
- 中央の $N-2 \times N-2$ マスには黒が、右端と下端にはそれぞれ白が置かれている
- 白い石を $Q$ 回置く
- 置く石は、以下の2通りのクエリで表現される
1 x: 最上段の左から $x$ 列目に置く2 x: 最左列の上から $x$ 行目に置く
- リバーシのように、白い石に挟まれた黒い石はひっくり返される
- 最終的に残っている黒い石の個数を求めよ
- $3 \le N \le 2 \times 10^5$
- $0 \le Q \le 2 \times 10^5$
- クエリは全て異なる
解法
AtCoder-Libraryが発表された折に遅延伝播セグメント木を用意したら、もっと賢い方法はありそうだけどついそれ使っちゃう。
以下の情報を持っておきたい。
- $H[i]=$ 上から $i$ 列目に今、石を置かれたらひっくり返される黒の個数
- $V[j]=$ 左から $j$ 列目に今、石を置かれたらひっくり返される黒の個数
はじめはそれぞれ $i=2～N-1$ について $N-2$ で初期化されている。他の $i$ については特に利用しないので未定義でよい。
N=5
i 2 3 4 H
j 2 ●●● 3
2 ●●● 3
4 ●●● 3
V 3 3 3
黒は $(N-2) \times (N-2)$ 個あり、そこからひっくり返される分を引いていく。
以下、縦方向にひっくり返される分について考える。横方向も軸を入れ替えて同様に考えればよい。
縦方向のクエリ
$j$ 列目に置かれたら、その時の $V[j]$ の値だけ黒が減る。他の列に関しては特に影響なし。
横方向のクエリ
縦方向にひっくり返されることは無いが、$V$ を更新する必要がある。
$i$ 行目に置かれると、横方向に $H[i]$ 個ひっくり返される。$k=H[i]$ とする。
するとそれ以降、$V[2]～V[k+1]$ に関しては、「現在の値と $i-2$ の小さい方」に置き換えられる。
i=4 2 3 4 5 6 ●●●○● ●●●○● ●●●○● ●●●○● ●●●○● → ○○○○● k=3 ●●●○● ●●●○● ●●●○● ●●●○● ５５５５５ ２２２５５
なので、縦方向と横方向のそれぞれで、最小値について1点取得と範囲更新ができるデータ構造を持っておけばよい。
import os
import sys
import numpy as np
def solve(inp):
SEGTREE_TABLES = []
COMMON_STACK = np.zeros(10 ** 7, dtype=np.int64)
INF = 10 ** 18
def bit_length(n):
ret = 0
while n:
n >>= 1
ret += 1
return ret
def segtree_init(n):
n2 = 1 << bit_length(n)
table = np.full((n2 << 1, 2), INF, dtype=np.int64)
SEGTREE_TABLES.append(table)
return len(SEGTREE_TABLES) - 1
def segtree_build(ins, arr):
table = SEGTREE_TABLES[ins]
offset = table.shape[0] >> 1
table[offset:offset + len(arr), 0] = arr
for i in range(offset - 1, 0, -1):
ch = i << 1
table[i, 0] = min(table[ch, 0], table[ch + 1, 0])
def segtree_eval(table, offset, i):
lazy_min = table[i, 1]
if i < offset:
ch = i << 1
table[ch, 1] = min(table[ch, 1], lazy_min)
table[ch + 1, 1] = min(table[ch + 1, 1], lazy_min)
table[i, 0] = min(table[i, 0], lazy_min)
table[i, 1] = INF
def segtree_bottomup(table, i):
lch = i << 1
rch = lch + 1
l_dat = min(table[lch, 0], table[lch, 1])
r_dat = min(table[rch, 0], table[rch, 1])
table[i, 0] = min(l_dat, r_dat)
def segtree_range_update(ins, l, r, mn):
table = SEGTREE_TABLES[ins]
offset = table.shape[0] >> 1
stack = COMMON_STACK
stack[:3] = (1, 0, offset)
si = 3
updated = []
while si:
i, a, b = stack[si - 3:si]
segtree_eval(table, offset, i)
if b <= l or r <= a:
si -= 3
continue
if l <= a and b <= r:
table[i, 1] = min(table[i, 1], mn)
si -= 3
continue
updated.append(i)
m = (a + b) // 2
stack[si - 3:si] = (i << 1, a, m)
stack[si:si + 3] = ((i << 1) + 1, m, b)
si += 3
while updated:
i = updated.pop()
segtree_bottomup(table, i)
def segtree_query(ins, l, r):
""" sum [l, r) """
table = SEGTREE_TABLES[ins]
offset = table.shape[0] >> 1
stack = COMMON_STACK
stack[:3] = (1, 0, offset)
si = 3
res = INF
updated = []
while si:
i, a, b = stack[si - 3:si]
segtree_eval(table, offset, i)
if b <= l or r <= a:
si -= 3
continue
if l <= a and b <= r:
res = min(res, table[i, 0])
si -= 3
continue
updated.append(i)
m = (a + b) // 2
stack[si - 3:si] = (i << 1, a, m)
stack[si:si + 3] = ((i << 1) + 1, m, b)
si += 3
while updated:
i = updated.pop()
segtree_bottomup(table, i)
return res
def segtree_debug_print(ins):
table = SEGTREE_TABLES[ins]
offset = table.shape[0] >> 1
for t in range(2):
i = 1
while i <= offset:
print(table[i:2 * i, t])
i <<= 1
n = inp[0]
q = inp[1]
ops = inp[2::2]
xxx = inp[3::2]
ins1 = segtree_init(n - 2)
ins2 = segtree_init(n - 2)
init = np.full(n - 2, n - 2, dtype=np.int64)
segtree_build(ins1, init)
segtree_build(ins2, init)
ans = (n - 2) * (n - 2)
for qi in range(q):
o = ops[qi]
x = xxx[qi]
if o == 1:
k = segtree_query(ins1, x - 2, x - 1)
ans -= k
segtree_range_update(ins2, 0, k + 1, x - 2)
else:
k = segtree_query(ins2, x - 2, x - 1)
ans -= k
segtree_range_update(ins1, 0, k + 1, x - 2)
# print(qi, o, x, k, ans)
# segtree_debug_print(ins1)
# segtree_debug_print(ins2)
return ans
if sys.argv[-1] == 'ONLINE_JUDGE':
from numba.pycc import CC
cc = CC('my_module')
cc.export('solve', '(i8[:],)')(solve)
cc.compile()
exit()
if os.name == 'posix':
# noinspection PyUnresolvedReferences
from my_module import solve
else:
from numba import njit
solve = njit('(i8[:],)', cache=True)(solve)
print('compiled', file=sys.stderr)
inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)
