競技プログラミングで使えるかもしれない、Pythonの小ネタを集めました。
癖の強いものばかりですが、ご笑納頂ければ幸いです。
更新履歴
2025/08/14更新:
・誤字を修正しました。
・bit_lengthの実装例を追加しました。
2025/08/15更新:
・区間代入・区間(最小/最大)値のassertにバグがあったので修正しました。
過去のPython宴会芸へのリンク
ローカル関数で高速化
PyPyはJITコンパイル機能を有しています。
筆者はあまり詳しくないのですが、これは頻繁に実行される演算を検知し、機械語にコンパイルして最適化する機能のようです。
実用上は以下のように解釈しています。
・ローカル関数内の
・1000回以上呼び出されるループを自動的に検知し
・その部分を機械語にコンパイルすることで、約20%程度高速にコードを実行する
特に「ローカル関数内」の条件が重要です。
どうやらPyPyはグローバル関数をトレースの対象に取りにくいようで、なかなかJITコンパイルをしてくれません。
そのため定数倍改善が必要な場面では、実行コードをできるだけローカル関数に移すことをおすすめします。
(補足: JIT以外の要因として、グローバル変数の辞書ルックアップの差もあるでしょう。どちらにしても、定数倍の改善が必要な場面ではローカル関数内での実行をおすすめします)
import random, time
random.seed(123_456_789)
N = 1000
start = time.perf_counter()
dist = [[random.getrandbits(62) for _ in range(N)] for _ in range(N)]
for k, dist_k in enumerate(dist):
for i, dist_i in enumerate(dist):
for j in range(N):
dist_i[j] = min(dist_i[j], dist_i[k] + dist_k[j])
print( f'{round( (time.perf_counter() - start) * 1000 )} ms' ) #2100 ms
#変更点: 先述のグローバルのコードをdef mainに移し、最後に実行用のmain()を追加
def main():
import random, time
random.seed(123_456_789)
N = 1000
start = time.perf_counter()
dist = [[random.getrandbits(62) for _ in range(N)] for _ in range(N)]
for k, dist_k in enumerate(dist):
for i, dist_i in enumerate(dist):
for j in range(N):
dist_i[j] = min(dist_i[j], dist_i[k] + dist_k[j])
print( f'{round( (time.perf_counter() - start) * 1000 )} ms' ) #1500 ms
main()
なお、ループ部分だけ関数化することでもPyPyが効率化してくれるようになります。
定数倍に困ったときは、頻繁なループだけでも関数内で実行するようにしましょう。
import random, time
random.seed(123_456_789)
N = 1000
start = time.perf_counter()
dist = [[random.getrandbits(62) for _ in range(N)] for _ in range(N)]
#Floyd-Warshallの最大ループ部分を関数化
def update_j(N, k, i, dist_k, dist_i):
for j in range(N):
dist_i[j] = min(dist_i[j], dist_i[k] + dist_k[j])
for k, dist_k in enumerate(dist):
for i, dist_i in enumerate(dist):
update_j(N, k, i, dist_k, dist_i)
print( f'{round( (time.perf_counter() - start) * 1000 )} ms' ) #1550ms
sys.stderr
長さ$N$の順列$P$: [$P_1$, $P_2$, ･･･, $P_N$] を与える。
以下の操作を任意の回数繰り返すことで、Pをソートできるか判定せよ。
操作: $1 \leq i < j \leq N$、$i + 2 \leq j$となるi, jを選び、$P_i$と$P_j$を交換する。
制約: $1 \leq N \leq 10^6$, $P$は[$1$, $2$, ･･･, $N$]を並び替えた順列入力例: N = 4, P = [2, 3, 1, 4]
出力例: Yes ([2, 3, 1, 4] → [4, 3, 1, 2] → [4, 2, 1, 3] → [3, 2, 1, 4] → [1, 2, 3, 4])
print(file = sys.stderr)とすると、出力先を標準出力からエラー出力に変更できます。
通常のプログラムの出力と区別したいデバッグ情報や、補助情報の出力に使うと便利です。
使用例として、例題をエスパーで解いてみましょう。
逆操作を考え、[1, 2, ･･･, N]から得られる順列Pを列挙することにします。
ここでソートできるものは標準出力へ、ソートできないものはエラー出力に出力先を分けると、「ソートできない数列」の条件を考えやすくなります。
N = 3
visited = { P := tuple(range(1, N + 1)) }
stack = [P]
while stack:
S = stack.pop()
for i in range(N):
for j in range(N):
if 0 <= i < j <= N - 1 and j - i != 1:
T = list(S)
T[i], T[j] = T[j], T[i]
if ( T := tuple(T) ) not in visited:
visited.add(T)
stack.append(T)
import sys, itertools
for S in itertools.permutations( range(1, N + 1) ):
if S in visited: #Sが操作でソートできる場合、標準出力へ
print(*S)
else: #ソートできない場合、エラー出力へ
print(*S, file = sys.stderr)
N = 3でコードを実行すると、画像のようにソートできる数列2通りとソートできない数列4通りが分かれて出力されている様子が確認できます。
N = 4で同様の実験をすると、標準エラー出力が空となり、全ての順列がソート可能であることがわかります。
さらにNを変更して同様の実験を行うと、
・N = 2のとき、[1, 2]はYes、[2, 1]はNo
・Nが1または5, 6, 7, ･･･のとき、すべてYes
となります。
以上よりNが大きい時は常にYesとなると予想できたので、Noとなる5通りの数列を埋め込み、「N = 2, 3の一部のケースだけNo、それ以外はYes」とするコードを提出すると、未証明でもACが得られます。
時間計算量は$O(1)$です。
(補足: $N \geq 5$ならソート可能なことは帰納法で証明できます。具体的には、sort(P[1, N - 1])とsort(P[2, N])を適切な順序で行えばソートできます)
セイウチ演算子
:=の演算子のことで、式の中で変数に代入する構文です。
コード中で値を代入しつつ、それを評価に使えるため、コードの行数を減らしたい場面で便利です。
活用例をいくつかご紹介します。
range内受け取り
range関数内でセイウチ演算子を宣言することで1行削減できます。
実用上はクエリ数Qをワンライナーで受け取る場合に使えます。
for _ in range( T := int(input()) ):
N, M = map(int, input().split())
for q in range( Q := int(input()) ):
Ti, Xi = map(int, input().split())
match Ti:
case 1: print('if Ti == 1')
case 2: print('elif Ti == 2')
case _: print('else')
heapqの宣言
たとえ変数宣言の対象がリストでも、セイウチ演算子なら関数呼び出しの中で変数宣言ができます。
random.shuffleでも同様に使えます。
import heapq
dist = vertex = 0
heapq.heapify( priority_queue := [(dist, vertex)] )
木のトポロジカルソート
木DPの際に、根つき木のBFS順序が欲しくなることがあります。
これはBFS順序を記録するリストにforループをかけ、リストの末尾に頂点をappendしていくテクニックが便利です。
さらにセイウチ演算子を使うと、forループのイテレータ生成とリストの初期化を同時に書けます。
for now, back in ( Q := [ (root := 0, parent := -1) ] ):
for nxt in G[now]:
if nxt != back: Q.append((nxt, now))
SegmentTreeの更新
whileループはセイウチ演算子の使いどころです。
特にセグメント木のループは、forループでfor _ in range(logN): i >>= 1と書くより定数倍に優れます。
i |= size
while ( i := i >> 1 ):
node[i] = f( node[i << 1], node[i << 1 | 1] )
Binary Indexed Tree
$A_0$, $A_1$, ･･･, $A_i$の総和を返すBIT.sum(i)関数を書きたいとします。
BITは1-indexedが便利なので補正してから、whileループをセイウチ演算子で書くと簡潔になります。
class BIT:
def sum(self, i):
ans = self._node[ i := i + 1 ]
while ( i := i ^ (i & - i) ): ans += self._node[i]
return ans
座標圧縮
数列$A$の重複する要素を削除し、昇順に並び替えて出力せよ。
入力例: $A = [3, 1, 4, 1, 5]$
出力例: $[1, 3, 4, 5]$
過去の記事でも取り上げましたが、セイウチ演算子を使う方法を紹介します。
2行で書けるのでシンプルですが、セイウチ演算子で代入したbackの変数はリスト内包の外でも参照可能なので、変数衝突に注意してください。
back = None
C = [back := Ai for Ai in sorted(A) if back != Ai]
yield
yieldを使うと、値を順に返すジェネレータ関数を作成できます。
値の列挙（生成）部分と処理部分を分離でき、コードを簡潔にできます。
サイズKの集合列挙
$0 \leq S < 2^N$で、1が立つビットの個数がちょうど$K$個となるような$S$を昇順に列挙します。
アルゴリズムの詳細は蟻本を参照してください。
#サイズKの集合列挙: 0 <= S < 2 ** N, S.bit_count() == K を満たすSを昇順に列挙する
#Reference: 秋葉拓哉ほか, 『プログラミングコンテストチャレンジブック 第2版』, P.144
def enumerate_k_combinations(N: int, K: int):
if not 0 <= K <= N:
return
if ( S := ~ (- 1 << K) ) == 0:
yield 0
return
while S < 1 << N:
yield S
S = (d := S + (LSB := S & - S)) | (S & ~ d) // LSB >> 1
#使用例
N = 4
for K in range(6):
print(f'{K = }, enumerate = {[S for S in enumerate_k_combinations(N, K)]}')
#K = 0, enumerate = [0]
#K = 1, enumerate = [1, 2, 4, 8]
#K = 2, enumerate = [3, 5, 6, 9, 10, 12]
#K = 3, enumerate = [7, 11, 13, 14]
#K = 4, enumerate = [15]
#K = 5, enumerate = []
#使用例2
for N in range(18):
for K in range(N + 1):
for S in enumerate_k_combinations(N, K):
pass #集合Sに対する処理
Θ(3^N) 部分集合列挙
集合Sの部分集合を2冪個降順に列挙します。
基本形は以下の通りです。
N = 18
for S in range(1 << N):
T = S
while T >= 0:
T &= S
pass #この行で、Sの部分集合Tに対する処理を行う
T -= 1
これをジェネレータ関数にすると、列挙部分を1行で呼び出せます。
#Θ(3^N)部分集合列挙: 0 <= T <= S, S & T == T を満たすSの部分集合Tを降順に列挙する
def enumerate_subsets(S: int):
T = S + 1
while T > 0:
T = (T - 1) & S
yield T
#使用例
N = 18
for S in range(1 << N):
for T in enumerate_subsets(S):
pass #この行で、Sの部分集合Tに対する処理を行う
ただし重大な注意点として、 この実装では実行速度が非常に遅くなります。
AtCoderのコードテストで比較してみたところ、前者は400msなのに対し後者は1300msと約3倍遅くなっていました。
原因はyieldのオーバーヘッドです。
yieldで各要素を返すたびに、ジェネレータ関数の一時停止・呼び出し・再開に相当するコストが発生してしまいます。
このため、部分集合列挙のような反復回数が膨大で、かつ各反復内が軽い処理では不利に働きます。
代案として、部分集合の列挙部分まではテンプレ化しておき、問題ごとに関数に直接処理を加筆する形式を提案します。
これなら可読性を保ちつつ、実行速度低下を防げます。
def exec_subsets(S: int):
T = S + 1
while T > 0:
T = (T - 1) & S
pass #この行で、Sの部分集合Tに対する処理を行う(問題ごとに加筆)
N = 18
for S in range(1 << N):
exec_subsets(S)
BFS
01-BFS
デックの代わりにスタック2本で01-BFSを行うテクニックは過去の記事でも取り上げましたが、距離のキーを別で持つと定数倍の改善ができます。
注意点として、距離distの変数は-1で初期化します。こうすることで、最初のスタック交換の後に距離がちょうど0になります。
Q, R = [], [start_vertex := 0]
dist = -1 #dist: 現在処理している距離。-1で初期化するので注意
while R:
Q, R = R, Q
dist += 1 #ここで1を足すので、distの初期化は-1にする
while Q:
now = Q.pop()
Dial's algorithm
Dial's algorithmはループの制御にany関数を使うと簡潔になります。
max_distance = 999 #辺の最大重み
shift = max_distance.bit_length()
bitmask = ~ ( - 1 << shift ) #(1 << shift) - 1 と等価
D = [[] for _ in range(1 << shift)]
D[0].append( start_vertex := 0 )
while any(D): #ダイアル内が空になるまで回したい → any関数で制御
for i, Di in enumerate(D):
while Di:
now = Di.pop()
グリッド上の探索
マス(h, w)がグリッド内かどうか確認するには、h in range(H) and w in range(W)と書くこともできます。
0 <= h < H and 0 <= w < Wのほうが高速なのですが、その日の気分で選んでもいいかと思います。
グリッド内の判定をさぼる方法もあります。
たとえば上下左右に1マスだけ移動できる場合、グリッドの下側に1行・右側に1列壁マスを足すだけで境界判定を省略できます。
H, W = 3, 6
S = ['..X...',
'X...X.',
'.XXXX.']
#Θ(HW)で外周に壁マス'X'を追加
for h in range(H): S[h] += 'X'
S.append( 'X' * (W + 1) )
for h in range(H + 1): print(S[h])
# ..X...X
# X...X.X
# .XXXX.X
# XXXXXXX
グリッド一次元化
2次元グリッドの管理はS[h][w]のようにアクセスするのが一般的ですが、[h]と[w]の2回のランダムアクセスが発生してしまい、定数倍が悪くなります。
そこでグリッドを一元化し、S[h * W + w]のようにアクセスするようにすると、ランダムアクセスの回数が減り、メモリ効率も改善します。
h * W + wの部分は間違えやすいので、個別に関数化するとスマートです。
なお、筆者はh << shift | wの方式を愛用しています (ここで、shift = (W - 1).bit_length()とします)。
論理和演算子の|は<<や+より演算の優先順位が低いので、たいていの場合は括弧でくくらなくても正しく動作します。
メモリ消費量は最大2倍になるので、そこだけご注意ください。
H, W = 3, 6
S = ['..X...',
'X...X.',
'.XXXX.']
#h * W + w での一次元化
T = ''.join(S[h][w] for h in range(H) for w in range(W))
convert = lambda h, w: h * W + w
assert all(S[h][w] == T[ convert(h, w) ] for h in range(H) for w in range(W))
#h << shift | w での一次元化
shift = (W - 1).bit_length()
is_road = bytearray(H << shift) #初期値は0
for h, Sh in enumerate(S):
for w in range(W):
is_road[h << shift | w] = ( Sh[w] == '.' )
assert all( (S[h][w] == '.') == is_road[h << shift | w]
for h in range(H) for w in range(W) )
TSP(巡回セールスマン問題)
$N$頂点$M$辺の有向グラフを与える。
辺$i$は頂点$U_i$から頂点$V_i$への有向辺で、距離は非負整数$W_i$である。
頂点$0$から移動を開始し、すべての頂点を1度ずつ訪問してまた頂点$0$に戻る経路のうち、最小の距離を出力せよ。
そのような経路が存在しない場合、それを報告せよ。
多くの巡回セールスマン問題の解説では、DPを次のように定義します。
DP[now][S]: 現在の頂点がnowで、これまで訪れた頂点の集合がSとなる経路の最短距離（存在しない場合はINF）
ただし、出発点(頂点0)は集合Sに含めないことにします。
DPの初期化は for now in range(1, N): DP[now][1 << now] = dist(頂点0, now)
答えは DP[終点 := 頂点0][全ての頂点] です。
TSP 実装例1
import random
random.seed(123_456)
#テストケースを作成
N = 20
INF = 10 ** 18
dist = [[0 if Ui == Vi else Wi if (Wi := random.getrandbits(30)) <= 10 ** 9 else INF
for Vi in range(N)] for Ui in range(N)]
def TSP_1(N, INF, dist):
#DP[now][S]: 現在の頂点がnow、出発点(頂点0)を含まずに通過した頂点集合がSの最短距離
DP = [[INF] * (1 << N) for _ in range(N)]
for now in range(N):
if ( Wi := dist[0][now] ) != INF:
DP[now][1 << now] = Wi
#遷移
has_bit = lambda S, i: S >> i & 1
for S in range(1, 1 << N):
visited, yet = [], []
for now in range(N):
( visited if has_bit(S, now) else yet ).append(now)
for now in visited:
if DP[now][S] == INF: continue
for nxt in yet:
T = S | 1 << nxt
if ( Wi := dist[now][nxt] ) != INF:
DP[nxt][T] = min( DP[nxt][T], DP[now][S] + Wi )
#答えを出力 到達不可能な場合、-1を返すことにする
ans = DP[0][(1 << N) - 1]
return ans if ans != INF else -1
print(TSP_1(N, INF, dist)) #3000ms
一方、筆者はDPを「出発点(頂点0)から頂点nowに至る有向パス」の最短距離として定義することを推奨します。すなわち、
DP[now][S]: 出発点(頂点0)から頂点nowに向かう有向パスで、パスに含まれる頂点集合がSとなるような経路の最短距離(なければINF)
と定義します。この場合、 出発点は常に集合に含まれる点に注意してください。
DPの初期化は DP[now := 頂点0][S := 1 << now] = 0 とします。
求めるべき値はパスの最短距離ではなくサイクルの最短距離ですが、最後に出発点(頂点0)に戻る部分は答えの計算時に反映します。具体的には、
min( DP[now][全ての頂点] + dist(now, 終点 := 頂点0) for now in range(N) )
のように、最後にdist(now, 終点)の距離を足してパスをサイクルとして完成させるイメージです。
なお、巡回セールスマン問題はDPのビットシフトによる一次元化との相性が非常に良いです。
具体的には、DP[now][S]を一次元配列DP[now << N | S]に置き換えることで、メモリ消費量を削減できます。
TSP 実装例2
import random
random.seed(123_456)
#テストケースを作成
N = 20
INF = 10 ** 18
dist = [[0 if Ui == Vi else Wi if (Wi := random.getrandbits(30)) <= 10 ** 9 else INF
for Vi in range(N)] for Ui in range(N)]
def TSP_2(N, INF, dist):
#DP[now << N | S]: 出発点から頂点nowへの有向パスに含まれる頂点集合がSの最短距離
DP = [INF] * (N << N)
DP[0 << N | 1 << 0] = 0
#遷移: DPを一次元化している部分を除いて共通
has_bit = lambda S, i: S >> i & 1
for S in range(1, 1 << N): #本問なら range(1, 1 << N, 2) でも可
visited, yet = [], []
for now in range(N):
( visited if has_bit(S, now) else yet ).append(now)
for now in visited:
if DP[now << N | S] == INF: continue
for nxt in yet:
T = S | 1 << nxt
if ( Wi := dist[now][nxt] ) != INF:
DP[nxt << N | T] = min(DP[nxt << N | T], DP[now << N | S] + Wi )
#有向パスをサイクルに作り直してから、答えを出力
ans = INF
S = (1 << N) - 1
for now in range(N):
if DP[now << N | S] != INF and dist[now][0] != INF:
ans = min( ans, DP[now << N | S] + dist[now][0] )
return ans if ans != INF else -1
print(TSP_2(N, INF, dist)) #1150ms
bit_count
Pythonのbit_countは非常に定数倍が悪く、頻繁に呼び出すとTLEになる恐れがあります。
ABCの過去問でtoamさんが紹介している通り、ビット演算による高速なpopcount関数の自作をおすすめします。
ここで、ビットごとに加算する6段階のうち、最後の3段階を積算に置き変えることでさらに定数倍の改善が可能です。
実装例は以下の通りになります。なお符号付き64bit整数の範囲に収めるため、途中でビットシフトによる調整を行っています。
#bitcount Θ(log √wordsize) = Θ(log wordsize)
def bitcount(N: int):
assert 0 <= N <= ~ (- 1 << 63)
N = ( N & 0x5555555555555555 ) + ( (N >> 1) & 0x5555555555555555 )
N = ( N & 0x3333333333333333 ) + ( (N >> 2) & 0x3333333333333333 )
N = ( N & 0x0F0F0F0F0F0F0F0F ) + ( (N >> 4) & 0x0F0F0F0F0F0F0F0F )
N = ( N + (N >> 32) ) & 0xFFFFFFFF #0 <= N < 1 << 32 ならこの行は不要
return N * 0x1010101 >> 24 & 63
bit_length
Pythonのbit_lengthも同様に定数倍が悪いので、こちらも改善しましょう。
5通りの実装例を紹介します。お好きなものをご利用ください。
なお理論上は時間・空間計算量ともに$O(1)$のアルゴリズムも存在しますが、測定上は以下の実装例の方法のほうが高速でした。
2025/08/14 更新部分
bit_lengthの実装例を2つ追加しました。
それに伴い、空間計算量ごとに速度順に並べ直しました。
空間計算量O(wordsize) De Bruijn列
空間O(wordsize)では最速です。
原理はまったく分からないのですが、Wikipedia(英語版)に方法が紹介されています。
方法の概略は次の通りです。
$2^1 -1, 2^2-1, ･･･, 2^{32}-1$にマジックナンバー$M$をかけたとき、連続する5ビットがすべて異なるような$M$を探します。
実際に全探索してみると、27ビット目から31ビット目で条件を満たす$M$が多数見つかり、順に 130329821, 130330317, 130331509, 130333493, 130337501, ･･･ となります。
この$M$をひとつ埋め込むことで、テーブルアクセスで最上位ビットを求められます。
後述のmod 67を用いる方法と比べて、除算を回避できるぶん高速に動作します。
#De Bruijn lookup 時間O(log wordsize), 空間O(wordsize)
_MSB_index_table = bytes([ 1,10, 2,11,14,22, 3,30,12,15,17,19,23,26, 4,31,
9,13,21,29,16,18,25, 8,20,28,24, 7,27, 6, 5,32])
def bitlen(N: int):
assert 0 <= N <= ~ (- 1 << 63)
if N == 0: return 0
N = N >> ( ans := (N >> 32 > 0) << 5 )
N |= N >> 1; N |= N >> 2; N |= N >> 4; N |= N >> 8; N |= N >> 16
return _MSB_index_table[N * 0x7C4ACDD >> 27 & 31] + ans
探索コード
計算量が爆発しているので注意してください。
実験上、$h \leq 26$でマジックナンバーがないことは確認してあります。(終)
def find_magic_number(start_h = 0):
for h in range(start_h, 32):
for M in range(1 << 5 + h):
C = 0
for i in range(1, 33):
N = ~ ( - 1 << i)
v = (N * M >> h & 31)
if C >> v & 1: break
C |= 1 << v
if C == 4294967295:
print(f'found. {h = }, {M = }')
#return
print(f'progress: {h = }') #進捗の目安
空間計算量O(wordsize) mod67テーブルの参照
$2$は素数$67$の原始根なので、$2^0$, $2^1$, ･･･, $2^{65}$を$67$で割った値はすべて異なります。
これを利用して、最上位ビット以下をすべて1に変えた値を$67$で割り、テーブルアクセスすれば高速にbit_lengthが求められます。
#bit_length(mod67 table lookup) 時間O(log wordsize), 空間O(wordsize)
_mod67_discrete_log = bytearray(66)
for i in range(66): _mod67_discrete_log[~(- 1 << i) % 67] = i
def bitlen(N):
assert 0 <= N <= ~ (- 1 << 63)
N |= N >> 1; N |= N >> 2; N |= N >> 4; N |= N >> 8; N |= N >> 16; N |= N >> 32
return _mod67_discrete_log[N % 67]
空間計算量O(1) bitfill + popcount
空間O(1)では最速です。
最上位ビット以下をすべて1に変え、1のビットの個数を高速bit_countで数えればbit_lengthが求まります。
#bit_length(bitfill + popcount) 時間O(log wordsize), 空間O(1)
def bitlen(N):
assert 0 <= N <= ~ (- 1 << 63)
N |= N >> 1; N |= N >> 2; N |= N >> 4; N |= N >> 8; N |= N >> 16; N |= N >> 32
N = ( N & 0x5555555555555555 ) + ( (N >> 1) & 0x5555555555555555 )
N = ( N & 0x3333333333333333 ) + ( (N >> 2) & 0x3333333333333333 )
N = ( N & 0x0F0F0F0F0F0F0F0F ) + ( (N >> 4) & 0x0F0F0F0F0F0F0F0F )
return ( (N + (N >> 32)) & 0xFFFFFFFF ) * 0x1010101 >> 24 & 63
空間計算量O(1) 二分探索
上位ビットから下位ビットに向けて二分探索し、最上位ビットの位置を探します。
実装例では最後の2ステップをマジックナンバーの参照で省略し高速化しています。
#bit_length(binary search MSB) 時間O(log wordsize), 空間O(1)
def bitlen(N):
assert 0 <= N <= ~ (- 1 << 63)
ans = 0
if N >> 32: ans |= 32; N >>= 32
if N >> 16: ans |= 16; N >>= 16
if N >> 8: ans |= 8; N >>= 8
if N >> 4: ans |= 4; N >>= 4
return ans + ( 0x4444444433332210 >> (N << 2) & 7 )
空間計算量O(1) De Bruijn列 + マジックナンバー
先述のDe Bruijn列を用いた方法ではテーブルアクセスが必要でしたが、追加の二分探索を1回行うことで、64bit整数だけでテーブルを代用できるようになります。
#De Bruijn lookup 時間O(log wordsize), 空間O(1)
def bitlen(N: int):
assert 0 <= N <= ~ (- 1 << 63)
if N == 0: return 0
N >>= ( ans := (N >> 32 > 0) << 5 )
ans |= ( sh := (N >> 16 > 0) << 4 ); N >>= sh
N |= N >> 1; N |= N >> 2; N |= N >> 4; N |= N >> 8
return ( 0x6C95B43F071D8A2E >> (N * 28883 >> 10 & 60) & 15 ) + 1 + ans
bytearray
Pythonの組み込み関数bytearrayは、$0$以上$255$以下の非負整数だけを格納できるリストのようなものです。
これだけならただの制限付きリストなのですが、メモリ効率が非常に良いのが特徴です。
通常のリストは1要素あたり数十バイトものメモリを消費しますが、bytearrayなら1要素あたりちょうど1バイトで管理できます。
これによりキャッシュ効率が上がり、定数倍の高速化が可能です。
bool値を管理したいときや、文字の種類が少ない文字列型などを受け取りときにぜひご活用ください。
visited = bytearray(N)
S = bytearray( ord(Si) for Si in input().rstrip() )
memoryview
memoryviewはbytearrayと組み合わせて、バイト列を異なる型とみなして効率的に読み書きできます。
ただし、listに比べ読み込みが約3倍、書き込みが約15倍遅く、PyPy3環境ではメモリ削減効果も乏しいため、実用性はほぼ皆無です。
キーボードのLキーが壊れてlistが打てない時の切り札としてご活用ください。
N = 10
#長さNの符号付き32bit整数として扱う場合
mv = memoryview( bytearray(N << 2) ).cast('i') #cast('i') で符号付き32bit整数
mv[0] = 1_234_567_890
mv[1] = - 1_223_334_444
print(mv[0], mv[1]) #1234567890 -1223334444
mv[0] //= 10 ** 6 #演算も可能
print(mv[0]) #1234
#長さNの符号付き64bit整数として扱う場合
mv = memoryview( bytearray(N << 3) ).cast('q') #cast('q') で符号付き64bit整数
mv[0] = 1_234_567_890_123_456_789
mv[9] = - 9_001_002_003_004_005_006
print(*[value for value in mv])
# → 1234567890123456789 0 0 0 0 0 0 0 0 -9001002003004005006
mv[1] = 2 ** 63 - 1 #符号付き64bit整数の上限値
mv[2] = - 2 ** 63 #符号付き64bit整数の下限値
mv[1] += 1 #ValueError: memoryview: invalid value for format 'q'
mv[2] -= 1 #ValueError: memoryview: invalid value for format 'q'
エラトステネスの篩
ものすごく乱暴ですが、等間隔で代入する操作はforループの代わりにスライス代入でも可能です。
リストの場合は右辺の配列確保がボトルネックとなり遅くなることがありますが、bytearrayへのスライス代入は高速化に寄与する場合が多いです。
#■最大素因数表を作成
#エラトステネスの篩のアルゴリズムで、最大素因数表を作成する
def eratosthenes_sieve_1(N: int):
assert N >= 0
E = list(range(N + 1))
for p in range(2, N + 1):
if E[p] == p:
for k in range(p, N + 1, p):
E[k] = p
return E
#E[k] = pをスライス代入化 (遅くなる)
def eratosthenes_sieve_2(N: int):
assert N >= 0
E = list(range(N + 1))
for p in range(2, N + 1):
if E[p] == p:
E[p: N + 1: p] = [p] * len(range(p, N + 1, p))
return E
#■bytearray 素数判定
#素数なら1、そうでなければ0にする
def eratosthenes_isprime_1(N: int):
assert N >= 0
E = bytearray(b'\x01' * (N + 1))
E[0] = 0
if N >= 1: E[1] = 0
for p in range(2, N + 1):
if E[p] == 1:
for k in range(p ** 2, N + 1, p):
E[k] = 0
return E
#スライス代入
def eratosthenes_isprime_2(N: int):
assert N >= 0
E = bytearray(b'\x01' * (N + 1))
E[0] = 0
if N >= 1: E[1] = 0
for p in range(2, N + 1):
if E[p] == 1:
E[p ** 2: N + 1: p] = b'\x00' * len(range(p ** 2, N + 1, p))
return E
#実行例
N = 10 ** 7
eratosthenes_sieve_1(N) #450ms, 155MiB
eratosthenes_sieve_2(N) #480ms, 290MiB
eratosthenes_isprime_1(N) #150ms, 100MiB
eratosthenes_isprime_2(N) #130ms, 110MiB
CRT(中国剰余定理)
$n ≡ n_1$ mod $M_1$と$n ≡ n_2$ mod $M_2$を同時に満たす最小の非負整数nを求めます。
存在しない場合、-1を返します。
細かい処理を組み込み関数powに投げると4行で書けます。
gcd = lambda x, y: gcd(y, x % y) if y else abs(x)
def CRT(n1, M1, n2, M2): #smallest n: n ≡ n1 (mod M1) and n ≡ n2 (mod M2)
if ((n1 := n1 % M1) - (n2 := n2 % M2)) % (G := gcd(M1, M2)) != 0: return -1
return (n1 - n2) * pow(m2 := M2 // G, -1, M1 // G) % M1 * m2 + n2
おおまかな原理
$n ≡ n_2$ mod $M_2$ より $n = n_2 + M_2 × t$ と$n$を$t$を用いて表す。
$n ≡ n_1$ mod $M_1$ に上述の$n$の式を代入し変形すると
$n_2 + M_2 × t ≡ n_1$ mod $M_1$
→ $M_2 × t ≡ (n_1 - n_2)$ mod $M_1$ ･･･ (1)
ここで$G$を$M_1$と$M_2$の最大公約数として、$m_1 = \dfrac{M_1}{G}$, $m_2 = \dfrac{M_2}{G}$ とおくと
(1) → $m_2 × t ≡ (n_1 - n_2)$ mod $m_1$ ･･･ (2)
$m_1$と$m_2$は互いに素なので、オイラーの定理より$m_2$の逆元が定義できる。これを$R$とすると
(2) → $t ≡ (n_1 - n_2) × R$ mod $m_1$ ･･･ (3)
となる。(3)を満たす最小の非負整数を選び、$n = n_2 + M_2 × t$に代入すると
n = (n1 - n2) // G * pow(M2 // G, -1, m1 := M1 // G) % m1 * M2 + n2 ･･･ (4)
のPythonの式が得られる。適切な前処理の下、$0 \leq n_2 < M_2$となることに注意すると、(4)で得る値は条件を満たす最小の$n$となる。
更に、(4)の(n1 - n2) // Gの$G$の除算を遅延させる変形を施すと
(n1 - n2) * pow(m2 := M2 // G, -1, M1 // G) % M1 * m2 + n2 ･･･ (5)
となり、実装例のコードに一致する。
$G$の除算を遅らせたぶん、$M_2$倍を$m_2 = \dfrac{M_2}{G}$倍に変更し代償した。(終)
range set query
長さ$N$の整数列$A$を与える。
以下の$Q$個のクエリに答えよ。クエリは2種類ある。
区間代入: 半開区間A[Li, Ri)の値をすべてViに変更する
区間総和: 半開区間A[Li, Ri)の総和を出力する
区間代入・区間総和の問題は遅延セグメント木を用いれば解けますが、遅延を持つ代わりにノードに直接代入することで、定数倍を大きく改善することが可能です。
遅延伝播はノードに代入した値の半分を子に伝播させればよいです。
同様に区間代入・区間最小値でもノードへの直接代入で高速化できます。
実装例として、整数範囲での区間代入・区間(総和・最小値・最大値)の遅延セグメント木を紹介します。
整数の制約がありますが非常に高速です。参考になれば幸いです。
2025/08/15 更新部分
区間代入・区間(最小/最大)値の遅延セグ木のassertに致命的な誤字があったので修正しました。
大変失礼いたしました。
区間代入・区間総和
#遅延セグ木: 区間代入・区間総和
class range_set_range_sum:
__slots__ = ('_N', '_logN', '_size', '_node')
def __init__(self, N: int):
'''
制約: 入力は整数に限ります(負の整数でもかまいません)。
速度: 要素の絶対値の和が 2 ** 61 未満であれば高速に動作します。
'''
self._N, self._logN = N, max(0, N - 1).bit_length()
self._size, self._node = 1 << self._logN, [0] * (2 << self._logN)
def build(self, A: list[int]):
'''
ノードを(長さNの)配列Aで初期化します。
'''
for i, Ai in enumerate(A, start = self._size):
assert type(Ai) == int, 'Ai must be integer'
self._node[i] = Ai << 2
for i in range(self._size - 1, 0, -1):
self._node[i] = self._node[i << 1] + self._node[i << 1 | 1]
def range_set(self, Li: int, Ri: int, value: int):
'''
半開区間[Li, Ri)の値をすべてvalueに変更します。
'''
if not 0 <= Li < Ri <= self._N: return
assert type(value) == int, 'value must be integer'
iL, iR, h = Li | self._size, Ri - 1 | self._size, self._logN + 1 #propagate
while ( h := h - 1 ):
if ( vL := self._node[jL := iL >> h] ) & 1:
self._node[jL] ^= 1; self._node[jL << 1] = self._node[jL << 1 | 1] = vL >> 1 | 1
if ( vR := self._node[jR := iR >> h] ) & 1:
self._node[jR] ^= 1; self._node[jR << 1] = self._node[jR << 1 | 1] = vR >> 1 | 1
Lt, Rt, value = Li | self._size, Ri + self._size, value << 1
while Lt < Rt:
value <<= 1
if Lt & 1: self._node[Lt] = value | 1; Lt += 1
if Rt & 1: self._node[Rt := Rt - 1] = value | 1
Lt >>= 1; Rt >>= 1
iL, iR = Li | self._size, Ri - 1 | self._size
while ( iL := iL >> 1 ):
if self._node[iL] & 1 == 0:
self._node[iL] = ( self._node[iL << 1] + self._node[iL << 1 | 1] ) >> 2 << 2
if self._node[iR := iR >> 1] & 1 == 0:
self._node[iR] = ( self._node[iR << 1] + self._node[iR << 1 | 1] ) >> 2 << 2
def range_sum(self, Li: int, Ri: int):
'''
半開区間[Li, Ri)の総和を取得します。
'''
if not 0 <= Li < Ri <= self._N: return 0
iL, iR, h = Li | self._size, Ri - 1 | self._size, self._logN + 1 #propagate
while ( h := h - 1 ):
if ( vL := self._node[jL := iL >> h] ) & 1:
self._node[jL] ^= 1; self._node[jL << 1] = self._node[jL << 1 | 1] = vL >> 1 | 1
if ( vR := self._node[jR := iR >> h] ) & 1:
self._node[jR] ^= 1; self._node[jR << 1] = self._node[jR << 1 | 1] = vR >> 1 | 1
Lt, Rt, ans = Li | self._size, Ri + self._size, 0
while Lt < Rt:
if Lt & 1: ans += self._node[Lt] >> 2; Lt += 1
if Rt & 1: ans += self._node[Rt := Rt - 1] >> 2
Lt >>= 1; Rt >>= 1
return ans
def find_right(self, v: int, Lt: int = 0, decreasing_sum_le_v: bool = False):
'''
閉区間[Lt, Rt]の総和がv以上となる最小のRtを探します。該当なしの場合、Nを返します。
制約: すべての要素が0以上であることを前提とします。
decreasing_sum_le_v = True の場合:
閉区間[Lt, Rt]の総和がv以下となる最小のRtを探します。該当なしの場合、Nを返します。
制約: すべての要素が0以下であることを前提とします。
'''
if ( Lt := max(0, Lt) ) >= self._N: return self._N
i, h = Lt | self._size, self._logN + 1
while ( h := h - 1 ):
if ( w := self._node[j := i >> h] ) & 1:
self._node[j] ^ 1; self._node[j << 1] = self._node[j << 1 | 1] = w >> 1 | 1
cnt, le_v = 0, bool( decreasing_sum_le_v )
while True:
i //= i & - i
if ( t := cnt + (self._node[i] >> 2) ) == v or le_v ^ (t > v): break
cnt = t
if i & ( i := i + 1 ) == 0: return self._N
while i < self._size:
if ( w := self._node[i] ) & 1:
self._node[i] ^= 1; self._node[i << 1] = self._node[i << 1 | 1] = w >> 1 | 1
if (t := cnt + (self._node[i << 1] >> 2)) == v or le_v ^ (t > v): i <<= 1
else: cnt, i = t, i << 1 | 1
return i ^ self._size
def find_left(self, v: int, Rt: int = 0, decreasing_sum_le_v: bool = False):
'''
閉区間[Lt, Rt]の総和がv以上となる最大のLtを探します。該当なしの場合、-1を返します。
制約: すべての要素が0以上であることを前提とします。
decreasing_sum_le_v = True の場合:
閉区間[Lt, Rt]の総和がv以下となる最大のLtを探します。該当なしの場合、-1を返します。
制約: すべての要素が0以下であることを前提とします。
'''
if ( Rt := min(self._N - 1, Rt) ) < 0: return -1
i, h = Rt | self._size, self._logN + 1
while ( h := h - 1 ):
if ( w := self._node[j := i >> h] ) & 1:
self._node[j] ^ 1; self._node[j << 1] = self._node[j << 1 | 1] = w >> 1 | 1
cnt, le_v = 0, bool( decreasing_sum_le_v )
if Rt == self._N - 1: #例外処理
if ( cnt := self._node[i] >> 2 ) != v and le_v ^ (cnt < v):
i -= 1
if self._N == 1: return -1
else: return Rt
while True:
i //= ~ i & - ~ i
if (t := cnt + (self._node[i] >> 2)) == v or le_v ^ (t > v): break
else:
cnt = t
if i & ( i := i - 1 ) == 0: return -1
while i < self._size:
if ( w := self._node[i] ) & 1:
self._node[i] ^= 1; self._node[i << 1] = self._node[i << 1 | 1] = w >> 1 | 1
if (t := cnt + (self._node[i << 1 | 1] >> 2)) == v or le_v ^ (t > v): i = i << 1 | 1
else: cnt, i = t, i << 1
return i ^ self._size
区間代入・区間最小値
#遅延セグ木: 区間代入・区間最小値
class range_set_range_min:
__slots__ = ('_N', '_logN', '_size', '_node')
def __init__(self, N: int):
'''
制約: 入力は - 2 ** 62以上 2 ** 62未満の整数に限ります。
'''
self._N, self._logN = N, max(0, N - 1).bit_length()
self._size, self._node = 1 << self._logN, [2 ** 63 - 2] * (2 << self._logN)
def build(self, A: list[int]):
'''
ノードを(長さNの)配列Aで初期化します。
'''
for i, Ai in enumerate(A, start = self._size):
assert ( type(Ai) == int and - 1 << 62 <= Ai < 1 << 62
), 'Ai must be: (1) integer, (2) - 2^62 <= Ai < 2^62'
self._node[i] = Ai << 1
for i in range(self._size - 1, 0, -1):
self._node[i] = min( self._node[i << 1], self._node[i << 1 | 1] )
def range_set(self, Li: int, Ri: int, value: int):
'''
半開区間[Li, Ri)の値をすべてvalueに変更します。
'''
if not 0 <= Li < Ri <= self._N: return
assert ( type(value) == int and - 1 << 62 <= value < 1 << 62
), 'value must be: (1) integer, (2) - 2^62 <= value < 2^62'
iL, iR, h = Li | self._size, Ri - 1 | self._size, self._logN + 1 #propagate
while ( h := h - 1 ):
if ( vL := self._node[jL := iL >> h] ) & 1:
self._node[jL] ^= 1; self._node[jL << 1] = self._node[jL << 1 | 1] = vL
if ( vR := self._node[jR := iR >> h] ) & 1:
self._node[jR] ^= 1; self._node[jR << 1] = self._node[jR << 1 | 1] = vR
Lt, Rt, value = Li | self._size, Ri + self._size, value << 1 | 1
while Lt < Rt:
if Lt & 1: self._node[Lt] = value; Lt += 1
if Rt & 1: self._node[Rt := Rt - 1] = value
Lt >>= 1; Rt >>= 1
iL, iR = Li | self._size, Ri - 1 | self._size
while ( iL := iL >> 1 ):
if self._node[iL] & 1 == 0:
self._node[iL] = min(self._node[iL << 1], self._node[iL << 1 | 1]) >> 1 << 1
if self._node[iR := iR >> 1] & 1 == 0:
self._node[iR] = min(self._node[iR << 1], self._node[iR << 1 | 1]) >> 1 << 1
def range_min(self, Li: int, Ri: int):
'''
半開区間[Li, Ri)の最小値を取得します。
0 <= Li < Ri <= N を満たさない場合、単位元: 2 ** 62 - 1 を返します。
'''
if not 0 <= Li < Ri <= self._N: return ~ (- 1 << 62)
iL, iR, h = Li | self._size, Ri - 1 | self._size, self._logN + 1 #propagate
while ( h := h - 1 ):
if ( vL := self._node[jL := iL >> h] ) & 1:
self._node[jL] ^= 1; self._node[jL << 1] = self._node[jL << 1 | 1] = vL
if ( vR := self._node[jR := iR >> h] ) & 1:
self._node[jR] ^= 1; self._node[jR << 1] = self._node[jR << 1 | 1] = vR
Lt, Rt, ans = Li | self._size, Ri + self._size, ~ (- 1 << 62)
while Lt < Rt:
if Lt & 1: ans = min(ans, self._node[Lt] >> 1); Lt += 1
if Rt & 1: ans = min(ans, self._node[Rt := Rt - 1] >> 1)
Lt >>= 1; Rt >>= 1
return ans
def find_right(self, v: int, Lt: int = 0):
'''
閉区間[Lt, Rt]の総和がv以下となる最小のRtを探します。該当なしの場合、Nを返します。
'''
if ( Lt := max(0, Lt) ) >= self._N: return self._N
i, h = Lt | self._size, self._logN + 1
while ( h := h - 1 ):
if ( w := self._node[j := i >> h] ) & 1:
self._node[j] ^ 1; self._node[j << 1] = self._node[j << 1 | 1] = w
while True:
if self._node[i := i // (i & - i)] >> 1 <= v: break
if i & ( i := i + 1 ) == 0: return self._N
while i < self._size:
if ( w := self._node[i] ) & 1:
self._node[i] ^= 1; self._node[i << 1] = self._node[i << 1 | 1] = w
i = i << 1 | ( self._node[i << 1] >> 1 > v )
return i ^ self._size
def find_left(self, v: int, Rt: int = 0):
'''
閉区間[Lt, Rt]の総和がv以下となる最大のLtを探します。該当なしの場合、-1を返します。
'''
if ( Rt := min(self._N - 1, Rt) ) < 0: return -1
i, h = Rt | self._size, self._logN + 1
while ( h := h - 1 ):
if ( w := self._node[j := i >> h] ) & 1:
self._node[j] ^ 1; self._node[j << 1] = self._node[j << 1 | 1] = w
if Rt == self._N - 1: #例外処理
if self._node[i] >> 1 > v:
i -= 1
if self._N == 1: return -1
else: return Rt
while True:
if self._node[i := i // (~ i & - ~ i)] >> 1 <= v: break
if i & ( i := i - 1 ) == 0: return -1
while i < self._size:
if ( w := self._node[i] ) & 1:
self._node[i] ^= 1; self._node[i << 1] = self._node[i << 1 | 1] = w
i = i << 1 | ( self._node[i << 1 | 1] >> 1 <= v )
return i ^ self._size
区間代入・区間最大値
#遅延セグ木: 区間代入・区間最大値
class range_set_range_max:
__slots__ = ('_N', '_logN', '_size', '_node')
def __init__(self, N: int):
'''
制約: 入力は - 2 ** 62以上 2 ** 62未満の整数に限ります。
'''
self._N, self._logN = N, max(0, N - 1).bit_length()
self._size, self._node = 1 << self._logN, [- 1 << 63] * (2 << self._logN)
def build(self, A: list[int]):
'''
ノードを(長さNの)配列Aで初期化します。
'''
for i, Ai in enumerate(A, start = self._size):
assert ( type(Ai) == int and - 1 << 62 <= Ai < 1 << 62
), 'Ai must be: (1) integer, (2) - 2^62 <= Ai < 2^62'
self._node[i] = Ai << 1
for i in range(self._size - 1, 0, -1):
self._node[i] = max( self._node[i << 1], self._node[i << 1 | 1] )
def range_set(self, Li: int, Ri: int, value: int):
'''
半開区間[Li, Ri)の値をすべてvalueに変更します。
'''
if not 0 <= Li < Ri <= self._N: return
assert ( type(value) == int and - 1 << 62 <= value < 1 << 62
), 'value must be: (1) integer, (2) - 2^62 <= value < 2^62'
iL, iR, h = Li | self._size, Ri - 1 | self._size, self._logN + 1 #propagate
while ( h := h - 1 ):
if ( vL := self._node[jL := iL >> h] ) & 1:
self._node[jL] ^= 1; self._node[jL << 1] = self._node[jL << 1 | 1] = vL
if ( vR := self._node[jR := iR >> h] ) & 1:
self._node[jR] ^= 1; self._node[jR << 1] = self._node[jR << 1 | 1] = vR
Lt, Rt, value = Li | self._size, Ri + self._size, value << 1 | 1
while Lt < Rt:
if Lt & 1: self._node[Lt] = value; Lt += 1
if Rt & 1: self._node[Rt := Rt - 1] = value
Lt >>= 1; Rt >>= 1
iL, iR = Li | self._size, Ri - 1 | self._size
while ( iL := iL >> 1 ):
if self._node[iL] & 1 == 0:
self._node[iL] = max(self._node[iL << 1], self._node[iL << 1 | 1]) >> 1 << 1
if self._node[iR := iR >> 1] & 1 == 0:
self._node[iR] = max(self._node[iR << 1], self._node[iR << 1 | 1]) >> 1 << 1
def range_max(self, Li: int, Ri: int):
'''
半開区間[Li, Ri)の最大値を取得します。
0 <= Li < Ri <= N を満たさない場合、単位元: - 2 ** 62 を返します。
'''
if not 0 <= Li < Ri <= self._N: return - 1 << 62
iL, iR, h = Li | self._size, Ri - 1 | self._size, self._logN + 1 #propagate
while ( h := h - 1 ):
if ( vL := self._node[jL := iL >> h] ) & 1:
self._node[jL] ^= 1; self._node[jL << 1] = self._node[jL << 1 | 1] = vL
if ( vR := self._node[jR := iR >> h] ) & 1:
self._node[jR] ^= 1; self._node[jR << 1] = self._node[jR << 1 | 1] = vR
Lt, Rt, ans = Li | self._size, Ri + self._size, - 1 << 62
while Lt < Rt:
if Lt & 1: ans = max(ans, self._node[Lt] >> 1); Lt += 1
if Rt & 1: ans = max(ans, self._node[Rt := Rt - 1] >> 1)
Lt >>= 1; Rt >>= 1
return ans
def find_right(self, v: int, Lt: int = 0):
'''
閉区間[Lt, Rt]の総和がv以上となる最小のRtを探します。該当なしの場合、Nを返します。
'''
if ( Lt := max(0, Lt) ) >= self._N: return self._N
i, h = Lt | self._size, self._logN + 1
while ( h := h - 1 ):
if ( w := self._node[j := i >> h] ) & 1:
self._node[j] ^ 1; self._node[j << 1] = self._node[j << 1 | 1] = w
while True:
if self._node[i := i // (i & - i)] >> 1 >= v: break
if i & ( i := i + 1 ) == 0: return self._N
while i < self._size:
if ( w := self._node[i] ) & 1:
self._node[i] ^= 1; self._node[i << 1] = self._node[i << 1 | 1] = w
i = i << 1 | ( self._node[i << 1] >> 1 < v )
return i ^ self._size
def find_left(self, v: int, Rt: int = 0):
'''
閉区間[Lt, Rt]の総和がv以上となる最大のLtを探します。該当なしの場合、-1を返します。
'''
if ( Rt := min(self._N - 1, Rt) ) < 0: return -1
i, h = Rt | self._size, self._logN + 1
while ( h := h - 1 ):
if ( w := self._node[j := i >> h] ) & 1:
self._node[j] ^ 1; self._node[j << 1] = self._node[j << 1 | 1] = w
if Rt == self._N - 1: #例外処理
if self._node[i] >> 1 < v:
i -= 1
if self._N == 1: return -1
else: return Rt
while True:
if self._node[i := i // (~ i & - ~ i)] >> 1 >= v: break
if i & ( i := i - 1 ) == 0: return -1
while i < self._size:
if ( w := self._node[i] ) & 1:
self._node[i] ^= 1; self._node[i << 1] = self._node[i << 1 | 1] = w
i = i << 1 | ( self._node[i << 1 | 1] >> 1 >= v )
return i ^ self._size
おわりに
おわりです。
ネタがふえたらまたかきたいです。