数列から等差数列を引いていって [0]*n にできるかを答える問題 n = 5 の場合、引く候補は [1,2,3,4,5], [2,3,4,5,1], [3,4,5,1,2], [4,5,1,2,3], [5,1,2,3,4] の 5 つあるが、 どれも総和は 15 であり、引ける回数 k は sum(a) // 15 になる 引いた後の遷移…

気づくこと 一回でも x を操作する途中で２倍した後は、二回連続で +1, -1 を使わない。 理由 p 回 +1 した後に、２倍して q 回 +1 すると、 (x + p)*2 + q = 2x + 2*p + q q ≧ 2 のとき 2x + 2*p + q = 2x + 2*p + 2*s + t(s ≧１, t は 0 or 1) となり p + …

ほぼこれ。abc 137 E - Coins Respawn (python) - aacord’s memo 頂点１からNまでに通りうる経路だけ抜き出して、その中で bellman-ford を使う。更新回数が m 回をこえたら inf を出力する。 from collections import deque def belman(s,n,w,es): d = [-fl…

サンプルを使ってワーシャルフロイドした結果が、サンプルと一致していなければ答えは -1 となる。 そうでない場合は存在する道の和を出力しないといけないが、それは i から j に道が引かれているとき == min( d[ i ][ k ] + d[ k ][ j ] ) > d[ i ][ j ] …

久しぶりに拡張ダイクストラの問題 day2 にも拡張ダイクストラが出ていたりする。 ダイクストラといっても、距離は一切出てこなくて、休憩回数の最小値を求める問題。 heap で (累計の休憩回数、前の隙間、今いる頂点）を保管して、今いる頂点から次の頂点に…

一つでもpath上に黒がある個数を、総数ーpath上がすべて白く塗る個数と置き換えて包除原理を使う。 m 個の path の中から i 個を選ぶ方法は itertools.combinations を使い、1つの path が通る辺の集合を辺１つずつに番号を座圧の要領でつけていき、2進数表…

結局注目する点は、隣り合う2数を足したときに、繰り上がって桁数が変化しない時は、全体の数の和が9減るということのみ。桁数が減る時は繰り上がりがないため、全体の和は変化しない。 なので求める回数は、全体の和を S, 桁数を T とすると、T-1 + (S-1)//…

stack, dict, set 全部使った。盛りだくさん。 まず、降順ソートしてｋ個選んだ時に、L 種類の寿司が含まれているとき、当然それはL 種類の寿司を選ぶ美味しさの中での最大値となる。同様にして、k > L なら種類が被っている寿司を食べているので、k =L にな…

始点ソートして、L ≦ i ≦ R でd[ i ] = min( d[ i ], d[ L ] + c ) で更新していけば終わり。 答えは d[ n-1 ] で、d[ n-1 ] = INF なら -1 を出力する d[ i ] の一点取得、L ≦ i ≦ R の区間更新なのでセグ木を使えば簡単。 import sys read = sys.stdin.buf…

dp の巻き戻しするやつ。dfs をして頂点を探索する際に、stack (deque) に次の頂点を入れる前に、dp を変更する前の要素を入れておくことで、dfs順に頂点を探索するときに、行き止まりについてから、一つ前の頂点に戻る時にその時点での dp を再現することが…

172 4完 パフォ1421 173 4完 パフォ1319 まあ失敗ではないけど大成功でもない感じ。次で水色なりたいね。 172は包除原理の一般法則を知らなかったのが原因。Fは難しかった。 #172 E import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.re…

頂点１を根として、dfs をしていき、それまでの xor 和を defaultdict (D) で管理して、現在のxor和 = X^a を満たす a が今までの xor和に含まれていればいいので、dfs 順に D [ 現在のxor和^X ] を足していけばいい。根からの xor和がちょうど X になるとき…

これの下位互換。 F - Absolute Minima abc 127 F - Absolute Minima (python) - aacord’s memo import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline class Bit: def __init__(self, n): self.size = n self.tree = [0] * (n + 1…

BIT木。初見で解いているときは BIT木を知らなくて TLE を出し続け、諦めて解説読んでナニコレとなった。 BIT木の使いどころは、BIT木を2本持つことで、小さい方から i 番目の値の探索を log(N) を行える点である。値の追加、探索、削除を log(N) でできるの…

bit dp の問題。ゴールした順に bit を作っていくとうまく dp が作れる。 例えば 1 よりも 2 が早くゴールしているときは、今ゴール済みの人を s で表すと、 s & 1 == 0であれば、まだ１がゴールしていないので s から s | 1 n,m = map(int,input().split())…

セグ木の練習。木というているけど、使いどころはグラフ問題ではなく、ソートされた数列で、特定の区間の最小値や公約数を求めたり、特定の区間の値を変更するときに使う。 愚直にやると N^2かかるが、heap を使おうとすると頭が痛くなるときに便利。 今回の…

M回握手をして出来る幸福度の最大値を、１回の握手で幸福度がｘ以上上がるような握手の回数がM回出来るｘの最大値を求める問題と考えれば、二分探索でｘを求めて、左手 i を固定したときにｘ以上の握手ができる手の数は、 a を昇順ソートしておけば k = n - …

Eまで5完。Fが形式的冪級数だと気づきさえすれば６完できたのに。 Bは０が後ろにあるケースがサンプルにあったからすぐ修正できた。sort したら前から10**18 を超えたら -1 を出力するようにプログラミングしてよい。python は10**18の計算をしてもエラー吐…

経過時間*P 枚コインを失い、辺を通るのに１分かかり、辺上でC枚のコインを得るので、 辺を通ったときにかかるコスト（-コインの数）を －C＋P 枚とすれば、最短路問題に帰着できる。今回は負の辺があるのでベルマンフォード法を使う。 面倒なのは、頂点１か…

自力AC。差の絶対値の総和を求める。 こういうときは | n - m | = max(n,m) - min(n,m) なので、a より小さいものの数、大きいものの数を x 座標と y 座標で別々に求めたらよい。これの一次元版を解いたことある気がする。 1 そして X座標が x となる頂点の…

XOR の知識 1．a^a = 0, a^b^a = a^a^b = b（交換法則） 2．n%4 = 1 のとき 1^2^...^n = 1, n%4 = 3 のとき 1^2^...^n = 0 (ABC121 D)2. から 1^2^...^2**m-1 = 0 となり、1. から k 1^2^,...,^k-1^k+1^,...,^2**m-1 = k となる。 考察はできたが実装が手こ…

XOR っぽいけど本質はそこじゃない感じの問題。 本質は s = 0011100... と並んでいたら、s[0 : ], s[2 : ], s[5 : ] で操作する回数が異なっている必要があるということ。 なので s[2], s[5] で区切る必要があり、これを満たす最大の長さは min( max(2,len(s…

女子の選びだけ itertool で nCp 通り全列挙して男子の選び方を貪欲に選んでいく。 collection.Counter で most_common(q) とかして選んでいたら TLE したので普通にリストに入れていって上から q 番目まで取ったらいけた。 import sys input = sys.stdin.re…

３完。負け。いつも愚直に全探索するだけの問題を難しく考えすぎてそこで詰まる。 全探索するかとは一回は思うのだけど、今いち全探索しても間に合う制約なのかどうかが全く分からず結局他の方法を考える→時間切れみたいになっている。 Dも最初から因数分解…

サンプル２が結構ヒントになった。 まず m が最大値の時に条件を満たせばいいとわかる。 そして、初めの割り当ての２数 ( a, b ) の差(a 一周すると (1,b+n-a+1) となるから、 n = 奇数のときは一周すると偶奇が変わる、n = 偶数のときは偶奇が変わらないと…

青diff 初の自力AC 解説はX = (ak/2) ∗ (2p + 1) を X が 2 で割り切れる回数と ak/2 が 2 で割り切れる回数が同じ と言い換えててあたま良すぎかとなった a のなかにひとつでも ( aj / ai )% 2 == 0 となるものがあれば答えが 0 になって、そうでないなら答…

最大マッチング問題というらしい。 解説を読んだら理解はしたけど n= (a*b)**0.5 d = int(n) if n.is_integer(): d -= 1 ans = d*2-1 と c= int((a*b-1)**0.5) chk = 2*c-1 が同じものになると思っていたので、間違え続けた。（例えば、(a, b) = 134576397, …

ワーシャルフロイド法を二回使うらしい。思いつけるのか？ 解説読んで5分くらい考えて解説が正しいことを理解した。 python だと from scipy.sparse import csr_matrix from scipy.sparse.csgraph import floyd_warshall で簡単にワーシャルフロイド法ができ…

拡張ダイクストラで解く。総時間、頂点に加えて今持っている銀貨の数を追加して heap に入れる。時間を増やす要因が通過時間と通貨を交換する時間の二つ（疲れているのでダジャレみたいになっている）あるので、交換するか、移動するかで分けて考える。移動…

二分探索で最小値を探すやつ。蟻本３－１－３ 二分探索は値の探索をするだけなので、最小回数で動作終わるようにするための必要十分な動作方法を、主に貪欲法で見つけてくる方に難易度が関わってくる。 今回は左端 ( X0 ) から順に arg回で、それより左側の…