−目次
AtCoder Beginner Contest 179 D,E,F問題メモ
モノポリーは刑務所過ぎたオレンジあたりの土地が強い。知らんけど。
D - Leaping Tak
問題
- 一列に並んだ N マスを、1から N まで移動する
- 移動の方法は、以下の通り
- 共通部分を持たない K 個の区間 [L1,R1],[L2,R2],...,[LK,RK] が与えられる
- 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}) となる。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
import sysclass 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 = 998244353bit = 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個先、…の要素を求めていく方法でも解ける。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
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 ansn, 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点取得と範囲更新ができるデータ構造を持っておけばよい。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 |
import osimport sysimport numpy as npdef 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 ansif 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 solveelse: 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) |
