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

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

2018-10-08

JOI埋め(難易度10)

BIT

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

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

2018-09-30

ARC103

Constructive

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

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

2018-09-29

AOJ 1181

Math

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

ものを回転させる問題は他にも
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2169
がありますが、置換で回転をあらわす時の注意事項。
例えば、
(0, 1, 2, 3, 4, 5)
(4, 0, 2, 3, 5, 1)
だとしたら、位置0にあった要素を4に移す置換と考えます。つまり、
f={4, 0, 2, 3, 5, 1}、
変換前の値をvとすれば、変換後のv'は
v'[f[i]]=v[i]を満たします。
値iがjに変わるような置換としがちですが、これではうまく行きません。場所を移すと考えましょう。

set<vi> S;
map<vi, vector<vi>> M;


int F[4][6] = { //1, 2, 3, 4の方向に転がる
	{1, 5, 2, 3, 0, 4}, //a
	{2, 1, 5, 0, 4, 3}, //b
	{3, 1, 0, 5, 4, 2},  //ib
	{4, 0, 2, 3, 5, 1}  //ia
};

int dx[5] = {0, 1, 0, 0, -1};
int dy[5] = {0, 0, 1, -1, 0};

void solve() {
	queue<vi> que;
	que.push(vi{0, 1, 2, 3, 4, 5});
	S.insert(vi{0, 1, 2, 3, 4, 5});
	while(!que.empty()) {
		vi vec = que.front(); que.pop();
		rep(i, 0, 4) {
			vi tmp(6);
			rep(j, 0, 6) {
				tmp[F[i][j]] = vec[j];
			}
			if(!S.count(tmp)) {
				S.insert(tmp); que.push(tmp);
			}
		}
	}
	for(auto vec : S) {
		rep(i, 0, 4) {
			vi tmp(6);
			rep(j, 0, 6) {
				tmp[F[i][j]] = vec[j];
			}
			M[vec].pb(tmp);
		}
		// debug(vec, vector<vi>(all(M[vec])));
	}
	while(true) {
		int N; cin >> N;
		if(N == 0) break;
		map<vi, int> D;
		while(N--) {
			int a, b; cin >> a >> b; a--; b--;
			vi dice;
			for(auto vec : S) {
				if(vec[0] == a && vec[1] == b) dice = vec;
			}
			vi d({100, 0, 0});
			while(true) {
				if(d[0] == 0) break;
				d[0]--;
				if(D.count(d)) {
					d[0]++;
					pi p(-1, -1); //num and dir
					for(int i = 1; i <= 4; i++) {
						vi tmp = d;
						tmp[0]--; tmp[1] += dx[i]; tmp[2] += dy[i];
						if(!D.count(tmp) && dice[i] >= 3) {
							MAX(p, pi(dice[i], i));
						}
					}
					if(p.fst == -1) break;
					else {
						d[1] += dx[p.sec];
						d[2] += dy[p.sec];
						dice = M[dice][p.sec - 1];
					}
				}
			}
			// debug(d, dice[0]);
			D[d] = dice[0];
		}
		vi ans(6, 0);
		for(pair<vi, int> d : D) {
			d.fst[0]++;
			if(!D.count(d.fst)) ans[d.sec]++;
		}
		rep(i, 0, 6) {
			cout << ans[i] << (i == 5 ? '\n' : ' ');
		}
	}
}

面倒of面倒

2018-09-24

JOI埋め(難易度9)

AOJ/AtCoder-JOI

9はそんなに難しくはないですね。
実装が多めなのを考慮してもatcoderで言えば600-700くらい?

Typhoon 平面探査
Stamps pairでdp
Abduction xy独立です。
Ski にぶたん
Chopsticks うわぁこれは反省。区間dpということは両端の値が本質的になるということなのに、片方ばっかりみてた…一応ACしましたが、まずオーダーが意味不明だし、やばいケースだと落ちかねないです。
Regions にぶたんしてからpairでdp。正確にはループ回すだけでいいです。またこのタイプか。
Hide-and-seek 平面走査やるだけなんですが、infの値が小さく設定しすぎて結構詰まった…
Lake 直線に落とし込んでDP。全部値が異なることが重要。

2018-09-24

CODE FESTIVAL 2018 qual A+オマケ

https://beta.atcoder.jp/contests/code-festival-2018-quala

通過です…

A
sortしたけど、要素が3つでなんかオーバーキルな気がしてしまう
B
愚直にやった。sortもしてません
C
まあdpだよね。0にならないとKを減らせないので注意。
D
まあdpだよね。BIT使ったけどよく考えると累積和で十分。
E
最小値固定して、最大値を決めるんだけど、不等式の条件を整理したら二次元座標である領域から点を見つける問題になって、O(ZlogZ)(Z=X+Y)になったが?あんまり同じ解き方している人いませんね…みんな答えを二分探索してるんだけど、結局最大値最小値どっちも移動してあんまいい方針に見えなかった…

オマケ
ABC110C
これ難しくないですか…。S[i]->T[i]にグラフ張って考察したらこんがらがってしまいました…。普通に元の操作で考えればよかったですね。
解法ですがYesの時、グラフで枝分かれができちゃだめなので、単ループor直線になります。

2018-09-22

AGC003F

Tree Matrix

https://agc003.contest.atcoder.jp/tasks/agc003_f

非連結だと勘違いしてハマってた…

まず縦に並べても横に並べても繋がる場合は答えが1です。
どっちもつながらない場合は#の個数をPとしてP^(K-1)です。
問題は片方だけ繋がる場合です。今回は横に繋がるとします。
#が横に２つ連続で繋がるものの個数をen、連結成分の数をfnとします。
また、盤面を横に並べた時#が繋がる個数をDとします。
するとen+1とfn+1はPとDの線形和で表されます。後は行列累乗をO(logK)でやれば答えが求まります。

ただH=1とW=1の時は場合分けが発生するので注意しましょう。

void solve() {
	cin >> H >> W >> K;
	ll p = 0;
	rep(i, 0, H) {
		string str;
		cin >> str;
		rep(j, 0, W) {
			if(str[j] == '#') B[i][j] = 1;
			p += B[i][j];
		}
	}
	int bh = 0, bw = 0;
	rep(j, 0, W) {
		if(B[0][j] == 1 && B[H - 1][j] == 1) bh++;
	}
	rep(i, 0, H) {
		if(B[i][0] == 1 && B[i][W - 1] == 1) bw++;
	}
	if(H == 1) {
		if(bw) cout << 1 << "\n";
		else cout << mod_pow(p, K - 1) << "\n";
	}
	else if(W == 1) {
		if(bh) cout << 1 << "\n";
		else cout << mod_pow(p, K - 1) << "\n";
	}
	else {
		if(bw && bh) {
			cout << 1 << "\n";
		}
		else if(!bw && !bh) {
			cout << mod_pow(p, K - 1) << "\n";
		}
		else {
			int e = 0;
			int f;
			if(bh) {
				rep(i, 0, H - 1) {
					rep(j, 0, W) {
						if(B[i][j] == 1 && B[i + 1][j] == 1) e++;
					}
				}
				f = bh;
			}
			else {
				rep(j, 0, W - 1) {
					rep(i, 0, H) {
						if(B[i][j] == 1 && B[i][j + 1] == 1) e++;
					}
				}
				f = bw;
			}
			// debug(bh, bw, p, e);
			mat A(2, vl(2, 0));
			A[0][0] = p;
			A[0][1] = mod - 1;
			A[1][0] = 0;
			A[1][1] = f;
			mat B = mat_pow(A, K - 1);
			cout << (B[0][0] + B[0][1] * e % mod) % mod << "\n";
		}
	}
}

なんか割と非連結でもいけそうな雰囲気が漂っていたから誤読に全然気づかなかった…。
多分問題数もっと解けばできるできないの判断が鋭くなるんだろうな…

omochan's diary

AGC027