New Year Contest 2015

https://snuke21.contest.atcoder.jp/tasks/snuke21_e

懐かしの。ムズイ。

->初手でいけそうなのが、強連結の条件を考えてみるだけだった。
->強連結成分がL個以上ならまあまあできそう。これが求まればあと引き算するだけ。
-->N!Σ(n+m+...=N)(2^(n(n-1)/2) / n!)(2^m(m-1)/2 / m!)....を求めればいいところまで行けた。
-->しかしこれがムズい。O(N^3)くらいしか思いつかない。どうあがいても無理。
-->緩和したらいけるのではとか思ってみたけど無理。
-->やることなくなって諦めた。
->解説みると、ある条件を満たすnone empty subset Sを数え上げるらしい。思いつけないですこれは。でも詰まったらやっぱり初手選択ミスってることが多いですね。

ARC100F: Colorful Sequences

https://beta.atcoder.jp/contests/arc100/tasks/arc100_d

考えること多すぎ。

->とりまどうやって数え上げるか考える。
-->colorfulな列を考えて、そこにAが何個あるか?
-->i番目からAが始まる列がcolorfulな場合の数Fiを計算する?
-->まあ後者だろう。
->colorfulを数え上げる?not colorfulを数え上げる?
-->colorfulを数え上げるなら包除原理か。
--->でも煩雑そうだし、前M個の情報を完全に持っていないといけなさそう。
-->not colorfulは数えやすそう。
->とりまM=0の場合を考えてみる。
-->dp[i][j]:=iまで見た時前j個のelemが互いに異なる時の場合の数で行ける。
-->割とM > 0の時も応用できそう。
-->Aに同じelemがある時はdp[i][j]使ってiあたりO(1)で計算できる。
->全て違うelemの時が難しいんだろう。
-->K < M
-->全て違ったら、なんか数学的に嬉しそう。変な係数掛けてできる?
--->できないと思いました。結局コレが想定解。
-->じゃあ同じelemが出てくるまでKを伸ばしてあげれば良いのでは。
--->Kまで伸ばす
---->これはO(K^4)となり失敗。
--->本当に同じelemが出たところで切る。
---->そうするとなんか累積和が出てきてO(K^3)
---->実装大変。大学の1限まるまる使った。

SoundHound Programming Contest 2018 Masters Tournament,C: Not Too Close

https://soundhound2018-summer-final-open.contest.atcoder.jp/tasks/soundhound2018_summer_final_c

わりとすっきり解けた気がする。思考プロセス書きます。

N,D<=30
->分割統治?
->直線にしてみる?
->とりあえず緩和して最短距離がD以上のグラフの個数を数えてみる?
-->1から2への全ての経路がD以上になって見やすくなった。
-->bellman-ford的にdp?bfsっぽく距離1,2,3...の点と順番に見ていく?
--->後者っぽい。
--->dp[i][v][w]:=距離iの点まで見て、v個点が使われている。距離i-1で使われた点はw個。この時の場合の数 でできた。
--->緩和いらなくて草。
->こっからバグらせるんだよね。
-->dpにかかる係数をA,Bみたいに文字おいてごまかしたらわかりやすくなった。
-->困難は分割せよってそれ一番言われてる。

int N, D;

ll dp[41][41][41];

void solve() {
	cin >> N >> D;
	C_init(N);
	dp[0][1][1] = 1;
	rep(i, 0, D) {
		rep(v, 1, N) {
			rep(u, 1, N) {
				if(!dp[i][v][u]) continue;
				rep(w, 1, N) {
					ll A = mod_pow((mod_pow(2, u) - 1 + mod) % mod, w);
					ll B = mod_pow(2, w * (w - 1) / 2);
					ll E;
					if(i < D - 1) {
						if(N - v - 1 - w >= 0) E = C(N - (v + 1), w);
						else continue;
					}
					else if(i == D - 1) {
						if(N - v - w >= 0) E = C(N - (v + 1), w - 1);
						else continue;
					}
					else {
						if(N - v - w >= 0) E = C(N - v, w);
						else continue;
					}
					ADD(dp[i + 1][v + w][w], dp[i][v][u] * A % mod * B % mod * E % mod);
				}
			}
		}
	}
	ll res = 0;
	rep(i, 1, N + 1) {
		rep(j, 1, N) {
			ADD(res, dp[D][i][j] * mod_pow(2, j * (N - i) + (N - i) * (N - i - 1) / 2) % mod);
		}
	}
	cout << res << "\n";
}

AGC028

https://agc028.contest.atcoder.jp/

A
map使った。
B
方針ミスって式が複雑になってダメでした…。式で考察するのが苦手すぎる。
てか式で考察が進むことはあまりないんだよなぁ。
C
結構場合分けがあって難しいと思う。1発で通してる人はすごい。
D
おそらく直線にして、区間が一番左になる確率みたいなものから加法定理で解くんだろうけど、詰められる自信がない…。

数え上げの基礎能力が低すぎる。
まあ160位をとりあえず目標にしていたからオッケイかなぁ。

AGC027

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

virtual contestしました。やっぱり時間制限無しでやるのと全然緊張感が違う…

A
うん。
C
行き先がAのみとかBのみになるとヤバイので、そういう点を取り除いていく。
B
焦って、連続した区間でゴミを取っていけばいいと勘違いしてしまった…それで変な方向に考察してしまってダメでした。
なんか解けない問題になったら考察ミスを疑ったほうが良いかも。
D
良問ですね…やっぱりこういう構築は素数が絡むのでしょうか…。
再帰的に解く問題は結構得意だと思うけど、やっぱり構築になるとダメですね…。

JOI埋め(難易度10)

結構骨がある問題ばっかで面白い。

SALT TREE XV 点と辺がともに偶数の時負けであることを示しに行く。やっぱりGameは負けの条件を考えて、(勝ち->負けに必ず落とし込める+負け->負けと遷移できない)を示すのが定石ですね。必要条件から狭めていく感じと同じ。
Rampart '「'と'」'がどこまで伸ばせるかを考えて、対応関係を見ていく。そのときBITで高速化できる。
Long Mansion イマイチすっきり解けない…なんか無駄をなくそうと思うとmergeが見えてきて、それで実装したらならし計算量O(NlogN)になっていた…。図式化がわからない。
Tower of JOIOI 今だったら本戦で何人解くんだろ…。にぶたんしてOIについて貪欲すればいいです。

ARC103

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

F Open- >それっぽい考察はできたけど、Dが同じ値を複数持つ時どうするんだ…- >問題文「Dの値は全て異なる」 - >実装完了。この時点で75分で、300+300+700勢に勝てなさそうなので撤退…

C
これ難しくないか?実装が意外にめんどくさい。

int N;
pi P[2][100010];
int D[100010];

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> D[i];
	rep(i, 0, 2) {
		map<int, int> M;
		rep(j, 0, N / 2) {
			M[D[i + j * 2]]++;
		}
		int n = 0;
		for(auto p : M) {
			P[i][n++] = pi(-p.sec, p.fst);
		}
	}
	rep(i, 0, 2) sort(P[i], P[i] + N / 2);
	bool found = false;
	rep(i, 0, 2) {
		if(P[i][0].sec == P[i][1].sec) found = true;
	}
	if(found) {
		cout << N + P[0][0].fst + P[1][0].fst << "\n";
	}
	else if(P[0][0].sec != P[1][0].sec) {
		cout << N + P[0][0].fst + P[1][0].fst << "\n";
	}
	else {
		cout << min(N + P[0][0].fst + P[1][1].fst, N + P[0][1].fst + P[1][0].fst) << "\n";
	}
}

D
まず制約をちゃんと最後まで読みましょう。とりあえず、2のべき乗を並べるのはわかるとして、実験してみるのが重要でした。
再帰的にコードを書くのだから、前から実験するのは自然な発想だし、すぐできなかったのは反省。
解説では45度回転していますが、コンテスト中その発想にはなり得ないので、やはり実験が正解だったと思います。

int N;
ll X[1010], Y[1010];

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> X[i] >> Y[i];
	bool odd = false, even = false;
	rep(i, 0, N) {
		if((X[i] + Y[i]) % 2) odd = true;
		else even = true;
	}
	if(odd && even) {
		cout << -1 << "\n";
		return;
	}
	if(even) {
		rep(i, 0, N) {
			X[i]--;
		}
	}
	int M = 39;
	cout << (even ? M + 1 : M) << "\n";
	for(int i = 0; i < M; i++) {
		cout << (1ll << (M - i - 1)) << " ";
	}
	if(even) cout << 1 << "\n";
	else cout << "\n";
	rep(i, 0, N) {
		string str;
		rer(j, M, 0) {
			ll d = (1ll << j);
			// debug(X[i], Y[i], d);
			if(X[i] + Y[i] >= 0 && Y[i] - X[i] >= 0) {
				str +=  'U';
				Y[i] -= d;
			}
			else if(X[i] + Y[i] >= 0 && Y[i] - X[i] <= 0) {
				str += 'R';
				X[i] -= d;
			}
			else if(X[i] + Y[i] <= 0 && Y[i] - X[i] >= 0) {
				str += 'L';
				X[i] += d;
			}
			else {
				str += 'D';
				Y[i] += d;
			}
		}
		if(even) str += 'R';
		cout << str << "\n";
	}
}

E
ごにょごにょすればできますね。

int N;
string S;
int A[MAX_N];

pi ans[MAX_N];

void solve() {
	cin >> S;
	N = sz(S);
	rep(i, 0, N) { 
		A[i + 1] = (S[i] == '1');
	}
	if(A[1] != 1) {
		cout << -1 << "\n"; return;
	}
	rep(i, 0, N + 1) {
		if(A[i] != A[N - i]) {
			cout << -1 << "\n"; return;
		}
	}
	ans[0] = pi(0, 1);
	int cur = 1;
	for(int i = 2; i < N; i++) {
		ans[i - 1] = pi(cur, i);
		if(i <= N / 2 && A[i] == 1) cur = i;
	}
	rep(i, 0, N - 1) {
		cout << ans[i].fst + 1 << " " << ans[i].sec + 1 << "\n";
	}
}

F
問題文はちゃんと読みましょう。葉から再帰するのはわかるとして、Dが異なる値であることが本質でした。すると、葉から順番に木の形が決まっていきます。最後重心が残るので、重心が正しい値になっているかチェックすればOK。

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

pl D[MAX_N];
ll ts[MAX_N];
pi ans[MAX_N];

pl dist(int v, int p) {
	pl res(0, 1);
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(n == p) continue;
		pl tmp = dist(n, v);
		res.fst += tmp.fst + tmp.sec;
		res.sec += tmp.sec;
	}
	return res;
}

void solve() {
	cin >> N;
	rep(i, 0, N) {
		cin >> D[i].fst;
		D[i].fst *= -1;
		D[i].sec = i;
	}
	rep(i, 0, N) ts[i] = 1;
	sort(D, D + N);
	rep(i, 0, N - 1) {
		int at = lower_bound(D, D + N, pl(D[i].fst + (N - 2 * ts[i]), -inf)) - D;
		if(at == N || D[at].fst != D[i].fst + (N - 2 * ts[i]) || at <= i) {
			cout << "-1\n"; return;
		}
		ts[at] += ts[i];
		ans[i] = pi(D[i].sec, D[at].sec);
		G[D[i].sec].pb(D[at].sec);
		G[D[at].sec].pb(D[i].sec);
	}
	if(dist(D[N - 1].sec, -1).fst != -D[N - 1].fst) {
		cout << "-1\n"; return;
	}
	rep(i, 0, N - 1) {
		cout << ans[i].fst + 1 << " " << ans[i].sec + 1 << "\n";
	}
}

(問題文はちゃんと読もうな重要な制約が書いてある可能性があるから+もっと再帰的に考えような)ですね…。