CODE FESTIVAL 2016 Final,F: Road of the King

https://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_f

これは簡単だった。

どんなグラフになるかというと、連結成分を潰して1つの頂点と見れば直線になっています。
なので、dp[i][j][k]:=(i回目でまだとっていない点の数がj個、1を含む連結成分の大きさがkとした時の場合の数)とすればできます。

int N, M;
ll dp[2][310][310];

void solve() {
	cin >> N >> M;
	dp[0][N - 1][1] = 1;
	
	int now = 0, nex = 1;
	rep(i, 0, M) {
		memset(dp[nex], 0, sizeof(dp[nex]));
		rep(j, 0, N + 1) {
			rep(k, 0, N + 1) {
				if(!dp[now][j][k]) continue;
				if(j != 0) ADD(dp[nex][j - 1][k], dp[now][j][k] * j % mod);
				if(N - j - k > 0) ADD(dp[nex][j][k], dp[now][j][k] * (N - j - k) % mod);
				ADD(dp[nex][j][N - j], dp[now][j][k] * k % mod);
			}
		}
		swap(now, nex);
	}
	cout << dp[now][0][N] << "\n";;
}

AGC007C: Pushing Balls

https://agc007.contest.atcoder.jp/assignments

期待値ってこんなこともできるのか…

まずf(d1,d2,....d2n)を距離の間隔がそれぞれd1...d2nの時の期待値と定義します。
簡単な例でf(1,2,3,4,5,6)を取り上げます。
1手進めてみましょう。すると
f(1,2,3,4,5,6)=(1+2+3+4+5+6)/6+1/6{f(3,4,5,6)+f(6,4,5,6)+f(1,9,5,6)+f(1,2,12,6)+f(1,2,3,15)+f(1,2,3,4)}
となります。ここで{}内について考えてみます。
f(a,b,c,d)=E1(a)+E2(b)+E3(c)+E4(d)となります。ここでEk(x)はk番目長さxの区間のみに注目した時の期待値とします。
さらにEk(x)=x*Ek(1)となります。なのでf(3,4,5,6)=3*E1(1)+4*E2(1)+5*E3(1)+6*E4(1)です。
なので{}内=13E1+23E2+33E3+43E4=13(E1+23/13E2+33/13E3+43/13E4)=13*f(1,23/13,33/13,43/13)となります。
あとはこれを繰り返すだけでO(N)で求められます。

同じような状態を平均化している感じですね。加法定理が使えるとこういうこともできるなんて勉強になりました。

あとlong doubleにしても誤差が10^-9以下にならずに辛いなぁと思ってましたが、相対誤差が10^-9でいいのでdoubleでもいいです。

int N;
long double d, x;

long double loop(int n, long double D, long double X) {
	if(n == 0) return 0.0;
	long double nD = (2 * n + 2.0) * D + 5.0 * X;
	long double nX = (2 * n + 4.0) * X;
	long double s = (2.0 * n * D + (2.0 * n - 1.0) * n * X) / (2.0 * n);
	return s + nD / (2.0 * n) * loop(n - 1, 1.0, nX / nD);
}

void solve() {
	cin >> N >> d >> x;
	cout << loop(N, d, x) << "\n";
}

CODE FESTIVAL 2016 Final,E: Cookies

https://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_e

まずクッキーを食べる回数Tを固定します。これは40くらいまでやればいいです。

クッキーを食べるまでA+si秒待ったとすると、
クッキーの総和はΠ(1<=i<=T+1)si、かかった時間はΣ(1<=i<=T+1)si+ATと表されます。
Σsiを固定してΠsiを最大化するとき、siはなるべくまんべんなくするのが良いです。これはlogとって凸方程式とかでわかります。
なのでsiの要素がすべてaと等しいとして、Πsi=a^(T+1)<=Nを満たす最大のaを求めます。
それからsiの値を１つづつincrementして、初めてΠsiがN以上になった時が答えです。

siをT+1まで定義するのがポイントです。僕はここをTまでしか定義しなくて、
AT+Σsi+ceil(N/Πsi)を最小化しようという問題を考えて、だいたいグラフが凸になる(と思われる)から3分探索したんですが落ちました。
やっぱり実験で立てた予想にすがりすぎるとダメですね。

追記
グラフは確かに凸になるんですが、同じ値が生じすぎて谷にうまく落ちていきません。なので二分探索二回するとかで対応する必要がありますね。
まあ三分探索学べたので良しとしましょう。

ll pow(ll a, ll n) {
	if(n == 0) return 1;
	ll res = pow(a, n / 2);
	if(n % 2 == 0) return res * res;
	else return a * res * res;
}

ll root(ll a, ll n) {
	if(n == 1) return a;
	else if(n == 2) {
		ll lv = -1, rv = 10000000;
		while(rv - lv > 1) {
			ll m = (lv + rv) / 2;
			if(pow(m, n) <= a) lv = m;
			else rv = m;
		}
		return lv;
	}
	else {
		ll m = 1;
		while(pow(m + 1, n) <= a) m++;
		return m;
	}
}

ll N, A;

void solve() {
	cin >> N >> A;
	ll ans = N;
	rep(T, 1, 40 + 1) {
		ll s = root(N, T + 1);
		ll sum = s * (T + 1);
		ll mul = pow(s, T + 1);
		// debug(T, sum, mul);
		rep(i, 0, T + 2) {
			if(mul >= N) {
				MIN(ans, A * T + sum);
				break;
			}
			mul /= s;
			mul *= (s + 1);
			sum++;
		}
	}
	cout << ans << "\n";
}

CODE FESTIVAL 2016 Elimination Tournament Round 1,B: 数字列をカンマで分ける問題

https://beta.atcoder.jp/contests/cf16-tournament-round1-open/tasks

にぶたんします。

結局任意のi,jに対してS[i...i+M]とS[j...j+M]が高速に比較できればいいんですが、これはsuffix arrayでできます。

suffix array知っていれば一瞬の問題なのかぁ。

部分列の比較ならsuffix arrayと思えば良さそう。

int N, K, M;
vector<int> S;
int ran[MAX_N];
vector<int> ord;
SA sa;

bool ok(int m) {
	int pat = ord[m];
	int cnt = 1;
	int at = 0;
	while(N - at >= M) {
		if(ran[at] <= ran[pat]) {
			at += M;
		}
		else {
			if(M == 1) return false;
			at += M - 1;
		}
		if(at == N) break;
		cnt++;
	}
	return cnt <= K + 1;
}

void solve() {
	cin >> K;
	string str; cin >> str;
	N = sz(str);
	S.resize(N);

	rep(i, 0, N) S[i] = str[i] - '0';
	sa.init(S, 10);

	M = (N + (K + 1) - 1) / (K + 1);

	rep(i, 1, N) {
		int a = sa.sa[i], b = sa.sa[i + 1];
		if(sa.lcp[i] >= M) ran[b] = ran[a];
		else ran[b] = ran[a] + 1;
	}
	rep(i, 1, N + 1) {
		if(sa.sa[i] < N - M + 1) ord.pb(sa.sa[i]);
	}
	int lv = -1, uv = N - M;
	while(uv - lv > 1) {
		int m = (lv + uv) / 2;
		if(ok(m)) uv = m;
		else lv = m;
	}
	string ans;
	int at = ord[uv];
	rep(i, 0, M) ans += S[at + i] + '0';
	cout << ans << "\n";
}

ARC012D: Colorful Balls

https://beta.atcoder.jp/contests/agc012/tasks/agc012_d

最初の提出で3ケースだけWAだったのでオーバーフローとかどうでもいいミスでしょと思いましたが違いました…
同じ色内だったら1番小さいやつから辺を張ればいいです。
でも違う色だったら色の中で一番小さいやつのうち一番小さいの+二番目に小さいのから辺を張る必要があります。
二番目も張らないといけないの、当たり前だけど気づかなかった…
さらに実装も一部ミスがあり、どっちもミスった結果大体のケースで正答を出すようなプログラムを書いてしまいました。

int N; ll X, Y;

vector<pl> group[MAX_N];
pl mel[MAX_N];
ll C[MAX_N], W[MAX_N];

vector<int> con[MAX_N];
int cnt[MAX_N];

void solve() {
	cin >> N >> X >> Y;
	C_init(N);
	rep(i, 0, N) {
		cin >> C[i] >> W[i]; C[i]--;
		group[C[i]].pb(pl(i, W[i]));
	}
	UF uf(N);
	fill(mel, mel + N, pl(linf, linf));
	rep(i, 0, N) {
		vector<pl>& g = group[i];
		int at = -1;
		ll w = linf;
		rep(i, 0, sz(g)) {
			pl p = g[i];
			if(w > p.sec) {
				w = p.sec;
				at = p.fst;
			}
		}
		mel[i] = pl(w, at);
		rep(i, 0, sz(g)) {
			pl p = g[i];
			if(p.sec + w <= X) uf.unite(at, p.fst);
		}
	}
	sort(mel, mel + N);

	rep(i, 0, min(2, N)) {
		int at = mel[i].sec;
		ll w = mel[i].fst;
		rep(j, 0, N) {
			if(C[at] != C[j] && w + W[j] <= Y) uf.unite(j, at);
		}
	}

	rep(i, 0, N) con[uf.find(i)].pb(i);

	ll ans = 1;
	int at = uf.find(mel[0].sec);
	vi& vec = con[at];
	rep(i, 0, sz(vec)) cnt[C[vec[i]]]++;
	ans = fac[sz(vec)];
	rep(i, 0, N) MUL(ans, fiv[cnt[i]]);
	cout << ans << "\n";
}

AGC010D: Decrementing

https://beta.atcoder.jp/contests/agc010/tasks/agc010_d

やっぱこういうのは偶奇ですね…。

操作を良く観察すると、奇数で割っても偶奇が変わらないことに気づきます。

なので列に奇数が2つ以上ある場合、または奇数が1つでもそれが1の場合、結局1ずつdecrementしていく作業と同じなので勝敗がわかります。

奇数が1つの場合はもう少し複雑で、どれか１つを偶数→奇数にして勝てるならそうして、それでも勝てなかったら奇数をdecrementしてA全体を最大公約数で割ります。この時2の階乗のみで割ると不十分なことに注意してください。
N=3,A={7,12,12}の時とか、7をdecrementして6ではなく2で割って、{3, 6, 6}にして考えると違う結果が出ます。それでWA出した。

ll gcd(ll a, ll b) {
	if(b == 0) return a;
	else return gcd(b, a % b);
}

int N;
ll A[MAX_N];

bool sub_solve() {
	if(N == 1) return (A[0] - 1) % 2;
	bool second = false;
	while(true) {
		// debug(vi(A, A + N));
		int odd = 0;
		bool one = false;
		rep(i, 0, N) {
			if(A[i] % 2) odd++;
			if(A[i] == 1) one = true;
		}
		if((N - odd) % 2) return (second ^ 1);
		else if(odd != 1 || one) return second;
		else {
			if(A[0] % 2) A[0]--;
			ll g = A[0];
			rep(i, 0, N) {
				if(A[i] % 2) A[i]--;
				g = gcd(g, A[i]);
			}
			rep(i, 0, N) A[i] /= g;
		}
		second ^= 1;
	}
}

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	if(sub_solve()) {
		cout << "First\n";
	}
	else cout << "Second\n";
}

AGC002D: Stamp Rally

https://agc002.contest.atcoder.jp/tasks/agc002_d

永続unionfindかぁと思ってたけど、想定解は並列二分探索というものらしいです。

同じような二分探索を大量にしないと行けない時に、まとめてやる感じです。

辺の数と点の数をswapしていて無限にバグらせた…

struct query {
	int a, b, c;
};

int N, M, Q, E;
query T[MAX_N];
int ans[MAX_N];

struct edge { int u, v, cost; };
edge es[MAX_N];

vector<pi> iv[40];
vector<vi> iq[40];

void sub_solve() {
	
	iv[0].resize(1);
	iv[0][0] = pi(-1, M - 1);
	iq[0].resize(1);
	iq[0][0].resize(Q);
	rep(i, 0, Q) iq[0][0][i] = i;

	int at = 0;
	while(true) {
		// debug(iv[at]);
		// debug(iq[at]);
		int n = sz(iv[at]);
		int iqat = 0;
		vector<pi> quexe;

		rep(i, 0, n) {
			if(iv[at][i].sec - iv[at][i].fst == 1) {
				rep(j, 0, sz(iq[at][i])) {
					ans[iq[at][i][j]] = iv[at][i].sec;
				}
			}
			else quexe.pb(pi((iv[at][i].fst + iv[at][i].sec) / 2, i));
		}
		// debug(quexe);
		if(sz(quexe) == 0) return;
		iv[at + 1].resize(sz(quexe) * 2);
		iq[at + 1].resize(sz(quexe) * 2);

		UF uf(N);
		rep(i, 0, M) {
			edge e = es[i];
			if(!uf.same(e.u, e.v)) {
				uf.unite(e.u, e.v);
			}
			if(iqat < sz(quexe) && quexe[iqat].fst == i) {

				pi p = quexe[iqat];
				vector<int>& vec = iq[at][p.sec];

				int l = iqat * 2, r = iqat * 2 + 1;
				iv[at + 1][l] = pi(iv[at][p.sec].fst, p.fst);
				iv[at + 1][r] = pi(p.fst, iv[at][p.sec].sec);

				rep(i, 0, sz(vec)) {
					query t = T[vec[i]];
					int tmp;
					if(!uf.same(t.a, t.b)) {
						tmp = uf.get_size(t.a) + uf.get_size(t.b);
					}
					else {
						tmp = uf.get_size(t.a);
					}
					if(tmp >= t.c) iq[at + 1][l].pb(vec[i]);
					else iq[at + 1][r].pb(vec[i]);
				}
				iqat++;
			}
		}
		at++;
	}
}