行く年来る年

2017年

重要なアルゴリズムはだいたい抑えられた。(特にflow)

問題の解き方が少しわかってきた。(前まではひらめくまで途方に暮れていた)

年末はコンテスト結構出れた。AtCoderのみだけど。

2018年目標

AtCoder Rate2600

CodeForces Rate2200

AtCoder精進(AGC,ARC)

できたら作問

赤一歩手前くらいまで到達できるとなぁ。

Codeforces Round #455 (Div. 2)

http://codeforces.com/contest/909/problem/E

全体的に問題文の把握に手間がかかっていますね…

A
はい。
B
親の顔より見た問題。一番重なっているところを累積和で求めます。
C
勘違いした…
D
削除は奈良市計算量チャンスです。
E
問題を理解するのに無限に時間を費やした。
トポロジカルソートして一番1の連続した区間が多いpathを求めます。
トポロジカルソートの実装を忘れたので戒めとしてコード貼ります。dfsしてreverseですよ。

int N, M;
int A[MAX_N];
int dp[MAX_N];
bool used[MAX_N];
vi ord;
vi G[MAX_N];

void dfs(int v) {
	used[v] = true;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(!used[n]) dfs(n);
	}
	ord.pb(v);
}

void solve() {
	cin >> N >> M;
	rep(i, 0, N) {
		cin >> A[i];
		if(A[i] == 1) dp[i] = 1;
	}
	rep(i, 0, M) {
		int a, b;
		cin >> a >> b;
		G[b].pb(a);
	}
	rep(i, 0, N) {
		if(!used[i]) dfs(i);
	}
	reverse(all(ord));
	rep(i, 0, N) {
		int v = ord[i];
		if(A[v] == 0) {
			rep(j, 0, sz(G[v])) {
				int n = G[v][j];
				if(A[n] == 1) MAX(dp[n], dp[v] + 1);
				else MAX(dp[n], dp[v]);
			}
		}
		else {
			rep(j, 0, sz(G[v])) {
				int n = G[v][j];
				MAX(dp[n], dp[v]);
			}
		}
	}
	int ans = 0;
	rep(i, 0, N) MAX(ans, dp[i]);
	cout << ans << "\n";
}

F
2番目は普通にできて、1番目は偶数の場合はできて、奇数の場合はできないことを証明しようとしてたんですができませんでした…。
さらに解説で4行くらいで済まされて悲しかった。ディレクリで終了です。

1番目は(2^n,2^n-1),(2^n+1,2^n-2)...みたいに並べて再帰的にやります。
2番目は(N<=5||N=2^k)の時できなくて、N=6,N=7は埋め込みます。
N>=8は奇数偶数で場合分けして、N=6とN=7の結果を利用します。

int N;
int ans[MAX_N];

void loop_sub1(int n) {
	if(n == 0) return;
	int pow2 = 1;
	while(pow2 * 2 <= n) pow2 *= 2;
	rep(i, 0, n - pow2 + 1) {
		int a = pow2 + i, b = pow2 - i - 1;
		ans[a] = b;
		ans[b] = a;
	}
	loop_sub1(pow2 * 2 - n - 2);
}

void ans_show() {
	cout << "YES\n";
	rep(i, 1, N) {
		cout << ans[i] << " ";
	}
	cout << ans[N] << "\n";
}

void sub1() {
	if(N % 2 == 1) cout << "NO\n";
	else {
		loop_sub1(N);
		ans_show();
	}
}

void sub2_6() {
	ans[1] = 3; ans[3] = 1;
	ans[2] = 6; ans[6] = 2;
	ans[4] = 5; ans[5] = 4;
}

void sub2_7() {
	ans[1] = 3; ans[3] = 7; ans[7] = 1;
	ans[2] = 6; ans[6] = 2;
	ans[4] = 5; ans[5] = 4;
}

void sub2() {
	if(N <= 5) {
		cout << "NO\n";
	}
	else if(N == 6) {
		sub2_6();
		ans_show();
	}
	else if(N == 7) {
		sub2_7();
		ans_show();
	}
	else {
		int pow2 = 8;
		while(pow2 * 2 <= N) pow2 *= 2;
		if(N - pow2 == 0) cout << "NO\n";
		else if((N - pow2) % 2 == 1) {
			sub2_7();
			for(int i = 8; i < N; i += 2) {
				ans[i] = i + 1; ans[i + 1] = i;
			}
			ans_show();
		}
		else {
			sub2_6();
			for(int i = 8; i <= pow2; i += 2) {
				ans[i] = i + 1; ans[i + 1] = i;
			}
			ans[7] = pow2 + 1; ans[pow2 + 1] = 7;
			ans[pow2] = pow2 + 2; ans[pow2 + 2] = pow2;
			for(int i = pow2 + 3; i < N; i += 2) {
				ans[i] = i + 1; ans[i + 1] = i;
			}
			ans_show();
		}
	}
}

void solve() {
	cin >> N;
	sub1();
	sub2();
}

全部解けそうだったね。

ARC068

https://beta.atcoder.jp/contests/arc068

C
はい。

D
結局2枚捨てるという操作なので。

E
解法2つあります。

dの倍数のdを小さくすると、r - l <= dを満たす区間、つまりl<=x < r の間にdの倍数が1つ以上ある区間の数は増えていきます。
これを利用する方法が1つです。

もうひとつは区間(l,r)を二次元plotすると、長方形領域にある点の数を数える問題になるので平面走査する方法です。
下のコードは2つ目の方法ですが、範囲を±1でミスりまくって結構辛かった。

区間の長さを短くするというのも本質的な考察になるんですね。二次元plotの方は思いついてもよかったなぁ。

int N, M;
vi point[MAX_N];
vector<pi> interval[MAX_N];
int ans[MAX_N];
BIT bit;

void solve() {
	cin >> N >> M;
	bit.init(M + 2);
	rep(i, 0, N) {
		int l, r; cin >> l >> r; r++;
		point[l].pb(r);
	}
	rep(i, 1, M + 1) {
		for(int j = -i; j + i <= M; j += i) {
			int l = j, r = j + i;
			if(l >= 0) interval[l + 1].pb(pi(r + 1, -i));
			interval[r + 1].pb(pi(r + 1, i));
		}
	}
	rep(i, 0, M + 2) {
		rep(j, 0, sz(interval[i])) {
			pi p = interval[i][j];
			int v = abs(p.sec);
			if(p.sec < 0) {
				ans[v] -= bit.get(p.fst, M + 2);
			}
			else ans[v] += bit.get(p.fst, M + 2);
		}
		rep(j, 0, sz(point[i])) {
			int p = point[i][j];
			bit.update(p, p + 1, 1);
		}
	}
	rep(i, 1, M + 1) {
		cout << ans[i] << "\n";
	}
}

ARC088

https://beta.atcoder.jp/contests/arc088

C
A*2^n<=B

D
結構詰まった人もいるっぽい。端は好き勝手変えられるので真ん中だけ考えればいいです。

AtCoder Regular Contest 080F: Prime Flip - omochan's diary

のように区間→2点更新の問題に言い換えられますが、今回はそれをすると逆に辛い問題に帰着されます。悲しい。

E
なんだこれはたまげたなぁ…

POJ 1854: Evil Straw Warts Live - omochan's diary

F
これも解いたことあるし、でもコンテスト中勘違いして解けなかった…Eまで解いて満足してしまった感がある。
あとこういう削除が絡む操作はsetでやっちゃいましょう。

CF434D: Wizard's Tour - omochan's diary

int N;
int in[MAX_N];
vi G[MAX_N];
int dp[MAX_N];
int M;

void dfs(int v, int p) {
	multiset<int> S;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(n == p) continue;
		dfs(n, v);
		if(dp[n] != -1) S.insert(-(dp[n] + 1));
	}
	if(in[v] % 2) S.insert(0);
	while(!S.empty()) {
		int t = -(*S.begin());
		S.erase(S.begin());
		auto b = S.lower_bound(-(M - t));
		if(b != S.end()) {
			S.erase(b);
		}
		else {
			if(dp[v] == -1) dp[v] = t;
			else dp[v] = M + 1;
		}
	}
}

bool ok(int m) {
	M = m;
	memset(dp, -1, sizeof(dp));
	dfs(0, -1);
	if(dp[0] == -1) return true;
	else return false;
}

void solve() {
	cin >> N;
	rep(i, 0, N - 1) {
		int a, b;
		cin >> a >> b; a--; b--;
		G[a].pb(b);
		G[b].pb(a);
		in[a]++; in[b]++;
	}
	int A = 0;
	rep(i, 0, N) {
		A += in[i] % 2;
	}
	int lv = 0, rv = N;
	while(rv - lv > 1) {
		int m = (lv + rv) / 2;
		if(ok(m)) rv = m;
		else lv = m;
	}
	cout << A / 2 << " " << rv << "\n";
}

ARC067

C
はい。
D
min(B, A * dist)で移動すればいいです。
E
普通にdpするとO(N^3)と見せかけてO(N^2logN)なので間に合います。速く書けてよかった。

void solve() {
	cin >> N >> A >> B >> C >> D;
	C_init(N + 50);

	dp[A][N] = 1;

	for(int i = A; i <= B; i++) {
		rep(n, 0, N + 1) {
			if(!dp[i][n]) continue;
			for(int j = C; j <= D; j++) {
				if(n - i * j >= 0) {
					ADD(dp[i + 1][n - i * j], 
							dp[i][n] * C_(n, i * j) % mod * fac[i * j] % mod * invf(mod_pow(fac[i], j)) % mod * fiv[j] % mod);
				}
				else break;
			}
			ADD(dp[i + 1][n], dp[i][n]);
		}
	}
	cout << dp[B + 1][0] << "\n";
}

F
JOI Cakeみたいな?最大値に注目して区間を分けるやつです。
スライド最小値に思考が行ってしまい良くなかった。
Mo?とも思ったんですが、MoはQが小さいのが本質で、今回はO(N^2)通り試すので使えません。

int N, M;
segtree seg;
ll A[MAX_N];
ll B[5010][210];
ll S[5010][5010];

void addblock(int x1, int x2, int y1, int y2, ll x) {
	S[x1][x2] += x;
	S[x1][y2] -= x;
	S[y1][x2] -= x;
	S[y1][y2] += x;
}


void dfs(int a, int b, int mi, int mj) {
	if(a == b) return;
	pl p = seg.get(a, b).v;
	ll v = p.fst; int t = p.sec;
	addblock(mi, t, t + 1, mj, v);
	dfs(a, t, mi, t);
	dfs(t + 1, b, t + 1, mj);
}

void solve() {
	cin >> N >> M;
	rep(i, 1, N) cin >> A[i];
	rep(i, 1, N + 1) A[i + 1] += A[i];
	rep(i, 0, N) 
		rep(j, 0, M) cin >> B[i][j];

	seg.init(N);
	rep(i, 0, M) {
		rep(j, 0, N) seg.update(j, T(pl(B[j][i], j)));
		dfs(0, N, 0, N);
	}
	rep(i, 0, N + 1) {
		rep(j, 0, N) {
			S[i][j + 1] += S[i][j];
		}
	}
	rep(j, 0, N + 1) {
		rep(i, 0, N) {
			S[i + 1][j] += S[i][j];
		}
	}
	ll ans = 0;
	rep(i, 0, N) {
		rep(j, i, N + 1) {
			MAX(ans, S[i][j] - (A[j] - A[i]));
		}
	}
	cout << ans << "\n";
}

ARC083

https://arc083.contest.atcoder.jp/

C
全通り試しましょう

D
とりあえず全部辺を張ってみて矛盾がないかワーシャルフロイド確かめましょう。矛盾があったら-1を返します。
もし矛盾がなかったら、頂点u,v,kについてdist(u,v)=dist(u,k)+dist(k,v)となっている辺(u,v)を取り除けます。

E
頂点を黒で塗ったら、その部分木の黒のコストはX[c]です。白のコストは小さければ小さいほどいいのでdp[v]として更新していけばよいです。

書くと簡単だけど、思いつくのはやっぱり時間がかかりますね…
典型を増やしていきたい。

ARC087

https://arc087.contest.atcoder.jp/

C
はい。
D
XY独立にできます。
E
本質っぽいgrundyのところまではわかったけどtrie木で敗北しました。
まずstringを2分木に対応させます。そうするといろいろな高さの2分木から頂点を取るゲームになります。
高さがdの2分木のgrundy数はdを2で割り切れる回数+1となるのであとは、trie木で片方しか頂点がない頂点を探せばいいです。

ll L;

int div(ll a) {
	int cnt = 0;
	while(a % 2 == 0) {
		cnt++;
		a /= 2;
	}
	return cnt;
}
struct trie {
	int G[MAX_N][2];
	int A[100];
	int M;

	trie() { init(); }
	void init() {
		memset(G, -1, sizeof(G));
		M = 1;
	}

	void add(const string& str) {
		int n = sz(str);
		int v = 0;
		rep(i, 0, n) {
			int y = str[i] - '0';
			if(G[v][y] == -1) {
				G[v][y] = M++;
			}
			v = G[v][y];
		}
	}
	void show() {
		rep(i, 0, 10) {
			debug(i, G[i][0], G[i][1]);
		}
	}

	void dfs(int v, int d) {
		// debug(v, d);
		int cnt = 0;
		if(G[v][0] != -1) {
			dfs(G[v][0], d + 1); 
			cnt++;
		}
		if(G[v][1] != -1) {
			dfs(G[v][1], d + 1);
			cnt++;
		}
		if(cnt == 1) {
			if(L - d >= 1) A[div(L - d)]++;
		}
	}
	bool win() {
		dfs(0, 0);
		rep(i, 0, 70) {
			if(A[i] % 2) return true;
		}
		return false;
	}
};

int N;
trie T;
string str[MAX_N];

void solve() {
	cin >> N >> L;
	rep(i, 0, N) {
		cin >> str[i];
		T.add(str[i]);
	}
	if(T.win()) {
		cout << "Alice\n";
	}
	else cout << "Bob\n";
}

F

これは初手がわからないと詰むパターンですね…

Σd(k,pk)=Σd(root,k)+d(root,pk)-2d(root, lca(k, pk))ですが、Σd(root,k)+d(root,pk)は一定なので、d(root, lca(k, pk))を最小化すればいいです。
さらにd(root, lca(k, pk)) = 0 <=> rootは重心が成立します。ここが難しいです。まあ木上での距離の和=>重心つかうは定石なんだけども。
証明はそんな大変じゃないです。少し試せばわかります。

重心が2つの時は単純で答えは((N/2)!)^2です。
重心が1つの時、lca(k,pk)!=rootとなるようなパーミュテーションを全体から引きたいので包除原理をします。
重心から生えてる木をT1...,TKとすれば
x1<=T1, ... xK<=TK、Σxi=xとすれば、求める値は

Σ(x=0→N-1)(-1)^x(N-x)! {Σ(x1,x2...xK)Π(k=1→K)C(Tk, xk)^2 xk!}となります。
この{}内をdp[i][x]:=Σ(k=0...i)xi = xの時のΣ(x1,x2...xi)Π(k=1→i)C(Tk, xk)^2 xk! と定義して求めます。
一見O(N^3)に見えますが、よくある木dpのようにO(N^2)となって間に合います。

int N;
vector<int> cen;
vector<int> G[MAX_N];
ll dp[2][MAX_N];

int search_centroid(int v, int p) {
	int s = 1, m = 0;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(p == n) continue;
		int t = search_centroid(n, v);
		s += t;
		MAX(m, t);
	}
	MAX(m, N - s);
	if(m <= N / 2) {
		cen.pb(v);
	}
	return s;
}

void solve() {
	cin >> N;
	C_init(N);
	rep(i, 0, N - 1) {
		int a, b; cin >> a >> b; a--; b--;
		G[b].pb(a);
		G[a].pb(b);
	}
	search_centroid(0, -1);
	if(sz(cen) == 2) {
		cout << fac[N / 2] * fac[N / 2] % mod << "\n";
	}
	else if(sz(cen) == 1) {
		int c = cen[0];
		vector<int> vec;
		rep(i, 0, sz(G[c])) {
			int n = G[c][i];
			vec.pb(search_centroid(n, c));
		}
		int K = sz(vec);
		dp[0][0] = 1;
		int s = 0;
		int now = 0, next = 1;
		rep(i, 0, K) {
			memset(dp[next], 0, sizeof(dp[next]));
			rep(j, 0, s + 1) {
				if(!dp[now][j]) continue;
				int t = vec[i];
				rep(k, 0, t + 1) {
					ADD(dp[next][j + k], dp[now][j] * C(t, k) % mod * C(t, k) % mod * fac[k] % mod);
				}
			}
			s += vec[i];
			swap(now, next);
		}
		ll ans = 0;
		rep(i, 0, N) {
			if(i % 2) ADD(ans, mod - fac[N - i] * dp[now][i] % mod);
			else ADD(ans, fac[N - i] * dp[now][i] % mod);
		}
		cout << ans << "\n";
	}
}

sugimさんみたいに数式を効率良くつかって解けるようになりたいね。