Codeforces Round 383

2017-01-12 | [Competitive programming]

A

全体がサイクルの合併になっていれば OK． (サイクル長が偶数なら 2 で割り，さもなくばサイクル長そのまま) の値をサイクルごとに求め LCM をとる．

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#include <cmath>

#include <stack>

#include <queue>

#include <set>

#include <map>

using namespace std;
#define MOD
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N, C[101];

i64 gcd(i64 a, i64 b)
{
	if (b == 0) return a;
	return gcd(b, a % b);
}
i64 lcm(i64 a, i64 b)
{
	return a / gcd(a, b) * b;
}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d", C + i);
		--C[i];
	}
	i64 ans = 1;
	for (int i = 0; i < N; ++i) {
		int len = 0;
		int p = i;
		for (;;) {
			p = C[p];
			++len;
			if (p == i) break;
			if (len > N) {
				puts("-1");
				return 0;
			}
		}
		ans = lcm(ans, len % 2 == 0 ? (len / 2) : len);
	}
	printf("%lld\n", ans);
	return 0;
}

B

Union Find をした後にナップサックをする．

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#include <cmath>

#include <stack>

#include <queue>

#include <set>

#include <map>

using namespace std;
#define MOD
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N, M, Wmax;
int W[1010], B[1010];
int uf[1010];

int root(int p)
{
	return uf[p] < 0 ? p : (uf[p] = root(uf[p]));
}
void join(int p, int q)
{
	p = root(p);
	q = root(q);
	if (p == q) return;
	uf[p] += uf[q];
	uf[q] = p;
}

vector<int> grp[1010];
vector<int> dp;

vector<int> upd(vector<int> &V, int W, int B)
{
	vector<int> ret = V;
	for (int i = ret.size() - 1; i >= W; --i) {
		ret[i] = max(ret[i], ret[i - W] + B);
	}
	return ret;
}

int main()
{
	scanf("%d%d%d", &N, &M, &Wmax);
	for (int i = 0; i < N; ++i) scanf("%d", W + i);
	for (int i = 0; i < N; ++i) scanf("%d", B + i);
	for (int i = 0; i < N; ++i) uf[i] = -1;
	
	for (int i = 0; i < M; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		join(x - 1, y - 1);
	}

	for (int i = 0; i < N; ++i) {
		grp[root(i)].push_back(i);
	}

	dp = vector<int>(Wmax + 1, 0);
	for (int i = 0; i < N; ++i) if (grp[i].size() > 0) {
		vector<vector<int> > tmp;
		int sw = 0, sb = 0;
		for (int g : grp[i]) {
			sw += W[g];
			sb += B[g];
			tmp.push_back(upd(dp, W[g], B[g]));
		}
		tmp.push_back(upd(dp, sw, sb));
		for (vector<int> &v : tmp) {
			for (int j = 0; j < dp.size(); ++j) dp[j] = max(dp[j], v[j]);
		}
	}
	int ret = 0;
	for (int v : dp) ret = max(ret, v);
	printf("%d\n", ret);

	return 0;
}

C

単純に端から決めるみたいな方針だと難しいが，隣り合っている人同士でペアを作って各ペアの中でも違うものを割り当てる，という条件を課すと簡単に解ける．

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#include <cmath>

#include <stack>

#include <queue>

#include <set>

#include <map>

using namespace std;
#define MOD
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N, A[101010], B[101010];
int uf[404040];
int col[202020];
vector<int> graph[404040];
void diffside(int p, int q)
{
	graph[p].push_back(q);
	graph[q].push_back(p);
}

void setcolor(int p, int v)
{
	if (col[p] != 0) return;
	col[p] = v;
	for (int q : graph[p]) setcolor(q, 3 - v);
}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < 4 * N; ++i) uf[i] = -1;
	for (int i = 0; i < N; ++i) {
		scanf("%d%d", A + i, B + i);
		--A[i]; --B[i];
		diffside(A[i], B[i]);
	}
	for (int i = 0; i < N; ++i) {
		diffside(i * 2, i * 2 + 1);
	}
	for (int i = 0; i < 2 * N; ++i) {
		if (col[i] == 0) setcolor(i, 1);
	}

	for (int i = 0; i < N; ++i) {
		printf("%d %d\n", col[A[i]], col[B[i]]);
	}
	return 0;
}

D

マージテクをするが，マージ先の相手が存在するかどうかを O(1) で判定する必要がある．大きい配列にマージ先の情報をすべて持ってしまえばよいが，いちいち全部更新していると計算量が大きいので，できるだけ使いまわす．

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#include <cmath>

#include <stack>

#include <queue>

#include <set>

#include <map>

using namespace std;
#define MOD
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N;
vector<pair<int, int> > child[505050];
int tbl[1 << 22];
int ans[505050];
int ssize[505050];

int append(vector<pair<int, int> > *lg, int mask, int dep)
{
	int ret = tbl[mask];
	for (int i = 0; i < 22; ++i) ret = max(ret, tbl[mask ^ (1 << i)]);
	lg->push_back({ mask, dep });
	tbl[mask] = max(tbl[mask], dep);
	if (ret < 0) return -1;
	return ret + dep;
}
void clear_tbl(vector<pair<int, int> > *lg)
{
	for (auto p : *lg) tbl[p.first] = -1;
}

int comp_ssize(int p)
{
	ssize[p] = 1;
	for (auto e : child[p]) ssize[p] += comp_ssize(e.first);
	return ssize[p];
}

vector<pair<int, int> > *solve(int p, int mask, int dep)
{
	if (child[p].size() == 0) {
		auto ret = new vector<pair<int, int> >;
		ret->push_back({ mask, dep });
		tbl[mask] = max(tbl[mask], dep);
		ans[p] = 0;
		return ret;
	}

	vector<pair<int, int> > child_ord;
	for (int i = 0; i < child[p].size(); ++i) {
		child_ord.push_back({ ssize[child[p][i].first], i });
	}
	sort(child_ord.begin(), child_ord.end());

	vector<vector<pair<int, int> >*> chs;
	vector<pair<int, int> > *lg;
	for (int i = 0; i < child_ord.size(); ++i) {
		auto ch = child[p][child_ord[i].second];
		auto *tmp = solve(ch.first, mask ^ (1 << ch.second), dep + 1);
		if (i != child_ord.size() - 1) {
			chs.push_back(tmp);
			clear_tbl(tmp);
		} else {
			lg = tmp;
		}
		ans[p] = max(ans[p], ans[ch.first]);
	}
	int s = 0;
	for (auto v : chs) {
		for (auto e : *v) {
			s = max(s, append(lg, e.first, e.second));
		}
		delete v;
	}
	s = max(s, append(lg, mask, dep));
	ans[p] = max(ans[p], s - 2 * dep);
	//printf("%d %d %d\n", s, dep, ans[p]);

	//printf("%d: ", p);

	//for (auto a : *lg) printf("%d,%d ", a.first, a.second);

	//puts("");

	return lg;
}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N - 1; ++i) {
		int p;
		char c[5];
		scanf("%d%s", &p, c);
		child[p - 1].push_back({ i + 1, (int)(c[0] - 'a') });
	}
	for (int i = 0; i < (1 << 22); ++i) tbl[i] = -1;

	comp_ssize(0);
	solve(0, 0, 0);
	for (int i = 0; i < N; ++i) printf("%d%c", ans[i], i == N - 1 ? '\n' : ' ');
	return 0;
}

E

挿入位置ごとに得られる文字列たち，は suffix array があれば効率よくソートできる．クエリは平方分割的なことをすれば効率よく処理できるはず．と思って実装したが間に合わず，終了後送ったものも WA