2018-11-14

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

Segment Tree

DEFを見ただけですが…

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

2018-11-14

Mail.Ru Cup 2018 Round 2

String

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よりも簡単。

2018-10-30

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";
}

2018-10-30

Codeforces Round #519 by Botan Investments

DP Suffix Array Combination Inclusion and Exclusion

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

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

2018-10-28

VK Cup 2018 - Round 1

Segment Tree Adhoc

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

2018-10-17

New Year Contest 2015

DP Math

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

2018-10-16

ARC100F: Colorful Sequences

DP Combination

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限まるまる使った。