最大値と最小値を両方O(logN)で見たい、ワガママな人のための優先度付きキュー。要素の追加はO(logN)、要素の存在確認はO(1)。 ただし、heapqを２つ使っているので使うメモリも２倍、計算量も２倍。 import heapq class HeapBiq: def __init__(self,A=[]): s…

行列の累乗を計算する方法。 実行時間はgoogle colabのGPUなしで計測。Blocks POJ No.3734 (蟻本P182)などで使用できる。①対角化して累乗。数学的な感じ。 #input import numpy as np np.set_printoptions(precision = 0) A = np.array([[2,1,0],[2,2,2],[0,…

ABC 243 Moves on Binary Tree"L","R","U"で構成された文字列sから、RやLの後ろにあるUを1対1で消していきたい。 制約：sの文字数 n≦10**6例：LRULURLURLULULRURRLRULRRRUURRU →LRRLRRLLRR失敗例： RUとLUを、sの文字列が短くならなくなるまで消し続ける。 …