#math ヒント すべて 0 の数列から, 1 ずつ足して 0, 1 の数列 a を構成する. 解法 a = 0 ... 0 から a' = 0 0 ... 0 1 0 ... 0 と, i 番目のみ 1 にすることを考える. a に対応する f(x) から, a' に対応する f'(x) を構成する. f'(x) = f(x) + . x = i の…

問題 n * m の 0 か 1 の grid が与えられる. 毎ターン, それぞれのマスが, 隣り合う同じ色のマスをもたなければそのままで, それ以外なら 0, 1 反転する. t つの query が与えられる. p ターン後, マス (i, j) の数を答える. 考察 市松模様なら, 最初の gri…

#中央値 問題 連続した区間の数をその中央値にする. ただし, 区間の長さが偶数のとき, 小さい方にする. すべての数を k にすることができるか. 本番 k より小さい数を -1, k を 0, k より大きい数を 1 にする. ランレングス圧縮する. 0 と隣り合う 1 は 0 に…

立式する. 私が i 番目の宝石を合計 x 個とるとする. i 番目の宝石は計 Si 個あるとする. X - Y は, (x = ) 宝箱ごとに, すべての宝石 i に関して 2 Si x の合計を求める. 私は, 大きい順に 1 つとばしで得る. 最後に, すべての宝石 i に関して Si^2 を引く.…

重み付き unionfind で何ができるか. 任意の 2 つの要素で, どちらがどれだけ大きいかという情報を持つことができる. 以下の問題文を参考に. http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B&lang=jp まず, 重みなし unionfind とコード…

前提知識 構造体, dfs struct UnionFind { vector<int> data; int n; UnionFind(int n) : data(n, -1), n(n) {} bool connect(int x, int y) { if ((x = root(x)) == (y = root(y))) return false; if (data[x] > data[y]) swap(x, y); data[x] += data[y]; data[</int>…

#かっこ列 #kyopro_friends さん #貪欲法 開いてる ")" が少ない文字列から左から埋めた方がいいか? 開いてる ")" というのは, 相手の "(" がいない ")" ある時点で, "(" の数より ")" の数が多くなってはダメだから それの相手の "(" が手前にいないとかっ…

#数え上げ まず, 超素朴な dp を書いてみる O(N^3) https://atcoder.jp/contests/abc167/submissions/13093316 遷移をまとめられそう O(N^2) https://atcoder.jp/contests/abc167/submissions/13094970 dp[i][j] : i 番目のブロックを見ていて, これまでの隣…

#かっこ列 stack 2 本 ソースコード https://codeforces.com/contest/1263/submission/79348572 遅延セグ木 2 本 (TLE, 速くできる?) () 1 0 0 ... となる )( -1 0 0 ... となる min をとれる遅延セグ木で, 負の数があれば -1 また, 最後が 0 出ないのもだめ…

bi が x (= bi + 1) になったとする 上に凸な曲線で, x = 1/2 で最大値をとる x ≥ 1 で減少する 貪欲に n つから一番大きな が得られる i を探すのを k 回する は減少するだけだから貪欲に大きいのをとっていい 一番大きいのを取らなかったら, 一番大きいの…

解法 同じ path 上に 2 つ A が存在することはできない 任意の実数 xi に対し, ..., 任意の実数 xj が, となるから また, ある path 上で, A になれるのは index が一番小さいのだけ ある xi が存在し, それに対して..., 任意の xj が, とはできないから ま…

.#構築 #ゲーム 問題 https://atcoder.jp/contests/abc166/tasks/abc166_f 正解 具体例で Yes にし続ける方法を考える 例 1 100 100 100 常に, 少ない方に +1 するようにすればよさそう 同じ値の場合でも, 99 未満にはならないし, どっちでもいい 99 未満に…