頂点１を根として、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…

NOMURA プログラミングコンテスト 2020 A,B,C の3完 ABC170 A,B,C,D の4完でした。 土曜日の方はまずまず。C は直ぐセグ木じゃん楽勝と思った割に、実装をバグらせまくり時間をロスしすぎました。いもす法は知らなかったので、セグ木で毎回リスト A をみて 1…

タイトルからして dp だと思ったら解説は全探索だった。本質的には dp もメモ化全探索みたいなところあるけど。 w_i の制約が特徴的で max(w_i) - w_1 dp[ i ][ j ][ k ] で i 番目の荷物まで見たときに、j 個の荷物を入れて、 重さが j * w_1 + k となって…

k = 0 から順番に (A[k*2],B[k*2]), (A[k*2+1],B[k*2+1]) を (A[k*2]+B[k*2])*A[k*2+1]+B[k*2+1] と計算していく問題。 セグ木を使うと、(A[k*2]*A[k*2+1], B[k*2]*A[k*2+1]+B[k*2+1]) の結果を (A[k], B[k])に保存できるので、求める答えは sum(A[1]+B[1]) …

b より大きく、a 以下の数字の積の約数の数の個数を求めればいいのだけれど、b,a が大きすぎてそのまま掛け算をするとオーバーフローする。 なので一つずつ素因数分解して、個数分だけ素数をリストに入れていって、あとで collections.Counter で数えた。 a,…

最大マッチング問題というらしい。 解説を読んだら理解はしたけど 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, …

二分探索２つめ。 答えを n と仮定したときに n が条件を満たすかどうかは (a, b) = (x, 1)*k + (1, y) * (n - k) とおいたときに、R >= a かつ B >= b を満たす 0以上 n以下の整数 k が存在することと同値である。 （厳密にはさらに n これを正負に注意して…

https://qiita.com/saba/items/affc94740aff117d2ca9コードはこれを参考にしましたこれもとりあえず辺のリストを作成 ループがあることをどう表現するかがポイント 一周したというのを、「一回見た頂点に戻ってきた」と置き換えると memo = [True]*n で一回…