AtCoder Beginner Contest 098の解説

A - Add Sub Mul

入力:  A\;B\quad(A,B \in \mathbb{Z};\, -1000 \le A, B \le 1000)
出力:  A+B,  A-B,  A\times Bの中で最大の値

writeln(max(A+B, A-B, A*B));

感想: はい

B - Cut and Count

入力:
 N\quad (2 \le N \le 100)
 S\quad (|S| = N)
出力: Sを一箇所で切断してできた2つの文字列 X, Yのどちらにも含まれている文字の種類数の最大値

「どちらにも含まれている」 -> "setIntersection"

ulong res;
foreach(i; 0..N) {
	auto X = S.dup; // sort()が作用してしまうのでコピーする
	auto a = X[0..i].sort().uniq.array; // 部分列に含まれる文字を取得
	auto b = X[i..$].sort().uniq.array; // (sortで揃えてuniqで隣り合う同要素を一つにする)
	int tmp = setIntersection(a,  b).array.length.to!int; // 文字の種類数
	res = max(res, tmp);
}
writeln(res);

感想: B問題にしては難しい気がする

C - Attention

入力:
 N\quad (2 \le N \le 3\times 10^5)
 S\quad (|S| = N)  S_iは 'E' または 'W'
出力: 向く方向を変える人数の最小値

各地点でリーダーを決めて、向く方向を変える人数をforループで数え上げるとTLEします。(サンプルだけ通ってsubtaskは通らない)
ここで、累積和を使います。用意すべき配列は、「i番目含め左から今までのWの個数の配列」です。

auto A = new int[](N);

// i番目含め左から今までのWの個数
A[0] = S[0] == 'W';
foreach(i; 1..N) A[i] = S[i] == 'W' ? A[i-1]+1 : A[i-1];

// i番目含め左から今までのEの個数
// WでないならEがそこにあるため、余事象の考え方が使えます。
auto C = (int n) {
	return n+1 - A[n];
};

foreach(i; 0..N) {
	ulong tmp;
	tmp += C(N-1) - C(i); // リーダーより右でEを向いている人の数
	tmp += i < 1 ? 0 : A[i-1]; // リーダーより左でWを向いている人の数
	res = min(res, tmp);
}
res.writeln;

先に累積和の配列を生成することで、このようなTLEを解消できます。

感想: 累積和全然やってないオタクだったのでコンテスト中に解けず。頭が回らなかった。

D - Xor Sum 2

入力:
 N\quad (1 \le N \le 2 \times 10^5)
 A_1 \, A_2 \, \ldots \, A_N\quad (A_i \in \mathbb{Z};\, 0 \le A_i \le 2^20)
出力:  A_l \, {\rm xor} \, A_{l+1} \, {\rm xor} \, \ldots {\rm xor} \, A_r = A_l + A_{l+1} + \ldots + A_r を満たす整数  l, r\, (1 \le l \le r \le N) の組の個数

しゃくとり法を使います。

foreach(l; 0..N) {
	// 尺取り法(l: left, r: right)
	// 題意(和とxorが等しい)を満たすなら
	while(r < N && (total + A[r] == (xor_sum ^ A[r]))) {
		total += A[r];
		xor_sum ^= A[r];
		r += 1; // ひとつ右に進める
	}
	res += r - l; // 区間長をたす(一回前までうまくいっていたので)

	// 区間の左端をひとつ右に進めるので、そのぶん(A[i])をなかったことにする
	// 逆演算すればよい。足し算の反対は引き算、xorの反対はxor
	total -= A[l];
	xor_sum ^= A[l];
}
writeln(res);

ある区間 A = [l, r)で条件を満たしているなら、 \forall a \forall b([a, b))\, (a, b \in A)でも条件を満たします。

感想: コンテスト中にたどり着かなかった。しゃくとり法やったことなかった。知らない・理解していないアルゴリズムとか考え方はまだまだたくさんあるので、精進は大事だなあって思った。

A: Submission #2561733 - AtCoder Beginner Contest 098
B: Submission #2564967 - AtCoder Beginner Contest 098
C: Submission #2604714 - AtCoder Beginner Contest 098
D: Submission #2573473 - AtCoder Beginner Contest 098