ABC298から突如はじまったAtCoderへのDDos攻撃... ABC300は対策できたようでちょっと安心していたがABC301はダメそう。。 提出はできるけどコードテストが重すぎて動かないよ！ AtCoder tools とか使っている人はいいのかもだけど…。 クラッカーのくせにプロ…

atcoder.jp グラフが与えられて、最も離れている点同士を求めるような問題の場合、 「どこでもいいのでテキトウな点から一回BFSして、最も距離遠い点Aを見つけ、点Aから再度BFSをして最も遠い点Bを見つける」 という二重BFSをやると、最も離れている点のペア…

AHC 019 Silhouette Block Puzzle Creation 2023/3/18-4/2 概要 ブロック積み木をデザインしたい。指定した2セットの影の形を作れるような積み木セットを提案してください。子ども用なので、少数の大きいブロックだけで、無駄なブロックがでないように作って…

AHC 018 2/18(土)-2/26(日) 【概要】 水源がいくつかと、家がいくつかある200x200の土地がある。 水路を掘って、全ての家を水源と接続したい。 ただし、地面には隠しステータスとして「硬さ」があって、掘る時にそれに相応する「体力」を必要とする。 消費す…

AHC017 1/28(土)-2/5(日) 概要： N個の地点とそれぞれの地点を結ぶM本の道路があり、それをD日間ですべて1回（1日）ずつ工事したい。工事できるマンパワーは1日あたり道路K本まで。 工事中の道路は通れないので、各地点にいる人たちは別の地点に行くために迂…

最大値と最小値を両方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の文字列が短くならなくなるまで消し続ける。 …

3次元の入れ子を作りたいときに参照渡しにならないようにつくる方法。dp[i][j][k] 1≦i≦x 1≦j≦y 1≦k≦z として、 dp = [[[0]*(z+1) for _ in range(y+1)] for __ in range(x+1)] ABC281 D - Max Multiple などで使用。

・x**yを使わないといけないのに、yの制約が「0≦y≦10**9」とかのとき。①"aのn乗"の計算 def reppow(a,n): if n == 0: return 1 if n == 1: return a if n%2 == 1: ret = reppow(a,n-1)*a return ret ret = reppow(a,n//2) ret = ret*ret return ret このまま…

最小全域木問題に対してのプリム法による解法 AOJ ALDS1_12_A Minimum Spanning Tree・まずスタートの点を決める ・「既に到達した点」から「まだ到達していない点」へ行く辺の中で一番コストの低い辺を探す ・その辺を採用し、辺の先の点は「既に到達した点…

最小全域木問題に対してのクラスカル法による解法 AOJ GRL 2_A Minimum Spanning Tree・重みを持つすべての辺をコスト順に並び替える ・コストの低い辺から順に採用するか検討していく ・その辺を採用すると「閉路」ができてしまうなら採用しない ・「閉路」…

unionfindのお約束部分 #n = int(input()) par = [-1]*n siz = [1]*n def root(x): if par[x] == -1: return x else: par[x] = root(par[x]) return par[x] def size(x): return siz[root(x)] def unite(x,y): x = root(x) y = root(y) if x == y: return Fa…

エラトステネスのふるい・任意のn以下の素数のリストをO(nloglogn)（らしい）で得る。 def prime(x): x = int(x) if x < 2: return [] P = [True]*(x+1) P[0],P[1] = False,False res = [] for i in range(x+1): if P[i] == False: continue else: res.appen…