こういう問題も冷静になればシンプルに書けるんやなって。

結局、要素番号が偶数のやつから好きにとるか、奇数のやつから好きにとるかをすればいいとわかります。
構成法ですが、
1.数列を後から見て、使うやつまで全て消す。
2.数列を前から見て、使うやつまで全て消す。
3.数列の3番目の要素を見て、使うのだったら2番目に対して操作を行い、そうでなかったら3番目に対して操作を行う。
という順番でやれば簡単だと思います。

すべてマイナスの場合だけ注意しましょう。そのときも一番大きいelementを使うとして、上の構成法でできます。

int N, M = 0;
int A[MAX_N];
bool B[MAX_N];
int L, R;
int ans[MAX_N];

void add(int v) {
	ans[M++] = v;
}

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	ll es = 0, os = 0; //even sum, odd sum
	bool ok = false;// is B[i] == true exists?
	ll mx = -linf; int at = -1; //mxv and where mxv is located
	for(int i = 0; i < N; i++) {
		if(A[i] >= 0) {
			B[i] = true;
			ok = true;
			if(i % 2 == 0) es += A[i];
			else os += A[i];
		}
		if(mx < A[i]) {
			mx = A[i];
			at = i;
		}
	}
	if(!ok) {
		es = at % 2 == 0 ? mx : -linf;
		os = at % 2 == 0 ? -linf : mx;
		B[at] = true;
	}
	if(es >= os) {
		L = 0; 
		R = (N - 1) % 2 == 0 ? N - 1 : N - 2;
	}
	else {
		L = 1;
		R = (N - 1) % 2 == 0 ? N - 2 : N - 1;
	}
	while(!B[L]) L += 2;
	while(!B[R]) R -= 2;
	rep(i, 0, N - 1 - R) add(N - 1 - i);
	rep(i, 0, L) add(0);
	for(int l = L; l < R; l += 2) {
		if(!B[l + 2]) add(2);
		else add(1);
	}

	cout << max(es, os) << "\n";
	cout << M << "\n";
	rep(i, 0, M) {
		cout << ans[i] + 1 << "\n";
	}
}

2018-04-19

AGC014C: Closed Rooms

DFS

https://agc014.contest.atcoder.jp/tasks/agc014_c

結局1回目は開いているところをK回移動、2回目以降は壁を壊しながらK回移動と言い換えられます。
なので2回目以降は4方向のうち一番近い場外へ直線で行くのが最適です。

変数がsx,x,nxと結構出てきてしまったんですけど、xに関する変数がもうひとつあったらバグらせる原因になりますね…考えどころです。
あとcontinueはなるべく使わないようにしました。カッコがないと逆にわかりにくいので。

int N, M, K;
bool vsd[1010][1010];
char S[1010][1010];

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

void solve() {
	cin >> N >> M >> K;
	int sx, sy;
	rep(i, 0, N) {
		rep(j, 0, M) {
			cin >> S[i][j];
			if(S[i][j] == 'S') {
				sx = i; sy = j;
			}
		}
	}
	queue<pi> que;
	vsd[sx][sy] = true;
	que.push(pi(sx, sy));
	rep(q, 0, K) {
		int qs = sz(que);
		while(qs--) {
			pi p = que.front(); que.pop();
			int x = p.fst, y = p.sec;
			rep(i, 0, 4) {
				int nx = x + dx[i], ny = y + dy[i];
				if(0 <= nx && nx < N && 0 <= ny && ny < M) {
					if(S[nx][ny] != '#' && !vsd[nx][ny]) {
						vsd[nx][ny] = true;
						que.push(pi(nx, ny));
					}
				}
			}
		}
	}
	int ans = inf;
	rep(i, 0, N) {
		rep(j, 0, M) {
			if(vsd[i][j]) {
				MIN(ans, 1 + (min(min(i, j), min(N - 1 - i, M - 1 - j)) + K - 1) / K);
			}
		}
	}
	cout << ans << "\n";
}

2018-04-19

CODE FESTIVAL 2017 Elimination Tournament Round 1,C: Paired Parentheses

https://cf17-tournament-round1-open.contest.atcoder.jp/tasks/asaporo2_c

考察よりも実装を重視して解いた。

解法自体は良くありがちなやつ。
2つのカッコ列が成立するための必要条件が、最初がどちらも(、最後がどちらも)、真ん中で違うのが偶数個なのだが、それが実は十分でもあるというもの。なので、基本的に真ん中はAとBの好きな方を取れるが、Aを取る回数が奇数回になってしまった時に調節をしなければならない。調節方法だが、AiとBiの絶対値が一番小さいiを見て、使うのを最善の時と逆にする。これはmultisetを使えばできる。

強い人の実装をみて思ったことは、
1.定義する変数or関数が少ない
2.if文が少ない

だったのでそれに沿って実装してみました。結構コンパクトにかけたんじゃないかなぁ。

int N, Q;
ll A[MAX_N], B[MAX_N]; //[0, 2 * N) !!
multiset<ll> S;

void solve() {
	cin >> N >> Q;
	rep(i, 0, 2 * N) cin >> A[i];
	rep(i, 0, 2 * N) cin >> B[i];

	ll ans = 0; bool odd = false;
	ans += A[0] + A[2 * N - 1];
	rep(i, 1, 2 * N - 1) {
		ans += max(A[i], B[i]);
		odd ^= (A[i] > B[i]);
		S.insert(abs(A[i] - B[i]));
	}
	while(Q--) {
		ll a, x, y;
		cin >> a >> x >> y; a--;
		if(a == 0 || a == 2 * N - 1) {
			ans += x - A[a];
			A[a] = x;
		}
		else {
			odd ^= (A[a] > B[a]);
			odd ^= (x > y);
			ans += max(x, y) - max(A[a], B[a]);
			S.erase(S.lower_bound(abs(A[a] - B[a])));
			S.insert(abs(x - y));
			A[a] = x; B[a] = y;
		}
		cout << (!odd ? ans : ans - (*S.begin())) << "\n";
	}
}

2018-04-18

ARC094D: Worst Case

Constructive

https://arc094.contest.atcoder.jp/tasks/arc094_b

本質は構成ゲーです。

A<=Bとしても一般性を失いません。
CをA*B>C^2を満たすうち最大の数とします。
A=A*Bのとき2*C-2、
C(C+1)=3であることがわかります。
なのでB-A<=2の時は個別にやればよいです。
B-A=0のとき2*A-2
B-A=1のとき2*A-2
B-A=2のとき2*A-1
となります。これで全ての場合がカバーできました。
しかしよく見ると、B-A=2の場合はB-A>=3の時と同じ扱いができるので、結局B-A=0,1,>=2の3通りについて考えれば良いことがわかります。

こういう問題はいい構築方法が思いつけば勝ちですね。
二分探索思いつくのが一番良かったんですが。

ll Q, A, B;

void solve() {
	cin >> Q;
	while(Q--) {
		cin >> A >> B;
		if(A > B) swap(A, B);
		if(B - A <= 1) cout << 2 * A - 2 << "\n";
		else {
			ll C = ll(sqrt(A * B) - eps);
			if(C * (C + 1) >= A * B) cout << 2 * C - 2 << "\n";
			else cout << 2 * C - 1 << "\n";
		}
	}
}

2018-04-15

ARC095

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

こいついっつも同じような記事書いてるな。

C
はい。
D
C(a,b) < C(c,b)(a < c)です。
E
列と行の操作は入れ替えることができます。なので行を全探索した後、点対称にできるかどうか列を見ればよいです。
いえば簡単ですがめちゃくちゃバグりやすいです。罠がたくさんあって結局通せなかった…
グラフっぽく言い換えると少しはマシになるかも。
if文もなるべく使わずにしてコンパクトにしたのがこれです。

int H, W;
char S[12][12];
pi P[12];
bool visited[12];
bool same[12][12];

int creek(int v) {
	visited[v] = true;
	int res = 1;
	rep(i, 0, W) {
		if(!visited[i] && same[v][i]) {
			res += creek(i);
		}
	}
	return res;
}

bool ok() {
	// debug(vector<pi>(P, P + (H + 1) / 2));
	char T[12][12];
	int m1 = (H - 1) / 2, m2 = H / 2;
	rep(i, 0, (H + 1) / 2) {
		int a = P[i].fst, b = P[i].sec;
		rep(j, 0, W) {
			T[m1 - i][j] = S[a][j];
			T[m2 + i][j] = S[b][j];
		}
	}

	bool self[12];
	memset(same, 0, sizeof(same));
	memset(visited, 0, sizeof(visited));
	memset(self, 0, sizeof(self));

	rep(i, 0, W) {
		rep(j, 0, W) {
			bool ok = true;
			rep(k, 0, H) {
				if(T[H - k - 1][i] != T[k][j]) {
					ok = false;
					break;
				}
			}
			same[i][j] = ok;
		}
	}
	// rep(i, 0, W) {
	// 	rep(j, 0, W) {
	// 		cout << same[i][j];
	// 	}
	// 	cout << "\n";
	// }
	rep(i, 0, W) {
		if(same[i][i]) self[i] = true;
	}
	rep(i, 0, W) {
		if(self[i] || visited[i]) continue;
		if(creek(i) % 2) return false;
	}
	int odd = 0;
	rep(i, 0, W) {
		if(visited[i]) continue;
		odd += creek(i) % 2;
	}
	return odd <= 1;
}


bool used[12];

bool loop(int k) {
	if(k == (H + 1) / 2) {
		if(ok()) return true;
		else return false;
	}
	if(H % 2 == 1 && k == 0) {
		bool res = false;
		rep(i, 0, H) {
			P[k] = pi(i, i);
			used[i] = true;
			res |= loop(k + 1);
			used[i] = false;
		}
		return res;
	}
	bool res = false;
	int at = -1;
	rep(i, 0, H) {
		if(used[i]) continue;
		at = i;
		break;
	}
	used[at] = true;
	rep(i, 0, H) {
		if(used[i]) continue;
		used[i] = true;
		P[k] = pi(at, i);
		res |= loop(k + 1);
		used[i] = false;
	}
	used[at] = false;
	return res;
}

void solve() {
	cin >> H >> W;
	rep(i, 0, H) {
		rep(j, 0, W) {
			cin >> S[i][j];
		}
	}
	if(loop(0)) cout << "YES\n";
	else cout << "NO\n";
}

2018-04-13

CSAcademy: Round #76

つら。

ABC
はい。

D
あーもうめちゃくちゃだよ。
queueっぽいものが見えてから発想が転換できなかったのが敗因。
やっぱり実装力ないし、考察時に実装量を見積もるのも下手ですね。
面倒な問題たくさん解いて精進したほうが良さそう…

int N, M;
ll Y[MAX_N], X[MAX_N];
vector<ll> vec;
vector<pl> Q[MAX_N];
ll leftv[MAX_N], rightv[MAX_N];

int fd(ll v) {
	return lower_bound(all(vec), v) - vec.begin();
}

void pre(ll value[MAX_N]) {
	vec.clear();
	rep(i, 0, N) {
		vec.pb(X[i] - Y[i]);
		vec.pb(X[i] + Y[i]);
		vec.pb(X[i]);
	}
	sort(all(vec));
	vec.erase(unique(all(vec)), vec.end());
	M = sz(vec);
	rep(i, 0, M) {
		Q[i].clear();
	}
	rep(i, 0, N) {
		int at1 = fd(X[i]);
		int at2 = fd(X[i] - Y[i]);
		Q[at1].pb(pl(X[i] - Y[i], i));
		Q[at2].pb(pl(X[i] - Y[i], i));
	}
	set<pl> que;
	rep(i, 0, M - 1) {
		rep(j, 0, sz(Q[i])) {
			pl x = Q[i][j];
			if(que.find(x) != que.end()) {
				que.erase(x);
			}
			else {
				que.insert(x);
			}
		}
		if(que.empty()) {
			value[i] = linf;
		}
		else value[i] = (*que.begin()).fst;
	}
}

void solve() {
	cin >> N;
	rep(i, 0, N) {
		cin >> Y[i] >> X[i];
		X[i] *= -1;
	}
	pre(rightv);
	rep(i, 0, M - 1) {
		rightv[i] *= -1;
	}
	reverse(rightv, rightv + M);
	rep(i, 0, N) X[i] *= -1;
	pre(leftv);

	ll res = 0;
	// debug(vec);
	// debug(vl(leftv, leftv + M));
	// debug(vl(rightv, rightv + M));
	rep(i, 0, M - 1) {
		ll x1 = vec[i], x2 = vec[i + 1];
		ll l1 = x1 - leftv[i], l2 = x2 - leftv[i];
		ll r1 = rightv[i + 1] - x1, r2 = rightv[i + 1] - x2;
		// debug(i, x1, x2, l1, l2, r1, r2);
		ll X = x2 - x1;
		if(l1 < -linf / 2 && r1 < -linf / 2) continue;
		if(l1 >= r1) {
			ll l = l1 + X - 1;
			res += (l + l1) * X / 2;
		}
		else if(l2 <= r2) {
			ll r = r1 - (X - 1);
			res += (r + r1) * X / 2;
		}
		else {
			ll u = (r1 - l1) / 2;
			ll ul = r1 - u;
			ll ur = l1 + (u + 1);
			// debug(u, ul, ur);
			res += (u + 1) * (r1 + ul) / 2;
			res += (X - u - 1) * (l2 - 1 + ur) / 2;
		}
		// debug(res);
	}
	cout << res << "\n";
}

一応queueの解法でも通ったんで。でも上位陣の方々と比べると実装が遥かに複雑になってしまってるのが解ると思います。

E
mincutでしょって思ってたんですがmincutで通るらしいですね。Writerの想定解は違いますが。

2018-04-12

精進4/11

https://beta.atcoder.jp/contests/arc063/tasks/arc063_c 範囲求めて木の根から決めていけば良い。証明が少しあやふやで本番WAしたら自信無くして通せなさそう。
https://arc079.contest.atcoder.jp/tasks/arc079_d 丁寧丁寧丁寧にやったのでバグらせなかったけどうーん遅いなぁ。ループ内の値が2択になるのでDPすれば良い。
https://agc011.contest.atcoder.jp/tasks/agc011_c 二部グラフかどうか判定すれば良いんだけどそれをバグらせるという…

bool loop(int v, int k) {
	used[v] = true;
	bi[v] = k;
	bool ok = true;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(!used[n]) {
			if(!loop(n, 1 - k)) {
				ok = false; // don't return false
			}
		}
		else {
			if(bi[v] == bi[n]) ok = false;
		}
	}
	return ok;
}

ちゃんと全部の連結成分についてvisitしないといけません。途中でfalseをreturnするとバグります。

omochan's diary

ARC092E: Both Sides Merger