#二項係数 まず, 愚直な dp を考える. rep(i, sz) rep(j, sz(s) + 1) rep(l, 26) { if (s[j] - 'a' == l) add(dp[i + 1][j + 1], dp[i][j]); else add(dp[i + 1][j], dp[i][j]); } cout << dp[sz][sz(s)] << endl; rep(l, 26) をなくすと以下のようになる. r…

問題 n * m の, 0, 1 のマスが与えられる. 2 人でゲームをする. 各ターン, あるマスの行, 列で, 1 のマスがないマスを 1 にできる (隣とは限らないよ). 相手が 1 にできなくなったら勝ち. 解法 1 のマスがない行, 列の個数をそれぞれ数える. それらの小さい…

問題 を 1, ..., n の permutation として, を最大化する. 解法 で, mod をとってできるだけ小さくならないようにする, と考えない. mod をとる側で, できるだけ大きくしようとする. mod 1 で最大は 0. mod 2 で最大は 1. のように. とすれば最大値が達成で…

問題 木と, 各頂点で得るべき数が与えられる. 各頂点で得る数は, 隣り合う頂点で, すでに数を得た頂点の数にない数の最小値. どの順番で頂点が数を得るか求める. 解法 各頂点, 得るべき数と得る数を一致させる. 得るべき頂点. 数 x を得るべき頂点において, …

#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 未満に…

ソースコード https://yukicoder.me/submissions/469576 n = , y = , x = とする 何周したかは, mi = min({y, n - 1- y, x, n - 1 - x}) その分のマス数は a(k) = 2 * k + 2 * (k - 2) : 1 辺の長さが k のときの 1 周のマス数 として, a(n) + a(n - 2) + ..…

#cycle 復元 #pair #pii #ダブリング 各頂点出次数 1 より, cycle から外に矢印は出ない 連結成分ごとに考える 各連結成分に cycle は 1 つ まず, black 関係ない答え cycle のサイズの合計 それだけ求めるコード map<pii, pii> G; vector<vector<char> > table; map<pii, int> seen; pii pos </pii,></vector<char></pii,>…

#探索 ソースコード https://codeforces.com/contest/1337/submission/76924920 g に関して全探索するとする r は, g の値に近いものをいくつか二分探索で出す b は, (g + r) / 2 に近いものをいくつか二分探索で出す ただし, b が g と r の間であることが…

#組合せ ソースコード https://atcoder.jp/contests/abc127/submissions/11155856 ずっと考えて AC できた 具体例で説明する X, Y, K = 2, 3, 3 答えは 100 まず, x, y を分けて考える x = 1 が何回足されて何回引かれるか考える マス (1, 1) の x = 1 が何…

#数式変形 #二分累乗法 youtube editorial の解読 数列の, k 桁の数の数列を考える A, A + B, A + 2B A は入力の A とは別で, k 桁の数列の初項 3 項だけだとすると A + 2B はそのまま足され, A + B は 10^k されて足され, A は されて足される (実際は, k +…

問題 https://atcoder.jp/contests/abc158/tasks/abc158_e類題 zero sum ranges https://agc023.contest.atcoder.jp/tasks/agc023_a s = 3543, p = 7 を考える 右から 3, 43, 543, 3543 に対し, 7 で割った余りを持つ(0), 3, 1, 4, 1 0 を埋めた同じ余り 1 …

#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 …