Codeforces Round #450(Div. 2)

A
はい。
B
解けなかったです。(絶望)
でもこれまあまあ難しい気がするんだけどどうなんだろう。

a*10^k/bの1の位を求めたいとします。以下の文字(a,b,c,d,e,f)はすべて整数です。

a*10^k/b=e+d/b(d < b)と表されているとしましょう。すると、
a*10^(k+1)/b=10*e+d*10/bとなり、d*10/bの1の位がcと一致するか確認すればいいです。
一致しない時、d*10/b=f+d'/b(d' < b)と表せば、d→d'と同じ形になるので帰納法を適用できます。

またdの値としてありうるのはb個しかないので、この操作をb回繰り返せばcが出るか出ないか判定できます。

てそれって結局筆算そのままじゃないですか?ということに気づいて悲しくなりました。

int A, B, C;

void solve() {
	cin >> A >> B >> C;
	for(int i = 1; i < B + 1; i++) {
		A *= 10;
		if(A / B == C) {
			cout << i << "\n";
			return;
		}
		A %= B;
	}
	cout << -1 << "\n";
}

C
ある要素vが条件を満たすとき、消された可能性がある要素uは区間の形で求まります。
なので累積和を取ればいいです。

めちゃくちゃWA出した。

D
包除原理すればいいです。一番すんなりできました。

E

ARC086

C
ノーコメント

D
符号を全部揃えれば簡単です。

E(部分点)
木dpしただけ。満点解法はマージテクらしいです。

int N;
int P[MAX_N];
vector<int> G[MAX_N];
int dep[MAX_N];

ll dp[2010][2010][2];

void loop(int v, int d) {
	dep[d]++;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		loop(n, d + 1);
	}
	rep(k, 0, N) {
		ll mul = 1, smul = 1;
		rep(i, 0, sz(G[v])) {
			int n = G[v][i];
			MUL(mul, dp[k][n][0]);
			MUL(smul, (dp[k][n][0] + dp[k][n][1]) % mod);
		}
		rep(i, 0, sz(G[v])) {
			int n = G[v][i];
			ADD(dp[k + 1][v][1], mul * dp[k][n][1] % mod * invf(dp[k][n][0]) % mod);
		}
		dp[k + 1][v][0] = (smul - dp[k + 1][v][1] + mod) % mod;
	}
	dp[0][v][0] = dp[0][v][1] = 1;
}

void solve() {
	cin >> N; N++;
	// init(N + 10);
	P[0] = -1;
	rep(i, 0, N - 1) {
		cin >> P[i + 1];
		G[P[i + 1]].pb(i + 1);
	}
	loop(0, 0);
	ll ans = 0;
	rep(i, 0, N + 1) {
		ADD(ans, dp[i][0][1] * mod_pow(2, N - dep[i]) % mod);
	}
	cout << ans << "\n";
}

E(満点)
マージテクします。dp列をいちいちすべて更新しなくていいことに気づくことが重要です。
ビー玉が2つ以上の時の処理に意外に手間取りました。

計算量ですが、高さdにある隣り合う2頂点u,vはlca(u,v)で1回更新されます。
よって高さdにある頂点数をavとするとav-1回の更新で済むので、各高さについて考えればO(N)となります。

int N;
vector<int> G[MAX_N];
deque<ll> S[MAX_N][3];
int dep[MAX_N];

void loop(int v, int d) {
	dep[d]++;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		loop(n, d + 1);
		int mv = sz(S[v][0]), mn = sz(S[n][0]);
		if(mv < mn) {
			rep(k, 0, 3) swap(S[v][k], S[n][k]);
			swap(mv, mn);
		}

		vector<vl> cnt(3, vl(mn, 0));
		vector<ll> vvec(3, 0), nvec(3, 0);

		rep(i, 0, mn) {
			rep(k, 0, 3) {
				if(S[v][k].empty()) vvec[k] = 0;
				else { 
					vvec[k] = S[v][k].front(); S[v][k].pop_front(); 
				}
			}
			rep(k, 0, 3) {
				if(S[n][k].empty()) nvec[k] = 0;
				else { 
					nvec[k] = S[n][k].front(); S[n][k].pop_front(); 
				}
			}
			rep(j, 0, 3) {
				rep(k, 0, 3) {
					ADD(cnt[min(j + k, 2)][i], vvec[j] * nvec[k] % mod);
				}
			}
		}
		rer(i, mn, 0) {
			rep(k, 0, 3) S[v][k].push_front(cnt[k][i]);
		}
	}
	vector<ll> zero, one;  
	for(int i = 0; ; i++) {
		if(S[v][2].empty()) break;
		ll v0 = S[v][0].front(); S[v][0].pop_front();
		ll v1 = S[v][1].front(); S[v][1].pop_front();
		ll v2 = S[v][2].front(); S[v][2].pop_front();
		zero.pb((v0 + v2) % mod);
		one.pb(v1);
	}
	rer(i, sz(zero), 0) {
		S[v][0].push_front(zero[i]);
		S[v][1].push_front(one[i]);
	}
	S[v][0].push_front(1);
	S[v][1].push_front(1);
	S[v][2].clear();
}

void solve() {
	cin >> N; N++;
	rep(i, 0, N - 1) {
		int p; cin >> p;
		G[p].pb(i + 1);
	}
	loop(0, 0);
	ll ans = 0;
	int cnt = 0;
	while(!S[0][1].empty()) {
		ll x = S[0][1].front();
		S[0][1].pop_front();
		ADD(ans, x * mod_pow(2, N - dep[cnt]) % mod);
		cnt++;
	}
	cout << ans << "\n";
}

F
コンテスト中誰も通してないしやばそう。

マージテクUF

todoリストに載っていたので。

struct mergeUF { //O(logn^2)
	int n;
	vector<set<int>> g;
	vector<int> gat;
	void init(int mx) {
		n = mx;
		g.resize(n); gat.resize(n);
		rep(i, 0, n) {
			g[i].insert(i);
			gat[i] = i;
		}
	}

	mergeUF(int mx = 0) { init(mx); }

	void unite(int x, int y) {
		int a = gat[x], b = gat[y];
		if(a == b) return;
		if(sz(g[a]) > sz(g[b])) swap(a, b);

		for(int s : g[a]) {
			gat[s] = b;
			g[b].insert(s);
		}
		g[a].clear();
	}

	bool same(int x, int y) { return gat[x] == gat[y]; }
	void show() {
		rep(i, 0, n) debug(i, vi(all(g[i])));
		debug(gat);
	}
};

setで実装している分遅いですが、mergeされる集合の要素が、mergeする集合に含まれているかなどを確認できたり、いろいろ機能を追加できます。

COLOCON -Colopl programming contest 2018

https://colopl2018-qual.contest.atcoder.jp/

久しぶりの投稿です。いろいろ忙しかった。
やっぱりコンテストだと結構焦ってまともに考えられないなぁ。

C
偶数は一緒に使えないので、すべて奇数or奇数+偶数1つという組み合わせしかありません。
あと、35以上の素数は考えなくて良くて、31までの計11コの素数で互いに素か判定できます。

ll A, B;
ll P[11] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
 
void solve() {
	cin >> A >> B;
	vl even, odd;
	for(ll i = A; i <= B; i++) {
		if(i % 2 == 0) even.pb(i);
		else odd.pb(i);
	}
	int n = sz(odd);
	int ans = 0;
	rep(bit, 0, (1 << n)) {
		vi cnt(11, 0);
		bool found = false;
		rep(i, 0, n) {
			if(bit & (1 << i)) continue;
			rep(j, 0, 11) {
				ll p = P[j];
				if(odd[i] % p == 0) {
					if(cnt[j] != 0) {
						found = true;
						break;
					}
					else cnt[j]++;
				}
			}
			if(found) break;
		}
		if(found) continue;
		ans++;
		rep(i, 0, sz(even)) {
			bool ok = true;
			rep(j, 0, 11) {
				ll p = P[j];
				if(even[i] % p == 0) {
					if(cnt[j] != 0) {
						ok = false;
						break;
					}
				}
			}
			if(ok) ans++;
		}
	}
	cout << ans << "\n";
}

D
まず、スタミナを消費するときはすべて消費すると考えていいです。
スタミナを時刻t1,t2...,tkで消費するとすれば、得られる知力はX+Σmax(X, ti-t(i-1))となります。
また、ti,t(i+1),t(i+2)について、t(i+2)-t(i)<=Xを満たす場合、t(i+1)は不要になります。
よってtiの次にスタミナを消費する時間はtl-ti>Xを初めて満たすlを考えればtlまたはtl-1となります。
なのでO(N^2)でdpできます。

int N, X;
int A[5010];
ll dp[5010][5010];
int to[5010];
 
void solve() {
	cin >> N >> X;
	rep(i, 0, N) {
		cin >> A[i];
	}
	rep(i, 0, N - 1) {
		int ub = i;
		while(A[ub + 1] - A[i] < X) {
			ub++;
			if(ub == N - 1) break;
		}
		to[i] = ub;
	}
	// debug(vi(to, to + N));
	dp[0][1] = X;
	rep(i, 0, N - 1) {
		rep(k, 0, N) {
			if(!dp[i][k]) continue;
			MAX(dp[to[i]][k + 1], (dp[i][k] + A[to[i]] - A[i]));
			if(to[i] != N - 1) {
				MAX(dp[to[i] + 1][k + 1], (dp[i][k] + X));
			}
		}
	}
	/*
	rep(i, 0, N) {
		rep(k, 1, N + 1) {
			debug(i, k, dp[i][k]);
		}
	}
	*/
	ll ans = 0;
	rep(k, 1, N + 1) {
		rep(i, 0, N) {
			MAX(ans, dp[i][k]);
		}
		cout << ans << "\n";
	}
}

スライド最大値をすれば確かにやるだけなんですが、自信がなかったので考察してAC。

以下はスライド最大値バージョン

struct slidemax {
	ll que[MAX_N];
	int s, e;
	void init() {
		s = 0; e = 0;
	}
	void add(ll x) {
		while(s < e && que[e - 1] < x) e--;
		que[e++] = x;
	}
	void remove(ll x) {
		if(s < e && que[s] == x) s++;
	}
	bool empty() {
		return s == e;
	}
	ll get() {
		if(s == e) return -linf;
		else return que[s];
	}
	void show() {
		debug(vi(que + s, que + e));
	}
};

int N, X;
int T[5010];
ll dp[2][5010];

void solve() {
	cin >> N >> X;
	rep(i, 0, N) cin >> T[i];
	rep(i, 0, N) dp[0][i] = X;
	cout << X << "\n";
	int now = 0, next = 1;
	rep(k, 2, N + 1) {
		ll ans = 0;
		slidemax que;
		que.init();
		memset(dp[next], 0, sizeof(dp[next]));
		int lv = -1;
		rep(i, 0, N) {
			while(lv + 1 < N && T[i] - T[lv + 1] > X) {
				lv++;
				que.remove(dp[now][lv] - T[lv]);
			}
			MAX(dp[next][i], que.get() + T[i]);
			if(lv >= 0) MAX(dp[next][i], dp[now][lv] + X);
			MAX(ans, dp[next][i]);

			que.add(dp[now][i] - T[i]);
		}
		cout << ans << "\n";
		swap(now, next);
	}
}

ライブラリ化できちゃうんですね。範囲に新たに入った値をadd,範囲から出た値をremoveすれば区間の最小値が求まります。

E
網目状に線分を引いていきます。
網目の最小単位によって(n*n+2*n+2)コの領域を新たに作ることができます。
使う点も4n+4コになるので、5000コの制限をクリアできます。
最初実装したやつは網目同士が重なってしまってWAになりました。
アイディア自体はコンテスト中に思いついたけどやっぱり通せないですね。

int N;
vector<pi> ans;

void loop(int D, int at) {
	int n = 0;
	while((n + 2) * (n + 2) + 2 * (n + 2) + 2 <= D) n += 2;
	if(n == 0) {
		ans.pb(pi(at, at + 1));
		ans.pb(pi(at + 2, at + 1));
		if(D - 2 != 0) loop(D - 2, at + 2);
		else ans.pb(pi(at + 2, at + 2));
		ans.pb(pi(at + 1, at + 2));
		ans.pb(pi(at + 1, at));
	}
	else {
		rep(i, 0, n / 2) {
			ans.pb(pi(at + i * 2, at + n + 1));
			ans.pb(pi(at + i * 2 + 1, at + n + 1));
			ans.pb(pi(at + i * 2 + 1, at - 1));
			ans.pb(pi(at + i * 2 + 2, at - 1));
		}
		ans.pb(pi(at + n, at + n + 1));
		ans.pb(pi(at + n + 2, at + n + 1));
		int L = n * n + 2 * n + 2;
		if(D - L != 0)  loop(D - L, at + n + 2);
		else  ans.pb(pi(at + n + 2, at + n + 2));
		ans.pb(pi(at + n + 1, at + n + 2));
		ans.pb(pi(at + n + 1, at + n));
		rer(i, (n / 2), 0) {
			ans.pb(pi(at - 1, at + i * 2 + 2));
			ans.pb(pi(at - 1, at + i * 2 + 1));
			ans.pb(pi(at + n + 1, at + i * 2 + 1));
			ans.pb(pi(at + n + 1, at + i * 2));
		}
	}
}

void solve() {
	cin >> N;
	if(N == 2) {
		cout << 4 << "\n";
		cout << 0 << " " << 0 << "\n";
		cout << 0 << " " << 1 << "\n";
		cout << 1 << " " << 1 << "\n";
		cout << 1 << " " << 0 << "\n";
		return;
	}
	if((N - 1) % 2 == 0) {
		ans.pb(pi(0, 0));
		loop(N - 1, 0);
	}
	else {
		ans.pb(pi(0, 0));
		ans.pb(pi(1, 0));
		loop(N - 2, 1);
		ans.pb(pi(0, 1));
	}
	cout << sz(ans) << "\n";
	rep(i, 0, sz(ans)) {
		cout << ans[i].fst << " " << ans[i].sec << "\n";
	}
}

ジャッジはオイラーの多面体定理を使っているらしいですね。
想定解のほうがシンプルでいいですね。

AOJ 1169: The Most Powerful Spell

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1169

dp[i][j]:=j番目のnodeについた時、文字列の長さがiのもののうち辞書列最小のもの
を更新していきます。i<=N*12までdpを更新します。

最小の呪文が決まるときは辞書列最小文字列の長さN*6以下になりますが、決まらないと、N*6より長さが大きい文字列が得られるので、その場合はNOを返します。

ベルマンフォードの負のサイクルの見つけ方と同じですね。

int N, M, S, T;
 
string dp[500][50];
vector<ps> G[50];
 
const string inf(1, (char)('z' + 1));
 
void solve() {
    while(true) {
        cin >> N >> M >> S >> T;
        if(N == 0) break;
        rep(i, 0, N) {
            G[i].clear();
        }
        rep(i, 0, M) {
            int a, b;
            string str;
            cin >> a >> b >> str;
            G[b].push_back(ps(a, str));
        }
        rep(i, 0, N * 12 + 1) 
            rep(j, 0, N) dp[i][j] = inf;
        dp[0][S] = "";
        rep(i, 0, N * 12 + 1) {
            rep(j, 0, N) {
                rep(k, 0, (int)G[j].size()) {
                    int n = G[j][k].fst;
                    string s = G[j][k].sec;
                    int sz = s.size();
                    if(i - sz >= 0 && dp[i - sz][n] != inf) {
                        dp[i][j] = min(dp[i][j], dp[i - sz][n] + s);
                    }
                }
            }
        }
        string res = inf;
        rep(i, 0, N * 12 + 1) {
            if(res > dp[i][T]) {
                if(dp[i][T] == "") continue;
                if(i <= N * 6) {
                    res = dp[i][T];
                }
                else {
                    res = "NO";
                    break;
                }
            }
        }
        if(res == inf) res = "NO";
        cout << res << '\n';
    }
}

なぜか記事書いてなかった…

Codeforces Round #438F: Yet Another Minimization Problem

http://codeforces.com/problemset/problem/868/F

良問of良問だと思う。

まず簡単なdpから考えて、dp(i,j):=j番目までの数列をiコに分割した時の最小コスト、と定義すれば
dp(i,j)=min(dp(i-1,j')+cost(j',j1))でできます。この時dp(i,j)が最小値となるj'をp(j)と表すと、
dp(i,j1), dp(i,j2)(j1p(j2)を仮定すると、コストが優モジュラー性(cost(x+i+j)-cost(x+i)>=cost(x+i)-cost(i)つまり、要素が多いほど要素を加えた時の変化も大きくなる)を有するので、cost(p(j2),j2)+cost(p(j1),j1)>=cost(p(j2),j1)+cost(p(j1),j2)が成立します。また、
dp(i,j2)が最小なので、dp(i-1,p(j2))+cost(p(j2)+j2)cost(p(j2)+j2)-cost(p(j1),j2)>=cost(p(j2),j1)-cost(p(j1),j1)となり、
dp(i,j1)=dp(i-1,p(j1))+cost(p(j1),j1)>dp(i-1,p(j2))+cost(p(j2),j1)となりますが、これはj1のとき最小であることと矛盾するので示せました。

単調性を有するdpの一般的なテクとして分割統治法があります。
真ん中の要素をとって、それに対する遷移をO(N)で全部試します。真ん中の要素から右左と潜ればO(NlogN)になるというテクニックです。
例としては
https://online.acmicpc.org/problems/money
とかです。

最後にcost(l,r)を求めたいのですが、これは真ん中の要素をmとすれば、[p(m),m)の区間から値を加えたり削除したりを区間の長さに等しい計算量だけ行えば、その区間についての必要なcostは求まるので、奈良市計算量O(1)です。

int N, K;
int lv, rv;
int A[MAX_N];
int C[200010];
ll dp[30][200010];
ll S;

void add(int v) {
	S += C[A[v]];
	C[A[v]]++;
}

void sub(int v) {
	C[A[v]]--;
	S -= C[A[v]];
}

void query(int l, int r) { //[lv, rv)to[l, r)
	while(lv < l) sub(lv++);
	while(lv > l) add(--lv);
	while(rv > r) sub(--rv);
	while(rv < r) add(rv++);
}

void loop(int l, int r, int pl, int pr, int k) { //[l, r) and [pl, pr)
	int m = (l + r) / 2;
	int at = 0;
	for(int i = min(m, pr); i >= pl; i--) {
		query(i, m);
		if(dp[k + 1][m] >= S + dp[k][i]) {
			at = i;
			dp[k + 1][m] = S + dp[k][i];
		}
	}
	if(r - l <= 1) return;
	loop(l, m, pl, at, k);
	loop(m + 1, r, at, pr, k);
}

void solve() {
	cin >> N >> K;
	rep(i, 0, N) cin >> A[i];
	S = 0; lv = 0; rv = 0;
	dp[1][0] = linf;
	rep(i, 1, N + 1) {
		query(0, i);
		dp[1][i] = S;
	}
	rep(k, 1, K) rep(i, 0, N + 1) dp[k + 1][i] = linf;
	rep(i, 1, K) loop(0, N + 1, 0, N + 1, i);
	cout << dp[K][N] << "\n";
}

dp,優モジュラー性、単調性、分割統治法といろいろ問題を構成する要素があって楽しい。
Endagorion先生流石です。と思ったけどどうやら典型らしい…。

2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest,D: Packmen Strike Back

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

これは考察系のDP。

場合分けでtrivialな場合は別で処理します。

非自明(Pが2つ以上ある)の時、まず二分探索して、距離Kすすめるとき*をすべて覆えるか?という問題を解くことを考えます。

dp(i):=i番目のPを使った時、*をカバーできる範囲が[0, l)だとして、lの最大値とします。
するとi+1番目のPがi番目の時点でカバーできているのなら、区間は必ず右に伸ばせばいいです。
カバーできてないとすると、[dp(i),P(i+1)の区間をカバーするのはi+1番目のP、またはi+2番目のPとなります。
なぜなら、i+k番目(k>=3)のPでその区間をカバーしたとすると、i+k-1番目のPは右に伸ばす場合が、dp(i+k)の候補になりえます。しかしi+k-2以下は右に伸ばすのも左に伸ばすのも自由になり、i+1番目のPでカバーしても問題ありません。

なのでdp(i)を更新するためにはdp(i-1)とdp(i-2)の値のみだけが必要で、dp(N)で求められます。
全部でO(NlogN)となり十分間に合います。

O(N)個参照しないといけないと見せて実はO(1)で済む系DPですね。
http://codeforces.com/contest/853/problem/D(解いてないけど)
とかもこれと同じ系統です。

int N, M;
string str;
int minv, maxv;
int P[1000010];
int S[1000010];
int dp[1000010];

bool exist(int l, int r) {
	return ((r > l) && (S[r] - S[l]));
}

bool C(int m) {
	rep(i, 0, M + 1) dp[i] = 0;
	rep(i, 1, M + 1) {
		int e = P[i - 1] + 1;
		if(!exist(dp[i - 1], e - m - 1)) MAX(dp[i], e);
		if(!exist(dp[i - 1], e)) MAX(dp[i], e + m);
		if(i != 1) {
			int f = P[i - 2] + 1;
			if(!exist(dp[i - 2], e - m - 1)) MAX(dp[i], f + m);
		}
	}
	// debug(m, vi(dp, dp + M + 1));
	return dp[M] > maxv;
}

void solve() {
	cin >> N >> str;
	M = 0;
	rep(i, 0, N) {
		if(str[i] == 'P') P[M++] = i;
		S[i + 1] = S[i] + (str[i] == '*');
	}
	minv = inf; maxv = -inf;
	rep(i, 0, N) {
		if(str[i] != '*') continue;
		MIN(minv, i);
		MAX(maxv, i);
	}
	if(M == 1) {
		int p = P[0];
		int lc = S[p], rc = S[N] - S[p];
		if(lc > rc) {
			cout << lc << " " << p - minv << "\n";
		}
		else if(lc < rc) {
			cout << rc << " " << maxv - p << "\n";
		}
		else { //lc == rc
			cout << lc << " " << min(maxv - p, p - minv) << "\n";
		}
		return;
	}
	C(2);
	int lv = 0, rv = N;
	while(rv - lv > 1) { //minimize
		int m = (lv + rv) / 2;
		if(C(m)) rv = m;
		else lv = m;
	}
	cout << S[N] << " " << rv << "\n";
}