#seg tree #BIT #pbds問題 n 点と, その位置, 速度が与えられる. すべての点の組み合わせで, その最小距離の合計を答える. ある時刻の, 距離の合計の最小値を答えるのではないことに注意.2 つの点が出会わないのであれば, 最初の距離の差 出会うなら, 0 ダブ…

#tree 一番浅い leaf とは, 5 のこと (root を除く) 上の図で, leaf で, 一番浅いのから上に上げる理由は, もともと chain で, 下の方が詰まりやすいから 一番右の図で, 4 を上げたら 2 の子が 3 つになる 親の親に移動するのではない 深さが 2 小さい頂点に…

#dp #cht #convex hull trick問題 http://poj.org/problem?id=3709 O(N^3) a[j + 1] ~ a[i] を a[j] と同じにする #include<bits/stdc++.h> using namespace std; typedef long long ll; #define F first #define S second #define pii pair<int, int> #define eb emplace_back #defin</int,></bits/stdc++.h>…

#全方位木dpコード https://atcoder.jp/contests/dp/submissions/10244725まず, 頂点 0 を根とした木の答えを求める. void dfs(int v, int p) { ll ret = 1; for (edge& e : G[v]) { if (e.to == p) continue; dfs(e.to, v); (ret *= dp[e.to] + 1) %= m; } …

真に増加していく部分列 (連続でなくてよい) で, 最長のものを求める数列 5 3 4 1 2 を考える (lis は 3, 4 とか 1, 2)vector を用意する最初に, 5 を入れる次, 3 がきて, 3 より大きいのを vector で探すと, 5 がある 5 を 3 に変える 5 の後に 3 がくる li…

#貪欲 #dfssample2, 問題文の図で考える. を 1 ~ n で, 異なるものにできることを言う. まず, 親が 0 の 0 番が 根 (root) = 1 = 2 とすれば, その子孫には自分より小さいのが 1 つで 1, あとは 3, 4, 50 の子の 1 に行く = 3 2 は 0 で使ったから使えず, 1,…

#math問題 https://codeforces.com/contest/1300/problem/Cコード https://codeforces.com/contest/1300/submission/70657047 演算 x | y - yx | y で x に y の 1 のとこを 1 にし, -y で y が 1 のとこを 0 にするx | y で y で 1 の bit はすべて 1 にな…

#math要素は sort してるものとするグループを2つに分ける 1 : 2k + 1 人がいて, 中央値は 2 : 2l + 1 人がいて, 中央値は i を示す i の上に k 人いる また, i k + l + 1 = n (2k + 1 + 2l + 1 = 2n k + l = n - 1) i の上に n 人はいる ゆえに, を示す j …