本日は12/25
- アドベントカレンダー最終日！
というわけで振り返りの記事。
12月ハイライト
- モチベーション維持と地力向上のためにD問題をたくさん解いた
- ABCで久々にratedに参加して一瞬だけ入緑
- 友人からもらったテンプレートのフィードバックに回答
モチベーション維持と地力向上のためにD問題をたくさん解いた
普段は週1問程度しかD問題を解かないのだが、ABC開催日とその次の日を除き、
大抵の日はD問題を1問ずつ解いて過ごした。
イベントだからやろうというモチベーションをうまく利用して多少なりとも精進できたのが良かった
ABCで久々にratedに参加して一瞬だけ入緑
ABC436で4完した結果、3回目の入緑を達成。
その次のABC437は3完止まりで結局茶色レートに戻ってしまったものの、D問題を解くことができた。
問題を解く頻度を少し上げたからなのか、多少なりとも地力が上がったのではないかと思った。
友人からもらったテンプレートのフィードバックに回答
友人に競プロについて話す機会があり、テンプレートのpyファイルを共有したら、
いくつか質問を頂いたので、記事にした。
ネタ提供に感謝
まとめ
今年もアドベントカレンダーで25記事作成できた
週単位でしか作成していなかった記事を毎日ペースで作成するとなると、
少し慌ただしかったが、その分アウトプットの時間が確保でき、色々学んだことがあった。
おまけ：今月解いた問題でのテクニック紹介
GPTに今月解いた記事を渡して有用性のあるテクニックを抽出してもらったので以降で紹介
- 個数管理 + 差分更新（置換クエリで総和を一瞬で更新）
- Top-K を保つなら
heapq（ソート挿入はだいたい負ける） - BFS は「状態を足す」と急に解ける（方向・回数・フラグ）
- 「BFSっぽい」キュー駆動シミュレーション（伝播条件があるやつ）
- 尺取法 + 累積和（「条件付きの和」を式で割る）
- 二分探索（答えを直接探さず「条件を満たすか」を判定する）
- imos 法（区間加算→最後に累積して一気に復元）
- 2次元 imos を「個数」と「番号合計」で二重に回す
- 転倒数 + FenwickTree（BIT）で「交換回数」を O(N log N)
- SortedSet / セグ木 / ヒープ：順序付き集合の選び方
- セグ木は「値」じゃなくて「ペア」を載せると世界が広がる
- ユークリッドの互除法は「引き算をまとめる」テクとして覚える
- 順列は「サイクル」に落とすと計算が一気に楽になる
- Trie 木：配列や文字列を「共通prefixでまとめる」
- Python実装のスピード小ネタ（地味に効く）
1. 個数管理 + 差分更新（置換クエリで総和を一瞬で更新）
定義: b → c みたいな「値の置換」が何度も来るとき、配列を更新せず 値ごとの個数 と 総和 だけ更新するテク。
要点
-
cnt[x] = 値xの個数を持つ（Counterが強い） - 置換
b→cならS += (c-b) * cnt[b] -
cnt[c] += cnt[b],cnt[b] = 0
from collections import Counter
cnt = Counter(A)
S = sum(A)
for b, c in queries:
k = cnt[b]
if k:
S += (c - b) * k
cnt[c] += k
cnt[b] = 0
print(S)
落とし穴
- 配列を全部書き換えて O(NQ) にして爆発しがち
（参考: ABC171Dを解いた【個数管理+差分更新】 #Python - Qiita）
2. Top-K を保つなら heapq（ソート挿入はだいたい負ける）
定義: 常に「上位K個」だけ持ちたいとき、最小ヒープに K 個を保って、あふれたら捨てる。
要点
- ヒープ先頭は常に最小
- 「K個の中の最小」が答え、みたいな問題に直撃
import heapq
hq = []
for a in A:
heapq.heappush(hq, a)
if len(hq) > K:
heapq.heappop(hq)
# len==K のとき、hq[0] が「K個の中の最小」
比較
-
insortでソート配列維持: 1回 O(N) → 合計 O(N^2) になりやすい - ヒープ: 1回 O(log K) → 合計 O(N log K)
（参考: ABC234Dを解いた【優先度付きキュー】 #Python - Qiita）
3. BFS は「状態を足す」と急に解ける（方向・回数・フラグ）
定義: 盤面最短路でも制約があるなら「マス」だけじゃ足りない。
(y, x, state) に拡張して BFS する。
要点
- 例: 「直前の移動方向と違う方向にしか進めない」
→state = 0(縦), 1(横)を持つ -
dist[y][x][state]で距離管理
from collections import deque
INF = 10**18
dist = [[[INF]*2 for _ in range(W)] for _ in range(H)]
q = deque()
dist[sy][sx][0] = dist[sy][sx][1] = 0
q.append((sy, sx, 0))
q.append((sy, sx, 1))
while q:
y, x, s = q.popleft()
for ny, nx, ns in transitions(y, x, s):
if dist[ny][nx][ns] > dist[y][x][s] + 1:
dist[ny][nx][ns] = dist[y][x][s] + 1
q.append((ny, nx, ns))
（参考: ABC387Dを解いた【BFS】 #Python - Qiita）
4. 「BFSっぽい」キュー駆動シミュレーション（伝播条件があるやつ）
定義: 最短路じゃなくても、条件を満たしたら隣へ波及する処理は キュー が最強。
要点
- 初期に「確定している点」を全部キューに入れる（マルチソース）
- 周囲の状態が変わったときだけ再チェックする
from collections import deque
q = deque(initial_cells)
while q:
y, x = q.popleft()
for ny, nx in neighbors(y, x):
if can_update(ny, nx):
apply(ny, nx)
q.append((ny, nx))
（参考: ABC425Dを解いた【BFSっぽいけど違かった】 #Python - Qiita）
5. 尺取法 + 累積和（「条件付きの和」を式で割る）
定義: 片方固定で、もう片方を伸ばしていく二本ポインタ。
「境界を超えたら値が固定」みたいな和は 累積和で一括が勝ち。
要点
- ソート後、ポインタは基本戻さない → O(N)
- 「どこから先は固定値」な境界を見つけて、残りは累積和でまとめる
（参考: ABC321Dを解いた【尺取法】 #Python - Qiita）
6. 二分探索（答えを直接探さず「条件を満たすか」を判定する）
定義: X が大きいほど条件が単調に変わるなら、境界は二分探索で取れる。
要点
-
ok(X)を作る（例: X以下に何個ある？） - 境界を詰めるだけ、という発想に切り替える
def ok(x):
return count(x) >= K
l, r = 0, 10**18
while r - l > 1:
m = (l + r) // 2
if ok(m):
r = m
else:
l = m
print(r)
（参考: ABC341Dを解いた【二分探索】 #Python - Qiita）
7. imos 法（区間加算→最後に累積して一気に復元）
定義: 区間 [l, r) を何回も足すなら、端点だけ更新して最後に累積。
要点
-
diff[l] += 1,diff[r] -= 1 - 最後に
cur += diff[i]で復元
diff = [0]*(MAX+2)
for l, r in segs:
diff[l] += 1
diff[r] -= 1
cur = 0
for i in range(MAX+1):
cur += diff[i]
cover[i] = cur
（参考: ABC256Dを解いた【imos法】 #Python - Qiita）
8. 2次元 imos を「個数」と「番号合計」で二重に回す
定義: 長方形塗りつぶし大量処理の定番。
さらに「ちょうど1つだけ覆うセルの所属ID」まで欲しいなら 2枚持つ。
要点
-
cc: 何枚重なってるか（カウント） -
ck: 重なっている雲番号の合計
→cc==1のときckがそのままID
# cc, ck に同じ長方形更新を流す（ccは+1、ckは+id）
# その後、2次元累積で復元
if cc[y][x] == 1:
owner = ck[y][x]
（参考: ABC434Dを解いた【2次元imos法】 #Python - Qiita）
9. 転倒数 + FenwickTree（BIT）で「交換回数」を O(N log N)
定義: 転倒数 = i < j なのに A[i] > A[j] なペア数。
バブルソートの交換回数と一致。
要点
- BITで「これまで見た値の個数」を管理
-
i - (今までに見た <= a の個数)を足す
# 座標圧縮した a を 0..M-1 にする前提
ans = 0
for i, a in enumerate(A):
le = bit.sum(a+1) # <= a の個数
ans += i - le
bit.add(a, 1)
（参考: ABC264Dを解いた【転倒数】 #Python - Qiita, ABC244Dを解いた【転倒数】 #Python - Qiita）
10. SortedSet / セグ木 / ヒープ：順序付き集合の選び方
定義: 「最小を取りたい」「削除したい」「挿入したい」が混ざるときの道具箱。
ざっくり比較
-
heapq：最小取得は速い、任意削除は弱い（遅延削除でカバー） -
SortedSet：最小取得・挿入・削除が全部強い（環境が許せば） -
segtree：値域が狭い/圧縮できるなら最強クラス
（参考: ABC294Dを解いた【SortedSet】 #Python - Qiita）
11. セグ木は「値」じゃなくて「ペア」を載せると世界が広がる
定義: 各ノードに (個数, 個数×値) みたいな情報を載せて、区間の集計を直接取る。
要点
-
op((c1,s1),(c2,s2))=(c1+c2, s1+s2)が作れれば勝ち - 区間内の「個数」と「総和」が同時に出せる
（参考: ABC432Eを解いた【セグ木】 #Python - Qiita）
12. ユークリッドの互除法は「引き算をまとめる」テクとして覚える
定義: gcd(a,b) のやつ。競プロだと「何回引けるか」を数える形で出る。
要点
-
a = q*b + rなので、aからbをq回引くのを一発処理できる - ループは
a, b = b, a % b
ans = 0
if a < b: a, b = b, a
while b:
ans += a // b
a, b = b, a % b
print(ans - 1)
（参考: ABC297Dを解いた【ユークリッドの互除法】 #Python - Qiita）
13. 順列は「サイクル」に落とすと計算が一気に楽になる
定義: i -> P[i] の辺を張ると、グラフはサイクルの集合になる。
要点
- サイクル長
cのペア数はC(c,2)=c(c-1)/2 - 全体は
Σ c(c-1)/2みたいに合算できることがある
（参考: ABC436Eを解いた【サイクルの計算】 #Python - Qiita）
14. Trie 木：配列や文字列を「共通prefixでまとめる」
定義: prefix を共有する列を木にまとめて、同じprefixの処理をまとめる構造。
要点
- ノード = prefix
- 同じ配列（同じprefix列）は同じノードに合流するように管理
（参考: ABC437Eを解いた【trie木】 #Python - Qiita）
Python実装のスピード小ネタ（地味に効く）
-
上限が決まってる配列は、
dict/defaultdictよりlistが速いことが多い
（添字を雑に扱うと、平気でTLE寄りに寄る） -
itertools.productに寄せても速くならないケースは普通にある（読みやすさ優先ならアリ）