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を数え上げるらしい。思いつけないですこれは。でも詰まったらやっぱり初手選択ミスってることが多いですね。

ARC100F: Colorful Sequences

https://beta.atcoder.jp/contests/arc100/tasks/arc100_d

考えること多すぎ。

->とりまどうやって数え上げるか考える。
-->colorfulな列を考えて、そこにAが何個あるか?
-->i番目からAが始まる列がcolorfulな場合の数Fiを計算する?
-->まあ後者だろう。
->colorfulを数え上げる?not colorfulを数え上げる?
-->colorfulを数え上げるなら包除原理か。
--->でも煩雑そうだし、前M個の情報を完全に持っていないといけなさそう。
-->not colorfulは数えやすそう。
->とりまM=0の場合を考えてみる。
-->dp[i][j]:=iまで見た時前j個のelemが互いに異なる時の場合の数で行ける。
-->割とM > 0の時も応用できそう。
-->Aに同じelemがある時はdp[i][j]使ってiあたりO(1)で計算できる。
->全て違うelemの時が難しいんだろう。
-->K < M
-->全て違ったら、なんか数学的に嬉しそう。変な係数掛けてできる?
--->できないと思いました。結局コレが想定解。
-->じゃあ同じelemが出てくるまでKを伸ばしてあげれば良いのでは。
--->Kまで伸ばす
---->これはO(K^4)となり失敗。
--->本当に同じelemが出たところで切る。
---->そうするとなんか累積和が出てきてO(K^3)
---->実装大変。大学の1限まるまる使った。

SoundHound Programming Contest 2018 Masters Tournament,C: Not Too Close

https://soundhound2018-summer-final-open.contest.atcoder.jp/tasks/soundhound2018_summer_final_c

わりとすっきり解けた気がする。思考プロセス書きます。

N,D<=30
->分割統治?
->直線にしてみる?
->とりあえず緩和して最短距離がD以上のグラフの個数を数えてみる?
-->1から2への全ての経路がD以上になって見やすくなった。
-->bellman-ford的にdp?bfsっぽく距離1,2,3...の点と順番に見ていく?
--->後者っぽい。
--->dp[i][v][w]:=距離iの点まで見て、v個点が使われている。距離i-1で使われた点はw個。この時の場合の数　でできた。
--->緩和いらなくて草。
->こっからバグらせるんだよね。
-->dpにかかる係数をA,Bみたいに文字おいてごまかしたらわかりやすくなった。
-->困難は分割せよってそれ一番言われてる。

int N, D;

ll dp[41][41][41];

void solve() {
	cin >> N >> D;
	C_init(N);
	dp[0][1][1] = 1;
	rep(i, 0, D) {
		rep(v, 1, N) {
			rep(u, 1, N) {
				if(!dp[i][v][u]) continue;
				rep(w, 1, N) {
					ll A = mod_pow((mod_pow(2, u) - 1 + mod) % mod, w);
					ll B = mod_pow(2, w * (w - 1) / 2);
					ll E;
					if(i < D - 1) {
						if(N - v - 1 - w >= 0) E = C(N - (v + 1), w);
						else continue;
					}
					else if(i == D - 1) {
						if(N - v - w >= 0) E = C(N - (v + 1), w - 1);
						else continue;
					}
					else {
						if(N - v - w >= 0) E = C(N - v, w);
						else continue;
					}
					ADD(dp[i + 1][v + w][w], dp[i][v][u] * A % mod * B % mod * E % mod);
				}
			}
		}
	}
	ll res = 0;
	rep(i, 1, N + 1) {
		rep(j, 1, N) {
			ADD(res, dp[D][i][j] * mod_pow(2, j * (N - i) + (N - i) * (N - i - 1) / 2) % mod);
		}
	}
	cout << res << "\n";
}

AGC028

https://agc028.contest.atcoder.jp/

A
map使った。
B
方針ミスって式が複雑になってダメでした…。式で考察するのが苦手すぎる。
てか式で考察が進むことはあまりないんだよなぁ。
C
結構場合分けがあって難しいと思う。1発で通してる人はすごい。
D
おそらく直線にして、区間が一番左になる確率みたいなものから加法定理で解くんだろうけど、詰められる自信がない…。

数え上げの基礎能力が低すぎる。
まあ160位をとりあえず目標にしていたからオッケイかなぁ。