AtCoder Beginner Contest 100の解説 - private-yusuke’s diary

A - Happy Birthday!

入力: $A\, B\quad (A, B \in \mathbb{Z}; A + B \le 16)$
出力: 可能なら'Yay!', そうでなければ ':('

「隣り合う2切れのケーキを両方取る」というのは、AかBどちらかが8より大きければ発生することなので、

if(A > 8 || B > 8) {
	writeln(":(");
	return;
} else {
	writeln("Yay!");
}

でいいです。
感想: Aなのに問題文が少しむずかしい。

B - Ringo's Favorite Numbers

入力: $D\, N\quad (D = 0,1,2; N \in \mathbb{Z}; 1 \le N \le 100)$
出力: 100でちょうど $D$ 回割り切れるN番目に小さい整数

アアアアアアアアアアアアアアアアアアアーーーーー。
とりあえず、 $N=100$ のときとそうでないときで分けて考えよう。

if(D == 0) {
	if(N == 100) writeln(101);
	else writeln(N);
} else if(D == 1) {
	if(N == 100) writeln(100*101);
	else writeln(100*N);
} else {
	if(N == 100) writeln(100*100*101);
	else writeln(10000*N);
}

感想: ABCをやってきて一番WAしたB問題。制約を読もう。双子が悪魔に見える。

C - *3 or /2

入力:
$N\quad (N \in \mathbb{Z}; 1 \le N \le 10000)$
$a_1\, a_2\, a_3\, \cdots \, a_N\quad (a_i \in \mathbb{Z}; 1 \le a_i \le 1000000000)$
出力: 最大の操作回数

この問題、いかにして $a_i$ を2で割れるのか、というところだけに注目すれば解くことができます。
一回一回の操作で「2で割れる要素のうち1つを決めて除算をし、それ以外は3倍する」ことをすれば、最大の操作回数となるようにできます。3倍しても、2で割れる回数は変わりませんので。

ulong cnt;
foreach(i; a) {
	while(!(i & 1)) {
		i /= 2;
		cnt++;
	}
}
cnt.writeln;

感想: B問題より簡単に感じた。

D - Patisserie ABC

入力:
$N\, M\quad (N, M \in \mathbb{Z}; 1 \le N \le 1000; 0 \le M \le N)$
$x_1\, y_1\, z_1$
$x_2\, y_2\, z_2$
$\vdots\, \vdots$
$x_N\, y_N\, z_N\quad (-10000000000 \le x_i, y_i, z_i \le 10000000000 (1 \le i \le N))$
出力: $\displaystyle\text{max}{\left(\sum_{{i}}{\left|{C}_{{{i}_{{x}}}}\right|}+{\left|{C}_{{{i}_{{y}}}}\right|}+{\left|{C}_{{{i}_{{z}}}}\right|}\right)}$

sortして、 $x \lt y, x \gt y, y \lt z, y \gt z, z \lt x, z \gt x$ というふうに6通りに分けてやればいいんじゃね？！とか思ってたらWAしました。その後いろいろ試すもWAWAWAのWA。方針が間違っている。
ということで、コンテスト中には解けなかったのですが、よい考え方があるので、それを紹介します。

まず、仮に今回の制約で $a_i$ が0以上だったと仮定すると、明らかに、ケーキ毎に $x,y,z$ の総和をとり、その総和が大きい順からM個とってそれらの和をとればよいとわかります。
ケーキ $C_i$ の総和を $\displaystyle{S}_{{i}}={C}_{{{i}_{{x}}}}+{C}_{{{i}_{{y}}}}+{C}_{{{i}_{{z}}}}$ と表し、数列 $\displaystyle{\left\lbrace{S}_{{{C}_{{i}}}}\right\rbrace}$ を降順にソートしたとすると、和は $\displaystyle{\sum_{{{i}={1}}}^{{M}}}{S}_{{i}}$ で表されます。

次に、今回と同じ制約で、 $a_i$ が負の値もとることがあるとしましょう。
ところで、 $|a|$ は $a \ge 0$ のとき $a$ 、そうでないとき $-a$ であることはご存知かと思います。
したがって $\textrm{max}(|a|) = \textrm{max}(a, -a)$ といえます。
よって $\textrm{max}(|a|+|b|) = \textrm{max}(\textrm{max}(a, -a)+\textrm{max}(b, -b)) = \textrm{max}(a+b, a-b, -a+b, -a-b)$ ですね。
だから、 $\textrm{max}(|a|+|b|+|c|) = \textrm{max}(\textrm{max}(a, -a)+\textrm{max}(b, -b)+\textrm{max}(c, -c)) = \textrm{max}(\textrm{max}(a+b, a-b, -a+b, -a-b)+\textrm{max}(c, -c)) = \textrm{max}(a+b+c, a+b-c, a-b+c, a-b-c, -a+b+c, -a+b-c, -a-b+c, -a-b-c)$ です。
要は、絶対値まわりの処理が面倒なので、最初から各ケーキについて八通りのありうる値のとり方を計算しておけば楽なわけです。
この八通りについて、それぞれのパターンでケーキの価値の総和をとっておきます。そうすると、その8つのうちの最大値が求める値になります。

alias Cake = Tuple!(long, "x", long, "y", long, "z", long[], "score");

void main() {
	auto ip = readln.split.to!(long[]), N = ip[0], M = ip[1];
	Cake[] cakes;

	foreach(_; 0..N) {
		auto ip2 = readln.split.to!(long[]), a = ip2[0], b = ip2[1], c = ip2[2];
		long[] score;
		foreach(i; [1,-1]) foreach(j; [1,-1]) foreach(k; [1,-1]) {
			score ~= a*i+b*j+c*k;
		}
		cakes ~= Cake(a, b, c,score);
	}
	ulong res;
	foreach(i; 0..8) {
		cakes.sort!((a, b) => a.score[i] > b.score[i]);
		res = max(res, calc(cakes[0..M]));
	}
	res.writeln;
}

ulong calc(Cake[] cakes) {
	long beat, deli, popu;
	foreach(i; cakes) {
		beat += i.x;
		deli += i.y;
		popu += i.z;
	}
	return abs(beat)+abs(deli)+abs(popu);
}

感想: めっっっちゃ頑張ってsortでゴリ押ししようとしたけどダメだった。精進しなきゃいけないですね。

A: Submission #2674649 - AtCoder Beginner Contest 100
B: Submission #2682146 - AtCoder Beginner Contest 100
C: Submission #2677346 - AtCoder Beginner Contest 100
D: Submission #2689798 - AtCoder Beginner Contest 100