ABC179

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

C - A x B + C

• 

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

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

  • 最初N - 1をN - A + 1にしてた
    • A==2だとあってしまう
  • A=3, N=10の時 (3, 1, 7), (3, 2, 4), (3, 3, 1)
  • A=3, N=9の時 (3, 1, 6), (3, 2, 3)
  • ここから (N - 1) // Aとわかる python

def solve(N):
    ret = N - 1
    for i in range(2, N + 1):
        ret += (N - 1) // i
    return ret

ABC179D E - Sequence Sum

• 

• ループ検出

  • やたら変数に束縛してるのは、printしてデバッグしたからです
    • loop_startが1ずれてたのとloop_tailを末尾からとってたバグ
  • ループの開始点を見つけるのはO(1)
    • visited が0の時は未出現で、非0の時は最初に出現した位置+1

python

def solve(N, X, M):
    visited = [0] * M
    a = X
    ret = []
    for i in range(N):
        if visited[a]:
            s = sum(ret)
            loop_start = visited[a] - 1
            loop_end = i
            loop_sum = sum(ret[loop_start:loop_end])
            loop_length = loop_end - loop_start
            loop_count = (N - i) // loop_length
            loop_left = (N - i) % loop_length
            loop_tail = sum(ret[loop_start:loop_start + loop_left])
            return s + loop_count * loop_sum + loop_tail
        ret.append(a)
        visited[a] = (i + 1)
        a = (a * a) % M

    return sum(ret)

• Twitter見てたらダブリングで解いた人も居たみたい？

F - Simplified Reversi

• 
• 範囲更新、点取得なので双対セグメント木で良い
  • のだが、相対セグメント木だけ自作コードの整理がまだだった…
  • 残り10分だったので焦ってしまった
• 値が変化する点を二分探索という手もある
  • だが、Pythonのbisectはソート済み配列を要求する
  • この問題条件だと配列への挿入が発生してO(N)になるから良くないね
  • 本質的にはPythonで使える平衡二分木をすぐ取り出して使えるように準備しとくべきなのかなー
  • 今回の問題に限れば「先頭以外への追加は必要ない」ので、逆順で持てば末尾追加でO(1)になるが、トリッキーだよなぁ
• 逆順で持って二分探索するバージョン python

def main():
    from bisect import bisect_left
    N, Q = map(int, input().split())
    ret = (N - 2) ** 2
    xs = [-N]
    xvals = [N - 2]
    ys = [-N]
    yvals = [N - 2]
    for _q in range(Q):
        q, x = map(int, input().split())
        if q == 1:
            i = bisect_left(xs, -x)
            ret -= xvals[i - 1]
            if i == len(xs) and yvals[-1] > x - 2:
                ys.append(-xvals[i - 1] - 2)
                yvals.append(x - 2)
        else:
            y = x
            i = bisect_left(ys, -y)
            ret -= yvals[i - 1]
            if i == len(ys) and xvals[-1] > y - 2:
                xs.append(-yvals[i - 1] - 2)
                xvals.append(y - 2)

    print(ret)

• 点取得だから遅延セグメント木がはなく双対セグメント木で十分なのだが、遅延セグメント木を使って解いてる人もたくさんいるからそれでよかったのかもなぁ
• 関連記事
  • https://hackmd.io/@tatyam-prime/DualSegmentTree