ABC179

Dが難しかったので先にEを解いてから戻って解いて5問正解

https://gyazo.com/1b1cfda315bbb1cd751451ec5b3ff6de

https://gyazo.com/26cf926e3eaf69b4d5887fc799ae4ed5

飛び飛びに存在する解がいくつあるか数える問題

切り上げ切り捨てでバグりがち

A=3, N=10の時 (3, 1, 7), (3, 2, 4), (3, 3, 1)

A=3, N=9の時 (3, 1, 6), (3, 2, 3)

code:python

def solve(N):

ret = N - 1

for i in range(2, N + 1):

ret += (N - 1) // i

return ret

https://gyazo.com/e62eff03c360b9b33d1aa6475b91817a

やたら変数に束縛してるのは、printしてデバッグしたからです

loop_startが1ずれてたのとloop_tailを末尾からとってたバグ

ループの開始点を見つけるのはO(1)

code:python

def solve(N, X, M):

a = X

ret = []

for i in range(N):

s = sum(ret)

loop_end = i

loop_length = loop_end - loop_start

loop_count = (N - i) // loop_length

loop_left = (N - i) % loop_length

return s + loop_count * loop_sum + loop_tail

ret.append(a)

a = (a * a) % M

return sum(ret)

https://gyazo.com/c75f91099aca8b95b10f33faaa847edb

のだが、相対セグメント木だけ自作コードの整理がまだだった…

残り10分だったので焦ってしまった

値が変化する点を二分探索という手もある

だが、Pythonのbisectはソート済み配列を要求する

この問題条件だと配列への挿入が発生してO(N)になるから良くないね

本質的にはPythonで使える平衡二分木をすぐ取り出して使えるように準備しとくべきなのかなー

今回の問題に限れば「先頭以外への追加は必要ない」ので、逆順で持てば末尾追加でO(1)になるが、トリッキーだよなぁ

逆順で持って二分探索するバージョン

code:python

def main():

from bisect import bisect_left

N, Q = map(int, input().split())

ret = (N - 2) ** 2

for _q in range(Q):

q, x = map(int, input().split())

if q == 1:

i = bisect_left(xs, -x)

yvals.append(x - 2)

else:

y = x

i = bisect_left(ys, -y)

xvals.append(y - 2)

print(ret)

関連記事