AtCoder Libraryを使える問題が出されるコンテスト。
BをケアレスミスしたことにCの提出後に気づき修正、Dを実装してサンプルを通してから提出したもののWAで、Eを見たら遅延伝搬セグメント木だなと思ったのでそちらを解く。何度か失敗してAC。Dに戻って「これはセグメント木でDPだな」と気づいたが、その時点で残り10分。間に合わず。
うわ、あと9ポイントで水色！惜しい！
- ケアレスミスした
- 大急ぎで直したので不格好な条件式 python
A, B, C, D = map(int, input().split())
# if A <= D <= B or A <= C <= B: # NG
if A <= D <= B or A <= C <= B or C <= A <= D:
print("Yes")
else:
print("No")
- 落ち着いて考えるとこう python
A, B, C, D = map(int, input().split())
if D < A or B < C:
print("No")
else:
print("Yes")
def solve(N, M, edges):
init_unionfind(N)
for e in edges:
unite(e[0] - 1, e[1] - 1)
s = set(find_root(x) for x in range(N))
return len(s) - 1
- どうACLに帰着するのかわからないのでまずは素朴に書く
- 提出したが WA/TLE混じり
- WAが取れてもTLEだろうし、どう解決するか目処が付いてないので一旦保留してEをやった
- 戻ってきて見直してみて、なるほどこれはセグメント木で動的計画法だなと気づいたが、残り10分だった
- 末尾の値を定義域、最長の長さを値域とする動的計画法
- 集めるDP
- i番目の値がAの時、Aの前後K個の値のmaxが「i番目の値をつなげることのできる最も長い列」なので、それに1足したもので更新
- 下記でサンプルは通る python
def solve(N, K, AS):
count = [0] * 300_000
count[AS[0]] = 1
for i in range(1, N):
A = AS[i]
start = max(0, A - K)
best = max(count[start:A + K + 1])
count[A] = best + 1
return max(count)
- 点更新範囲maxなのでセグメント木が使える
- セグメント木バージョン AC python
def solve(N, K, AS):
MAX_CAPACITY = 300_000
set_width(MAX_CAPACITY + 10)
count = [0] * SEGTREE_SIZE
point_set(count, AS[0], 1, max)
for i in range(1, N):
A = AS[i]
start = max(0, A - K)
end = min(A + K + 1, MAX_CAPACITY + 1)
best = range_reduce(count, start, end, max, -INF)
point_set(count, A, best + 1, max)
return range_reduce(count, 0, MAX_CAPACITY + 1, max, -INF)
- ハマりポイント
- Pythonのリストは`count[start:end]`でendが範囲外でも許されるが、セグメント木はそうではない
- `MAX_CAPACITY`を含むので+1が必要
-
-
範囲更新するので双対セグメント木かなと思った
-
クエリのたびに「20万桁の十進数とみなしてあまりを計算」って処理が走るのは範囲縮約だから遅延伝搬セグメント木が適当
-
この処理をするための値の二項演算が
(a * 10 + b) % MODだと勘違いした- 実際には右側の数字の桁数をsizeとして
(a * (10 ** size) + b) % MOD - 二項演算がsizeを引数に取らないので大急ぎで自作ライブラリを手直しした
- 別解
-
E は、(長さ、sum）を持ちました。 (10^n, sum) を持った方が mod pow を使わずに済んで計算量が良いと思います。
-
- 実際には右側の数字の桁数をsizeとして
-
20万桁の十進数になるので
11111111や10000000のあまりを前計算しておく python
def main():
# parse input
N, Q = map(int, input().split())
set_width(N + 1)
value_unity = 0
value_table = [value_unity] * SEGTREE_SIZE
value_table[NONLEAF_SIZE:NONLEAF_SIZE + N] = [1] * N
action_unity = None
action_table = [action_unity] * SEGTREE_SIZE
cache11 = {}
i = 1
p = 1
step = 10
while i <= N:
cache11[i] = p
p = (p * step + p) % MOD
step = (step * step) % MOD
i *= 2
cache10 = {0: 1}
i = 1
p = 10
while i <= N:
cache10[i] = p
p = (p * 10) % MOD
i += 1
def action_force(action, value, size):
if action == action_unity:
return value
# return int(str(action) * size)
return (cache11[size] * action) % MOD
def action_composite(new_action, old_action):
if new_action == action_unity:
return old_action
return new_action
def value_binop(a, b, size):
# return (a * (10 ** size) + b) % MOD
return (a * cache10[size] + b) % MOD
full_up(value_table, value_binop)
for _q in range(Q):
l, r, d = map(int, input().split())
lazy_range_update(
action_table, value_table, l - 1, r, d,
action_composite, action_force, action_unity, value_binop)
ret = lazy_range_reduce(
action_table, value_table, 0, N, action_composite, action_force, action_unity,
value_binop, value_unity)
print(ret)
- 平方分割で解いたとTwitterに書いてる人がいる
F