ABC179
Dが難しかったので先にEを解いてから戻って解いて5問正解
飛び飛びに存在する解がいくつあるか数える問題
切り上げ切り捨てでバグりがち
最初
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 とわかるpythondef solve(N):
ret = N - 1
for i in range(2, N + 1):
ret += (N - 1) // i
return ret
やたら変数に束縛してるのは、printしてデバッグしたからです
loop_startが1ずれてたのとloop_tailを末尾からとってたバグ
ループの開始点を見つけるのはO(1)
visited が0の時は未出現で、非0の時は最初に出現した位置+1pythondef 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見てたらダブリングで解いた人も居たみたい？
範囲更新、点取得なので双対セグメント木で良い
のだが、相対セグメント木だけ自作コードの整理がまだだった…
残り10分だったので焦ってしまった
値が変化する点を二分探索という手もある
だが、Pythonのbisectはソート済み配列を要求する
この問題条件だと配列への挿入が発生してO(N)になるから良くないね
本質的にはPythonで使える平衡二分木をすぐ取り出して使えるように準備しとくべきなのかなー
今回の問題に限れば「先頭以外への追加は必要ない」ので、逆順で持てば末尾追加でO(1)になるが、トリッキーだよなぁ
逆順で持って二分探索するバージョン
pythondef 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)点取得だから遅延セグメント木がはなく双対セグメント木で十分なのだが、遅延セグメント木を使って解いてる人もたくさんいるからそれでよかったのかもなぁ
関連記事
Related Pages
- →ダブリング×連結成分ごとに解けば良い×unionfind×辺を頂点にして二部グラフ×二部グラフの最大マッチング×根つき木に変換×辺の深さ優先探索×一つ構築せよ問題×端から埋める×floor_sum→
- →オイラー路×グリッド上の幅優先探索×ハンガリアン法×二部グラフの最大マッチング×二重辺連結成分分解×二重頂点連結成分分解×全点対間最短路×単一始点最短路×強連結成分分解×彩色数×最大クリーク×最大流×最大独立集合×最小全域有向木×最小全域木×最小流量制限付き最大流×最小費用流×橋/関節点×bit×binary-trie×convex-hull-trick-add-monotone×li-chao-tree×link-cut木_部分木クエリ×link-cut木×ウェーブレット行列×スパーステーブル×スライド区間の昇順k個の和×セグメント木×トライ木×マージ可能ヒープ×列の平方分割×平衡二分探索木×永続配列×素集合データ構造×unionfind×ローリングハッシュ×接尾辞配列×最長共通接頭辞×最長回文×回文×複数文字列検索×hl分解×全方位木dp×最小共通祖先×木の直径×木の重心分解×根付き木に変換×mod-pow×オイラーのφ関数×オイラーのφ関数テーブル×ベル数×ラグランジュ補間×二項係数×二項係数テーブル×任意mod畳み込み×分割数×分割数テーブル×商列挙×形式的冪級数×形式的べき級数×拡張ユークリッドの互除法×拡張ユークリッド互除法×第2種スターリング数×約数列挙×素因数分解×素数テーブル×素数判定×組合せ×行列演算×進数変換×階乗×離散対数問題×高速フーリエ変換×divide-and-conquer-optimization×monotone-minima×スライド最小値×一次元累積和×二次元累積和×個数制限付きナップサック×最大長方形×最適二分探索木×最長増加部分列×ダブリング×包除原理×燃やす埋める問題×燃やす埋める×牛ゲー×mo’s_algorithm×offline-dynamic-connectivity×座標圧縮×アルゴリズム→
- →アルゴリズム×蟻本×区間スケジューリング×二分探索木×unionfind×最短路問題×最小全域木×ユークリッドの互除法×ニ分探索×しゃくとり法×半分全列挙×座標圧縮×セグメント木×binary_lndexed_tree×バケット法×平方分割×ビットdp×bitdp×行列累乗×繰り返し二乗法×最大流×最小カット×二部マッチング×一般マッチング×マッチング×辺カバー×安定集合×点カバー×最小費用流×凸包×grundy数×強連結成分分解×2-sat×lca×ダブリング×接尾辞配列×sparse_table×rmq×atcoder→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]