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の文字列が短くならなくなるまで消し続ける。 …