ARC096

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

C.
Cを全通り試します。

ll A, B, C, X, Y;

void solve() {
	cin >> A >> B >> C >> X >> Y;
	ll ans = linf;
	for(int c = 0; c <= max(X, Y) * 2; c += 2) {
		ll res = 0;
		res += C * c;
		res += A * max(X - c / 2, 0ll);
		res += B * max(Y - c / 2, 0ll);
		MIN(ans, res);
	}
	cout << ans << "\n";
}

D.
折り返す場所を全通り試します。

int N; ll C;
ll X[MAX_N], V[MAX_N];
ll L1[MAX_N], L2[MAX_N], R1[MAX_N], R2[MAX_N];

void solve() {
	cin >> N >> C;
	rep(i, 0, N) {
		cin >> X[i] >> V[i];
	}

	ll vs = 0, l1m = 0, l2m = 0;
	rep(i, 0, N) {
		vs += V[i];
		MAX(l1m, vs - X[i]);
		MAX(l2m, vs - 2 * X[i]);
		L1[i + 1] = l1m;
		L2[i + 1] = l2m;
	}
	vs = 0; ll r1m = 0, r2m = 0;
	rer(i, N, 0) {
		vs += V[i];
		MAX(r1m, vs - (C - X[i]));
		MAX(r2m, vs - 2 * (C - X[i]));
		R1[i] = r1m;
		R2[i] = r2m;
	}
	ll res = 0;
	rep(i, 0, N + 1) {
		MAX(res, L1[i] + R2[i]);
		MAX(res, L2[i] + R1[i]);
	}
	cout << res << "\n";
}

E.
うわー2byte差で落とすというね…。
包除原理します。
そして、dp[i][j]:=iケタ0or1にするときその中で1を含む数の個数がjの時の場合の数とします。
するとdp[i][j]は簡単な遷移で求められて、
あとはiケタ0or1にするときの場合の数は、
ΣC(N,i)*2^(2^(N-i))*2^((N-i)*j)*dp(i,j)となるのでO(N^2)で求められます。
しかし、注意すべきことはpow(2,pow(2,N-i,mod),mod)としないことです。正しくは
pow(2,pow(2,N-i,mod-1),mod)です。2^(p-1)=1だからですね。これさえ気づければ通っていた…。

ll dp[3010][3010];

void solve() {
	cin >> N >> mod;
	C_init(N + 10);

	dp[0][0] = 1;
	rep(i, 0, N) {
		rep(j, 0, N) {
			if(dp[i][j] == 0) continue;
			ADD(dp[i + 1][j + 1], dp[i][j]);
			ADD(dp[i + 1][j], dp[i][j] * (j + 1) % mod);
		}
	}
	ll ans = 0;
	rep(i, 0, N + 1) {
		ll dps = 0;
		ll pown = mod_pow(2, mod_pow(2, N - i, mod - 1), mod);
		ll pp = mod_pow(2, N - i, mod);
		ll d = 1;
		rep(j, 0, i + 1) {
			ll pows = pown * d % mod;
			MUL(d, pp);
			ADD(dps, dp[i][j] * pows % mod);
		}
		if(i % 2 == 0) {
			ADD(ans, (C(N, i) * dps % mod));
		}
		else {
			ADD(ans, mod - (C(N, i) * dps % mod));
		}
	}
	cout << ans << "\n";
}

mod-1の件があったにせよ、解法を詰めるのが遅すぎですね…場合の数の計算に自信が持てないのはなんとかしないと…。

AGC015E: Nuske vs Phantom Thnook

https://agc015.contest.atcoder.jp/tasks/agc015_c

この発想に至るまでが時間かかる気がする。

森の数=木の頂点数-木の辺数と言い換えられれば勝ちです。
あとは累積和適当に取れば通ります。

実装なんですがB,S,E,U,D,L,Rと7つも2010*2010の配列を作ってしまったことは反省するべきですね。
工夫すれば4つとかになるはずです。

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

int N, M, Q;
int B[2010][2010]; //blocks
int S[2010][2010]; //num of blocks;
int E[2010][2010]; //num of edge
int U[2010][2010], D[2010][2010], L[2010][2010], R[2010][2010];

void solve() {
	cin >> N >> M >> Q;
	rep(i, 0, N) {
		rep(j, 0, M) {
			char b; cin >> b;
			B[i][j] = (b == '1');
		}
	}
	rep(i, 0, N) {
		rep(j, 0, M) {
			S[i + 1][j + 1] += B[i][j] + S[i][j + 1] + S[i + 1][j] - S[i][j];
			int e = 0;
			rep(k, 0, 4) {
				int nx = i + dx[k], ny = j + dy[k];
				if(0 <= nx && nx < N && 0 <= ny && ny < M) {
					e += B[nx][ny] * B[i][j];
				}
			}
			E[i + 1][j + 1] += e + E[i][j + 1] + E[i + 1][j] - E[i][j];
		}
	}
	rep(i, 0, N) {
		rep(j, 0, M) {
			int u = 0, d = 0;
			if(i != 0) {
				u = (B[i][j] && B[i - 1][j]);
			}
			if(i != N - 1) {
				d = (B[i][j] && B[i + 1][j]);
			}
			U[i][j + 1] += U[i][j] + u;
			D[i][j + 1] += D[i][j] + d;
		}
	}
	rep(j, 0, M) {
		rep(i, 0, N) {
			int l = 0, r = 0;
			if(j != 0) {
				l = (B[i][j] && B[i][j - 1]);
			}
			if(j != M - 1) {
				r = (B[i][j] && B[i][j + 1]);
			}
			L[i + 1][j] += L[i][j] + l;
			R[i + 1][j] += R[i][j] + r;
		}
	}
	while(Q--) {
		int a, b, c, d; cin >> a >> b >> c >> d; a--; b--; c--; d--;
		int e = (E[c + 1][d + 1] - E[a][d + 1] - E[c + 1][b] + E[a][b]);
		e -= U[a][d + 1] - U[a][b];
		e -= D[c][d + 1] - D[c][b];
		e -= L[c + 1][b] - L[a][b];
		e -= R[c + 1][d] - R[a][d];
		cout << (S[c + 1][d + 1] - S[a][d + 1] - S[c + 1][b] + S[a][b]) - e / 2 << "\n";
	}
}

CODE THANKS FESTIVAL 2017,F: Limited Xor Subset

https://code-thanks-festival-2017-open.contest.atcoder.jp/tasks/code_thanks_festival_2017_f

こういうの最近Codeforcesでも見た。

とりあえずdpを書いてみます。
dp[i][a]:=要素iまで見た時xor sumがaになるものの場合の数。
これはO(NK)になってとても間に合いませんが、iを固定して良くみるとdp[i][a]は0またはある値しかとりえません。
なのである値ansとansを取るものの集合Sを管理すればO(KlogK+N)で求められます。

int N, K;
bool S[MAX_N * 2];

void solve() {
	cin >> N >> K;
	ll ans = 1;
	S[0] = 1;

	rep(i, 0, N) {
		ll a;
		cin >> a;
		if(!S[a]) {
			rep(i, 0, (1 << 17)) {
				if(S[i]) {
					S[i ^ a] = true;
				}
			}
		}
		else MUL(ans, 2);
	}
	if(S[K]) cout << ans << "\n";
	else cout << 0 << "\n";
		
}

ARC092E: Both Sides Merger

https://arc092.contest.atcoder.jp/tasks/arc092_c

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

結局、要素番号が偶数のやつから好きにとるか、奇数のやつから好きにとるかをすればいいとわかります。
構成法ですが、
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";
	}
}

AGC014C: Closed Rooms

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

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

ARC094D: Worst Case

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