Yosupo Wettbewerb E: Oh, Vertexes & Edges!

http://kcs.miz-miz.biz/contest/6/view/E

AtCoder Grand Contest 014E: Blue and Red Tree - omochan's diary

これと全く同じじゃん!と思ったけど微妙に違った。

最初辺に注目してマージテクしようと思ったが(つまりqueueに入れるのを辺にした)、これでは新たに両端が黒になった辺がqueueに入れられることはない。入出力5を見てみるとわかると思う。

なのでqueueに入れるのは新たにmergeされた点で、元のグラフで隣接している点が黒のものがあったらmergeするというのを繰り返す。

queue<int> que;
bool B[MAX_N];

struct UF {
	int par[MAX_N];
	set<int> E[MAX_N]; //edge

	int find(int x) {
		if(par[x] == x) return x;
		else return par[x] = find(par[x]);
	}

	void init(int n) {
		rep(i, 0, n) par[i] = i;
	}

	void unite(int a, int b) { //update and merge
		a = find(a);
		b = find(b);
		if(a == b) return;
		par[a] = b;
		if((int)E[a].size() > (int)E[b].size()) swap(E[a], E[b]);
		for(int w: E[a]) {
			if(E[b].count(w)) que.push(w);
			E[b].insert(w);
		}
		E[a].clear();
	}
};

int N, M;

UF U;
vector<int> E[MAX_N];

void solve() {
	cin >> N;
	string str; cin >> str;
	rep(i, 0, N) {
		if(str[i] == 'B') {
			que.push(i);
		}
	}
	U.init(N);
	cin >> M;
	rep(i, 0, M) {
		int a, b;
		cin >> a >> b; a--; b--;
		E[a].pb(b);
		E[b].pb(a);
		U.E[a].insert(b);
		U.E[b].insert(a);
	}
	while(!que.empty()) {
		int v = que.front(); que.pop();
		if(B[v]) continue;
		B[v] = true;
		for(int w: E[v]) {
			if(B[w]) U.unite(w, v);
		}
	}
	rep(i, 0, N) {
		if(B[i]) cout << "B";
		else cout << "W";
	}
	cout << "\n";
}

テストケース何個か試したけどあってるっぽいから多分あってる(適当)

KMP法

KMPのK - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

MP法とKMP法の違い - 生きたい

ここを参考にさせてもらいました。

KMPで求めるのはまさに蟻本p327「禁止文字列」における文字列の状態推移である。
すなわち、ある文字列TとSを比較するとして、Sのi番目でマッチングが失敗したとき、次にどこを見るかを線形時間で求めてくれる。
MPよりも高速。

実はMPに少し手を加えるだけでKMPになる。

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

if(S[i + 1] == S[j]) A[i + 1] = A[j]というのが新しく追加された行だが、S[i + 1]でマッチングが失敗したら、S[i+1]とS[j]は同じ文字なのでS[j]でもマッチングが失敗するからA[j]に移動していいという理屈である。

これによってループ一回あたりO(logK)が達成される。詳しくは上のsnukeさんのブログを参照のこと。

これで何が嬉しいかというと、MP法では「禁止文字列」の下処理がO(K^2)かかっていたが、KMP法ではO(KlogK)となる。
"AACAACAA"みたいな文字列でMP法とKMP法で得られるAを比較してみると、
MP: {-1, 0, 1, 0, 1, 2, 3, 4, 5, 2}
KMP:{-1,-1, 1,-1,-1, 1,-1,-1, 5, 2}
となっており、KMPの方が圧倒的に優秀なことがわかる。

以下はKMP法による「禁止文字列」の下処理

vector<int> A = KMP(S);
rep(i, 0, K) {
	rep(j, 0, 4) {
		if(S[i] == AGCT[j]) nex[i][j] = i + 1;
		else {
			int k = A[i];
			while(k >= 0 && S[k] != AGCT[j]) k = A[k];
			k++;
			nex[i][j] = k;
		}
	}
}

下処理自体はMP法と変わらない。
がんばっても線形にはならない気がするんだけどどうなんだろう…

MP法

MP法を勉強したのでメモ。

文字列の頭良い感じの線形アルゴリズムたち - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

これを参考にしました。

A[i]の定義はS[0:i-1]の接頭辞と接尾辞が最大何文字一致しているかである。
[0:i-1]が一致しているからそんなの常にiになるんじゃねと思うが、接頭辞と接尾辞は文字列自身を含まないのでこの定義でOK。

これを求めて何がいいかというと、例えば文字列Tの中でSがあるか判定するプログラムで、S[0:i-1]で一致しているが、S[i]で不一致の時、次はSの何文字目から見ればいいかがわかる。

具体的には、
T=AGCAGCA…
S=AGCAGCG 
を先頭から比較していくと、i=6で不一致が発生する。T[3,6],S[0,3]は一致しているので、次見るべきはi=4からということになる。
(実際のMP法とは少し違うが)

iまでAが求まっているとする。またA[i]=kとする。A[i+1]を求めるために、まずS[0:k],S[i-k:i]が一致しているか見る。
しかしA[i]=kからS[0:k-1],S[i-k:i-1]が一致することは既知なので実際はS[k]とS[i]を比較すればよい。
もし一致していればA[i]=k+1だが一致していなければ次見るところはA[k]になる。なぜならS[0:k]でうまくいかない以上、次候補となるのは、二番目に最初からのsubstrと後ろからのsubstrが一致しているところである。それはまさしくA[k]であるからだ。

KMPを使って、蟻本p327「禁止文字列」の前処理partを行ってみる。
S[i]=AGCT[j]なら単にnext[i][j]=i+1とすれば良くて
S[i]≠AGCT[j]ならk=A[i]としてmp法の要領でS[k]とAGCT[j]が一致している場所を探す。

しかしこのアルゴリズムでは最悪計算量O(K^2)である。Aばかりの文字列を考えてもらってみるとわかると思う。
next[i]['G']などを求めるのにいちいちO(K)かかる。

蟻本にはO(K)でできる方法があると書いてあるが、これはおそらくKMP法を使ったら達成できるので、朝になったらやってみます。

void solve() {
	N = 3; S = "AT"; K = (int)S.size();
	vector<int> A = MP(S);
	debug(A);
	rep(i, 0, K) {
		rep(j, 0, 4) {
			if(S[i] == AGCT[j]) nex[i][j] = i + 1;
			else {
				int k = A[i];
				while(k >= 0 && S[k] != AGCT[j]) k = A[k];
				k++;
				nex[i][j] = k;
			}
		}
	}

	dp[0][0] = 1;
	rep(i, 1, K) dp[0][i] = 0;

	rep(t, 0, N) {
		rep(i, 0, K) dp[t + 1][i] = 0;

		rep(i, 0, K) {
			rep(j, 0, 4) {
				int ti = nex[i][j];
				if(ti == K) continue;
				ADD(dp[t + 1][ti], dp[t][i]);
			}
		}
	}

	int ans = 0;
	rep(i, 0, K) ADD(ans, dp[N][i]);
	cout << ans << "\n";
}

POJ 1854: Evil Straw Warts Live

http://poj.org/problem?id=1854

蟻本には分割統治法と書いてあるがBITでやってしまった。

同じ文字だったら一番右にあるのと一番左にあるのを回文のペアにするのが良くて、二番目三番目…についても同様である。
違う文字だったら、対称性よりどっちを先に端に持っていってもコストは変わらない。
なので一番左から順番に見ていき、見ている文字とそれとペアを組んでいる文字を文字列から抜いた時の各文字のindexを求める。
これはBITを{0,1,2,3...}と初期化して、range_sumで更新すればできる。

int N, Q;
vector<int> A[26];
int B[MAX_N];
char str[MAX_N];
BIT bit;

int main() {
	scanf("%d", &Q);
	while(Q--) {
		scanf("%s", str);
		N = strlen(str);
		rep(i, 0, 26) A[i].clear();

		rep(i, 0, N) {
			A[str[i] - 'a'].push_back(i);
		}
		int odd = 0;
		rep(i, 0, 26) {
			if((int)A[i].size() % 2 == 1) odd++;
		}
		if(odd >= 2) {
			printf("Impossible\n");
			continue;
		}
		rep(i, 0, 26) {
			int n = (int)A[i].size();
			rep(j, 0, (n + 1) / 2) {
				B[A[i][j]] = A[i][n - j - 1];
			}
		}
		int res = 0;
		bit.init(N);
		rep(i, 0, N) bit.range_add(i + 1, i + 1, i);
		int n = N;
		rep(i, 0, N) {
			if(bit.range_sum(i + 1, i + 1) == 0) {
				int j = B[i] + 1;
				res += n - bit.range_sum(j, j) - 1;
				if(i + 1 != j) {
					bit.range_add(1, j - 1, -1);
					bit.range_add(j, N, -2);
				}
				else {
					bit.range_add(j, N, -1);
				}
				bit.range_add(i + 1, i + 1, inf);
				bit.range_add(j, j, inf);
				n -= 2;
			}
		}
		printf("%d\n", res);
	}
		
	return 0;
}

実装のアイディアがなかなか思いつかなかった。
見ていく順番を単純化することが重要。

AtCoder Grand Contest 014E: Blue and Red Tree

http://agc014.contest.atcoder.jp/tasks/agc014_e

マージテクの問題を一つ解きたくなったので。

詳しくは解説に任せるが、青と赤の辺が重なっている部分を一つの頂点に併合していく感じの操作が出来れば良い。
これは各頂点から生えてる辺を持ってマージテクをしていくことによって実現できる。

実装はendagorionさんのを参考にした。
自力で実装しようとしたら、頂点をマージテクしようとしてうまくできなかった。
グラフもいつものvector G[MAX_N]みたいな形で表現してしまい、mergeしたときの処理が出来なかった。
変に赤と青を区別してしまったため、シンプルな実装からより遠ざけられた。

setの使い方もよくわかっていなくて、イテレータがランダムアクセスできないことを知った。

UF U;
int N;

vector<pi> L[MAX_N];
pi E[2][MAX_N];
set<pi> S[MAX_N];

void solve() {
	cin >> N;
	U.init(N);
	rep(k, 0, 2) {
		rep(i, 0, N - 1) {
			int a, b;
			cin >> a >> b; a--; b--;
			if(a > b) swap(a, b);
			E[k][i] = pi(a, b);
			S[k].insert(pi(a, b));
			L[a].push_back(pi(i, k));
			L[b].push_back(pi(i, k));
		}
	}

	queue<pi> que;
	for(auto w: S[0]) {
		if(S[1].count(w)) que.push(w);
	}

	while(!que.empty()) {
		pi p = que.front(); que.pop();
		int a = U.find(p.fst), b = U.find(p.sec);
		if(a == b) continue;
		if((int)L[a].size() > (int)L[b].size()) swap(a, b);
		U.unite(b, a);
		for(auto w: L[a]) {
			int id = w.fst, k = w.sec;
			S[k].erase(E[k][id]);
			E[k][id].fst = U.find(E[k][id].fst);
			E[k][id].sec = U.find(E[k][id].sec);
			if(E[k][id].fst > E[k][id].sec) swap(E[k][id].fst, E[k][id].sec);
			S[k].insert(E[k][id]);
			if(S[1 - k].count(E[k][id])) que.push(E[k][id]);
			L[b].push_back(w);
		}
		L[a].clear();
	}

	bool ok = true;
	for(int i = 0; i < N; i++) {
		if(U.find(0) != U.find(i)) ok = false;
	}
	cout << (ok ? "YES" : "NO") << "\n"; 
}

この実装ほんとに頭が良すぎる。

UVa 10245: The Closest Pair Problem

UVa Online Judge

蟻本にO(NlogN)になる理由などは述べられている。

実装だが、ここが本当にうまいと思った。

//a is sorted by x coordinate
int m = n / 2;
double x = a[m].fst;
double d = min(closest_pair(a, m), closest_pair(a + m, n - m));
inplace_merge(a, a + m, a + n, compare_y);

xの昇順で真ん中のところに線を引きながら、yの座標でmerge sortを行っている。
これをすることで愚直にsortするとO(Nlog^2N)になるところを改善している。ほかの問題にも応用できそうだ。

あとinplace_mergeというのを使っているが、これがまさにmerge sortを行っている部分。
compare_yという関数を引数にしているが、これは単なるmergeでも指定できる。

mergeといえばデータ構造をマージする際の一般的なテクニックだが、使ったことがないので学習しておきたい。

UVa 12161: Ironman Race in Treeland

UVaデビューです。

UVa Online Judge

重心分解。問題はどうやってsubtree間のpathを高速に処理するか。
まず各subtreeの重心からのpathについてdamageとlengthの合計を求めておく。
それをすべて一つの配列に入れてsortして、その配列と同じ大きさのsegtreeにソート後のlengthを入れておく。
segtreeは区間のmaxと、ある値のupdateをできるものを用意する。
さらにsubtreeのpathを順番に見ていき、許容されるdamage内でlengthが最大のものをsegtreeから求める。
この時、同じsubtree内のpathを参照するとダメなので、見ているpathに相当するsegtreeの値を0にしておく。

一発でsample合って、これは来たか?と思ったが結局3WA。

POJと違っていつものテンプレート使えるからよろしい。

namespace CD { //centroid decomposition

	struct edge { int to, damage, length; };

	vector<edge> G[MAX_N];
	bool centroid[MAX_N];
	int subtree_size[MAX_N];

	void init(int n) {
		rep(i, 0, n) G[i].clear();
	}
	void add_edge(int a, int b, int d, int c) {
		G[a].push_back((edge){b, d, c});
		G[b].push_back((edge){a, d, c});
	}

	int compute_subtree_size(int v, int p) {
		int c = 1;
		rep(i, 0, (int)G[v].size()) {
			int w = G[v][i].to;
			if(w == p || centroid[w]) continue;
			c += compute_subtree_size(G[v][i].to, v);
		}
		subtree_size[v] = c;
		return c;
	}

	pi search_centroid(int v, int p, int t) { 
		pi res = pi(inf, -1);
		int s = 1, m = 0;
		rep(i, 0, (int)G[v].size()) {
			int w = G[v][i].to;
			if(w == p || centroid[w]) continue;

			MIN(res, search_centroid(w, v, t));

			MAX(m, subtree_size[w]);
			s += subtree_size[w];
		}
		MAX(m, t - s);
		MIN(res, pi(m, v));
		return res;
	}

	void update(int s, int n);

	void solve_subproblem(int v) {
		compute_subtree_size(v, -1);
		int s = search_centroid(v, -1, subtree_size[v]).sec;
		centroid[s] = true;

		int cnt = 0;
		rep(i, 0, (int)G[s].size()) {
			if(centroid[G[s][i].to]) continue;
			solve_subproblem(G[s][i].to);
			cnt++;
		}
		update(s, cnt);
		centroid[s] = false;
	}

	////////////////////////////////////////////// edit from here
	
	//distance from centroid
	void enumerate_pathes(int v, int p, int d, int l, int cnt, vector<ppi> &ds) {
		ds.push_back(make_pair(pi(d, l), cnt));
		rep(i, 0, (int)G[v].size()) {
			int w = G[v][i].to;
			if(w == p || centroid[w]) continue;
			enumerate_pathes(w, v, d + G[v][i].damage, l + G[v][i].length, cnt, ds);
		}
	}

	int fd(const vector<ppi>& v, int n) {
		int lv = -1, rv = (int)v.size();
		while(rv - lv > 1) {
			int m = (lv + rv) / 2;
			if(v[m].fst.fst > n) rv = m;
			else lv = m;
		}
		return rv;
	}

	void update(int s, int n) {
		vector<ppi> ds;
		vector<vector<ppi>> tds(n);
		vector<vi> at(n);

		int cnt = 0;
		rep(i, 0, (int)G[s].size()) {
			if(centroid[G[s][i].to]) continue;
			tds[cnt].push_back(make_pair(pi(0, 0), cnt));
			//debug("omo", G[s][i].damage, G[s][i].length);
			enumerate_pathes(G[s][i].to, s, G[s][i].damage, G[s][i].length, cnt, tds[cnt]);

			ds.insert(ds.end(), tds[cnt].begin(), tds[cnt].end());
			cnt++;
		}
		int m = (int)ds.size();
		segtree seg;

		seg.init(m);
		sort(all(ds));

		rep(i, 0, m) {
			at[ds[i].sec].push_back(i);
			seg.update(i, ds[i].fst.sec);
		}

		//debug(s, ds);
		//seg.show();

		rep(i, 0, n) {
			rep(j, 0, (int)at[i].size()) {
				seg.update(at[i][j], 0);
			}

			rep(j, 0, (int)at[i].size()) {
				ppi pp = ds[at[i][j]];
				pi p = pp.fst;
				int at = fd(ds, M - p.fst);
				int res = seg.get(0, at).v;
				//debug(p.fst, M - p.fst, at, p.sec, res);
				MAX(ans, p.sec + res);
			}
			rep(j, 0, (int)at[i].size()) {
				seg.update(at[i][j], ds[at[i][j]].fst.sec);
			}
		}
	}
}


void solve() {
	cin >> Q;
	rep(q, 1, Q + 1) {
		cin >> N >> M;
		CD::init(N);
		rep(i, 0, N - 1) {
			int a, b, d, c;
			cin >> a >> b >> d >> c; a--; b--;
			CD::add_edge(a, b, d, c);
		}
		ans = 0;
		CD::solve_subproblem(0);
		cout << "Case " << q << ": " << ans << "\n";
	}
}

解いているときふとmap使えそうだなと思ったけど、使い方がよくわからず結局segtreeで解いてしまった。
イテレーターのスマートな使い方とか習得したい。