yukicoder埋め

https://yukicoder.me/problems/no/753

dp[level][bit][winner]:level段のトーナメントをbitに属す挑戦者で作る。勝者がwinnerの時の場合の数
として求めます。高速化いろいろしてAC。

https://yukicoder.me/problems/no/749

和と積のクエリが混ざっている時ってこうやれば良いんですね。解説で群論による考え方が記載されていたのであとで読みたいですね。
ai->kは0を掛けてkを足すクエリに言い換えられます。

struct segtree { // this is piece of shit. use BIT
	int n; vl sum, add, mul, fib;
	void init(int mx) {
		n = 1;
		while(n < mx) n *= 2;
		sum = vl(n * 2, 0);
		add = vl(n * 2, 0);
		mul = vl(n * 2, 1);
		fib = vl(n * 2, 0);
	}
	segtree(int mx = 0) { init(mx); }
	inline void lazy_eval(int k, int l, int r) {
		int m = (l + r) / 2;
		if(add[k] || mul[k] != 1 || fib[k]) {
			MUL(sum[k * 2 + 1], mul[k]);
			ADD(sum[k * 2 + 1], (vx[m] - vx[l] + mod) * add[k] % mod);
			ADD(sum[k * 2 + 1], (F[vx[m]] - F[vx[l]] + mod) * fib[k] % mod);
			MUL(mul[k * 2 + 1], mul[k]);
			MUL(add[k * 2 + 1], mul[k]);
			MUL(fib[k * 2 + 1], mul[k]);
			ADD(add[k * 2 + 1], add[k]);
			ADD(fib[k * 2 + 1], fib[k]);

			MUL(sum[k * 2 + 2], mul[k]);
			ADD(sum[k * 2 + 2], (vx[r] - vx[m] + mod) * add[k] % mod);
			ADD(sum[k * 2 + 2], (F[vx[r]] - F[vx[m]] + mod) * fib[k] % mod);
			MUL(mul[k * 2 + 2], mul[k]);
			MUL(add[k * 2 + 2], mul[k]);
			MUL(fib[k * 2 + 2], mul[k]);
			ADD(add[k * 2 + 2], add[k]);
			ADD(fib[k * 2 + 2], fib[k]);

			add[k] = 0;
			mul[k] = 1;
			fib[k] = 0;
		}
	}
	void addapp(int a, int b, ll s, int k, int l, int r) {
		if(b <= l || r <= a) return;
		if(a <= l && r <= b) {
			ADD(sum[k], (vx[r] - vx[l] + mod) * s % mod); //here too
			ADD(add[k], s);
		}
		else {
			lazy_eval(k, l, r);
			addapp(a, b, s, k * 2 + 1, l, (l + r) / 2);
			addapp(a, b, s, k * 2 + 2, (l + r) / 2, r);
			sum[k] = (sum[k * 2 + 1] + sum[k * 2 + 2]) % mod;
		}
	}
	void mulapp(int a, int b, ll s, int k, int l, int r) {
		if(b <= l || r <= a) return;
		if(a <= l && r <= b) {
			MUL(sum[k], s); //here too
			MUL(add[k], s);
			MUL(mul[k], s);
			MUL(fib[k], s);
		}
		else {
			lazy_eval(k, l, r);
			mulapp(a, b, s, k * 2 + 1, l, (l + r) / 2);
			mulapp(a, b, s, k * 2 + 2, (l + r) / 2, r);
			sum[k] = (sum[k * 2 + 1] + sum[k * 2 + 2]) % mod;
		}
	}
	void fibapp(int a, int b, ll s, int k, int l, int r) {
		if(b <= l || r <= a) return;
		if(a <= l && r <= b) {
			ADD(sum[k], (F[vx[r]] - F[vx[l]] + mod) * s % mod);
			ADD(fib[k], s);
		}
		else {
			lazy_eval(k, l, r);
			fibapp(a, b, s, k * 2 + 1, l, (l + r) / 2);
			fibapp(a, b, s, k * 2 + 2, (l + r) / 2, r);
			sum[k] = (sum[k * 2 + 1] + sum[k * 2 + 2]) % mod;
		}
	}
	ll ga(int a, int b, int k, int l, int r) {
		if(b <= l || r <= a) return ll();
		if(a <= l && r <= b) return sum[k];
		else {
			lazy_eval(k, l, r);
			ll lv = ga(a, b, k * 2 + 1, l, (l + r) / 2);
			ll rv = ga(a, b, k * 2 + 2, (l + r) / 2, r);
			return (lv + rv) % mod;
		}
	}
	void show() {
		vector<ll> tmp;
		rep(i, 0, n) tmp.push_back(get(i, i + 1));
		debug(tmp);
	}
	ll get(int a, int b) { return ga(a, b, 0, 0, n); } //[a, b)
	void addupdate(int a, int b, ll s) { addapp(a, b, s, 0, 0, n); } //[a, b)
	void mulupdate(int a, int b, ll s) { mulapp(a, b, s, 0, 0, n); } //[a, b)
	void fibupdate(int a, int b, ll s) { fibapp(a, b, s, 0, 0, n); } //[a, b)
};

https://yukicoder.me/problems/no/255

前の問題のsegtreeをそのまま使えます。

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 1)

https://codeforces.com/contest/1074

DEFを見ただけですが…

D
区間をsetで持っておけば奈良市計算量決められるやつ。
E
気合としか言いようがない。基本2*2の回転でできますが、最後だけ2*3の回転をいれて調整します。
F
euler tourすれば区間をたかだか3つ足して値が0の要素が何個あるか求めれば良い問題に帰着できたんですが、それがわからず。
0を直接かぞえるのではなく、最小値が何個あるか数えるようにするとうまく行きます。これは知らなかった。

Mail.Ru Cup 2018 Round 2

https://codeforces.com/contest/1055

A
ちょっと場合分けがあって面倒ですね。
B
幅1の区間しかたさないので、両脇見ればいいだけです。
C
GCD
D
良問。違う部分は共通じゃないと行けなくて（なぜかここにきづけなかった)、伸ばすだけ伸ばしてマッチしてほしいところより前でマッチすることを防ぐ。KMPの使い方を忘れていたのもあるのでコード張ります。

int N;
string A, B;
string pre, post;
string S1[MAX_N], S2[MAX_N];

vector<int> KMP(string S) {
	int n = (int)S.size();
	S += '_';
	vector<int> A(n + 1);
	A[0] = -1;
	int j = -1;
	rep(i, 0, n) {
		while (j >= 0 && S[i] != S[j]) j = A[j];
		j++;
		if(S[i + 1] == S[j]) A[i + 1] = A[j];
		else A[i + 1] = j;
	}
	return A;
}

void no() {
	cout << "NO\n"; exit(0);
}

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> S1[i];
	rep(i, 0, N) cin >> S2[i];
	rep(q, 0, N) {
		string s1 = S1[q], s2 = S2[q];
		int l = sz(s1), r = -1;
		rep(i, 0, sz(s1)) {
			if(s1[i] != s2[i]) {
				MIN(l, i); MAX(r, i);
			}
		}
		if(l != sz(s1)) {
			if(A.empty()) {
				A = s1.substr(l, r - l + 1); B = s2.substr(l, r - l + 1);
				string tmp = s1.substr(0, l); reverse(all(tmp));
				pre = tmp;
				tmp = s1.substr(r + 1);
				post = tmp;
			}
			else {
				if(A != s1.substr(l, r - l + 1)) no();
				if(B != s2.substr(l, r - l + 1)) no();
				int at = 0;
				while(l - 1 - at >= 0 && at < sz(pre) && s1[l - 1 - at] == pre[at]) at++;
				pre.resize(at);
				at = 0;
				while(r + 1 + at < sz(s1) && at < sz(post) && s2[r + 1 + at] == post[at]) at++;
				post.resize(at);
			}
		}
	}
	reverse(all(pre));
	string ans1 = pre + A + post;
	string ans2 = pre + B + post;
	vi match = KMP(ans1);
	rep(i, 0, N) {
		int at = -1;
		rep(j, 0, sz(S1[i])) {
			at++;
			while(at != -1 && ans1[at] != S1[i][j]) at = match[at];
			if(at == sz(ans1) - 1) {
				if(ans1 != S1[i].substr(j - at, sz(ans1)) 
						|| ans2 != S2[i].substr(j - at, sz(ans1))) no();
				else break;
			}
		}
	}
	cout << "YES\n";
	cout << ans1 << "\n" << ans2 << "\n";
}

E
よくあるにぶたんして0or1にするやつ。Dよりも簡単。

Educational Codeforces Round 53

http://codeforces.com/contest/1073

AB
はい。
C
にぶたん。
D
煩雑になるだろうなぁと思ったら、実は愚直な解法がO(NlogT)になっているという。良問。
何回も同じ値についてmodを取るとかなりの勢いで値が減っていくことがあんまり意識できてなかった。
E
めんどくさいけどまあまあうまく実装できたと思う。
とりまf(at, bit):=bitの集合に属する数をすでに使っているとする。あとのat+1桁を埋める際に最終的にKの条件を満たす数の個数
という関数でDPしといて他の値も求めていくみたいな感じでやりました。

int K;
ll L, R;
ll dp[20][(1 << 10)][2];
ll ep[20][(1 << 10)][2];
ll po10[20];

ll f(int at, int bit, int used) {
	if(at == -1) {
		if(__builtin_popcount(bit) <= K && used == 1) {
			return 1;
		}
		else return 0;
	}
	if(ep[at][bit][used] != -1) return ep[at][bit][used];
	ll res = 0;
	if(used) {
		for(int i = 0; i <= 9; i++) {
			ADD(res, f(at - 1, bit | (1 << i), used));
		}
	}
	else {
		for(int i = 1; i <= 9; i++) {
			ADD(res, f(at - 1, bit | (1 << i), 1));
		}
		ADD(res, f(at - 1, bit, 0));
	}
	return ep[at][bit][used] = res;
}

ll loop(int at, int bit, int used) {
	if(at == -1) return 0;
	if(dp[at][bit][used] != -1) return dp[at][bit][used];
	ll res = 0;
	if(used) {
		for(int i = 0; i <= 9; i++) {
			ADD(res, f(at - 1, bit | (1 << i), used) * po10[at] % mod * i % mod);
			ADD(res, loop(at - 1, bit | (1 << i), used));
		}
	}
	else {
		for(int i = 1; i <= 9; i++) {
			ADD(res, f(at - 1, bit | (1 << i), 1) * po10[at] % mod * i % mod);
			ADD(res, loop(at - 1, bit | (1 << i), 1));
		}
		ADD(res, loop(at - 1, bit, 0));
	}
	return dp[at][bit][used] = res;
}

ll G(ll N) { //N miman
	if(N == 0) return 0;
	vector<int> vec;
	while(N > 0) {
		vec.pb(N % 10);
		N /= 10;
	}
	reverse(all(vec));
	ll res = 0;
	int bit = 0;
	ll tmp = 0;
	rep(i, 0, sz(vec)) {
		if(i == 0) {
			ADD(res, loop(sz(vec) - i - 2, 0, 0));
			for(int j = 1; j < vec[i]; j++) {
				ADD(res, loop(sz(vec) - i - 2, bit | (1 << j), 1));
				ADD(res, f(sz(vec) - i - 2, bit | (1 << j), 1) * po10[sz(vec) - 1 - i] % mod * j % mod);
			}
		}
		else {
			for(int j = 0; j < vec[i]; j++) {
				ADD(res, loop(sz(vec) - i - 2, bit | (1 << j), 1));
				ADD(res, f(sz(vec) - i - 2, bit | (1 << j), 1) * ((tmp + po10[sz(vec) - 1 - i] * j % mod) % mod) % mod);
			}
		}
		bit |= (1 << vec[i]);
		ADD(tmp, po10[sz(vec) - 1 - i] * vec[i] % mod);
	}
	return res;
}


void solve() {
	cin >> L >> R >> K;
	memset(ep, -1, sizeof(ep));
	memset(dp, -1, sizeof(dp));
	po10[0] = 1;
	for(int i = 0; i <= 19; i++) {
		po10[i + 1] = po10[i] * 10 % mod;
	}
	cout << (G(R + 1) - G(L) + mod) % mod << "\n";
}

Codeforces Round #519 by Botan Investments

http://codeforces.com/contest/1043/problem/F

AB
うん
C
前から塊になるようにやれば。
D
SAつかって殴った。TLEめちゃくちゃギリギリ。解説は並び替えてやってますね。
E
a-bでsortすれば。
F
良問。まず数え上げに帰着して、包除原理する。このタイプ久しぶりにみて全然対処できませんでした…。

VK Cup 2018 - Round 1

http://codeforces.com/problemset/problem/923/D

A
良問。どこまで減らせるかが貪欲で求まる。
B
雪山について独立に考えれば。
C
よくあるbitのやつ。これtrieでやるのかなぁ…segtreeっぽくしちゃったけど。また使いそうなので貼っときます。

int K = 1;

struct node {
	int lat, rat, sum;
	node() {
		lat = -1, rat = -1, sum = 0;
	}
};

node seg[30 * MAX_N];

void update(int a, int v, int k, int l, int r) { //a.. at, k... segat
	// debug(a, v, k, l, r, seg[k].lat, seg[k].rat);
	if(r - l == 1) {
		seg[k].sum += v;
	}
	else {
		int m = (l + r) / 2;
		if(a < m) {
			if(seg[k].lat == -1) {
				seg[k].lat = K; K++;
			}
			update(a, v, seg[k].lat, l, m); //k
		}
		if(m <= a) {
			if(seg[k].rat == -1) {
				seg[k].rat = K; K++;
			}
			update(a, v, seg[k].rat, m, r);
		}
		seg[k].sum = seg[seg[k].lat].sum + seg[seg[k].rat].sum;
	}
}

int get_min(int a, int bat, int k, int l, int r) {
	if(bat == -1) return l;
	if(!(a & (1 << bat))) { //bat is 0. 0 is preferred
		if(seg[k].lat != -1 && seg[seg[k].lat].sum) {
			return get_min(a, bat - 1, seg[k].lat, l, (l + r) / 2);
		}
		else {
			return get_min(a, bat - 1, seg[k].rat, (l + r) / 2, r);
		}
	}
	else {
		if(seg[k].rat != -1 && seg[seg[k].rat].sum) {
			return get_min(a, bat - 1, seg[k].rat, (l + r) / 2, r);
		}
		else {
			return get_min(a, bat - 1, seg[k].lat, l, (l + r) / 2);
		}
	}
}

void seg_show(int k, int l, int r) {
	debug(k, l, r, seg[k].lat, seg[k].rat, seg[k].sum);
	if(seg[k].lat != -1) {
		seg_show(seg[k].lat, l, (l + r) / 2);
	}
	if(seg[k].rat != -1) {
		seg_show(seg[k].rat, (l + r) / 2, r);
	}
}

int N;
int A[MAX_N], B[MAX_N];

const int mv = 30;

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	rep(i, 0, N) {
		cin >> B[i];
		update(B[i], 1, 0, 0, (1 << mv));
	}
	// seg_show(0, 0, (1 << mv));
	rep(i, 0, N) {
		int t = get_min(A[i], mv - 1, 0, 0, (1 << mv));
		cout << (A[i] ^ t) << "\n";
		// debug(A[i], t);
		update(t, -1, 0, 0, (1 << mv));
	}
}

D
B->Cとできるし、Bの偶数個だけ数えれば良いやんと思ったらいろいろ考えてないケースがたくさんあって場合分け地獄にハマった…
煩雑になったら、何で場合分けするかちゃんと考えなおしたほうがいいですね。

New Year Contest 2015

https://snuke21.contest.atcoder.jp/tasks/snuke21_e

懐かしの。ムズイ。

->初手でいけそうなのが、強連結の条件を考えてみるだけだった。
->強連結成分がL個以上ならまあまあできそう。これが求まればあと引き算するだけ。
-->N!Σ(n+m+...=N)(2^(n(n-1)/2) / n!)(2^m(m-1)/2 / m!)....を求めればいいところまで行けた。
-->しかしこれがムズい。O(N^3)くらいしか思いつかない。どうあがいても無理。
-->緩和したらいけるのではとか思ってみたけど無理。
-->やることなくなって諦めた。
->解説みると、ある条件を満たすnone empty subset Sを数え上げるらしい。思いつけないですこれは。でも詰まったらやっぱり初手選択ミスってることが多いですね。