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

A - Entrance Examination

入力: $T\ X$
出力: 世界Aで実際に進んでいる時間(絶対誤差と相対誤差は $10^{-3}$ 以下である必要がある)
制約:
$1 \le T \le 100$
$1 \le X \le 100$

サンプルでエスパーしましょう(は?)

writefln("%.6f", T / X);

感想: エスパー

B - Polygon

入力:
$N$
$L_1\ L_2\ \ldots L_N$
出力: $N$ 角形が描けるなら'Yes'、そうでないなら'No'
制約:
$3 \le N \le 10$
$1 \le L_i \le 100$

問題文に定理が書かれているので、これを参考にして実装します。
具体的には、 $L_1, L_2, \ldots, L_N$ の総和をとり、一番長い辺の長さをそこから引いたものが、一番長い辺より真に大きいなら'Yes'、そうでないなら'No'と出力すればよいです。

if(L.reduce!max < L.sum - L.reduce!max) {
	writeln("Yes");
} else writeln("No");

感想: 定理が書かれてなかったら、めっちゃ点数上がってそうな気がした。

C - Streamline

入力:
$N\ M$
$X_1\ X_2\ \ldots\ X_M$
出力: 目的を達成するまでに移動を行う回数の最小値
制約:
$1 \le N \le 10^5$
$1 \le M \le 10^5$
$-10^5 \le X_i \le 10^5$
$\displaystyle\forall{i},{j}{\left({\left({i}\ne{j}\right)}\Rightarrow{\left({X}_{{i}}\ne{X}_{{j}}\right)}\right)}$

移動と言っているので、まずXをソートし、 $\displaystyle{i}{\left({0}\le{i}<{N}-{1}\right)}$ について $\displaystyle{X}_{{{i}+{1}}}-{X}_{{i}}$ な数列を考えたくなります。
$N \ge M$ のときは、 $N$ 個のコマによって $M$ 個の座標に訪れてしまうことが可能なので、この場合は0と出力すればよいです。

そうでないときは、1個以上のコマを移動する必要があります。

このとき、考えた数列について、大きい順から $N$ 要素の総和をとり、 $X$ の最大値と最小値の差からその総和を引けば、求める操作回数がわかります。

X.sort();
auto arr = new int[](M-1);
foreach(i; 0..M-1) arr[i] = abs(X[i+1] - X[i]);
//X.writeln;
//arr.writeln;
arr.sort!"a > b"();
long tmp;
if(N >= M) {
	writeln(0);
	return;
}
foreach(i; arr[0..N-1]) {
	tmp += i;
}
//tmp.writeln;
writeln(abs(X.reduce!max - X.reduce!min) - tmp);

感想: こういう問題、入力例から何となく解法を考えるのが大事な気がする

D - XXOR

入力:
$N\ K$
$A_1\ A_2\ \ldots\ A_N$
出力: $f$ の最大値
制約:
$1 \le N \le 10^5$
$0 \le K \le 10^{12}$
$0 \le A_i \le 10^{12}$

公式解説を読めばわかりますが、難しいので、1から理解した自分が書いてみます。

まず、これは質問ですが、 $30213$ と $40214$ はどちらが大きいでしょうか?
当然 $40214$ ですが、あなたはどのようにして大小を比較したでしょうか。
きっと、5桁目が $3 < 4$ だからすぐにわかったのだろうと思います。

では、 $(10101)_2$ と $(11010)_2$ は、どちらが大きいでしょうか?
これは $(11010)_2$ ですね。5桁目はどちらも $1$ なのでまだ大小が確定していませんが、4桁目を見ると $0 < 1$ より大小が確定します。公式解説では、このことを小難しい書きかたで表わしています。(雰囲気はこんな感じなはず)

この問題では、 $X \le K$ なる $X$ について $\displaystyle f{{\left({X}\right)}}=\sum_{{i}}{\left({X}\ \text{ xor }\ {A}_{{i}}\right)}$ としています。

$X \le K$ なので、この条件を満たしている状態を考えて、 $X$ の値を考えてみます。

$X = K$ のとき、特に何も考えず $f(K)$ を求めてみるとよいです。
そうでないとき、Kの2進法表記を考えてみます。
$X < K$ が確定するのは、XとKの二進法表記を上から見ていって、あるところで $0 < 1$ となるときです。
そのため、Kの二進法表記でそこが $1$ であるとき、そこをXの二進法表記で $0$ とすることを考えます。そこの桁を $i$ 桁目とします。
このとき、Xは $i$ より上の桁はKと等しく、 $i$ より下の桁は貪欲に選ぶことができます。
したがって、下のようなコードを書くことになります。なお、 $c_i$ は $i$ 桁目が $1$ である $A$ の要素の個数を表わしています。

auto c = new ulong[](64);
foreach(v; A) foreach(i; v.bitsSet) c[i]++;
ulong res;
if(K == 0) {
	writeln(A.sum);
	return;
}
// X < K のとき
foreach(i; 0..K.log2.ceil.to!ulong) {
	// Kの二進法表記でi桁目が1でなければcontinue(X < Kにしたいので)
	if(!(K & (1UL << i))) continue;
	ulong X = K;
	X &= ~(1UL << i); // Xのi桁目を0にする(i桁目でX < Kを確定させたいので)
	foreach(j; 0..i) {
		if(c[j] > N-c[j]) { // その桁を1にしてxorしたほうが都合がよいのか
			X &= ~(1UL << j);
		} else X |= (1UL << j);
	}
	ulong tmp;
	foreach(v; A) {
		tmp += v ^ X;
	}
	res = max(res, tmp);
}
ulong tmp;
foreach(v; A) { // X = K のとき
	tmp += v ^ K;
}
res = max(res, tmp);
res.writeln;

感想: これを理解したつもりでコードを書くと、X = Kの場合を忘れていてWAを連発したりした。
本番では嘘解法(上から貪欲に決めるとAC)が通るようになっていたのだが、シフト演算に慣れていないせいで1 << aと書いてしまい、1UL << aと書けばパフォ1600だったのに俺は何をオーバーフローさせてんだ…いやでもこれ嘘だしなあ…という微妙な気持ちになった。(どちらかというとレート上昇を逃したのが悔しい)
後日、しっかり本当の解法を理解しようと努めることによって、桁を上から見ることについて少しはわかったのではないかと思う(桁DPで解く方法についても今後考えたい)

A: Submission #4152674 - AtCoder Beginner Contest 117
B: Submission #4153387 - AtCoder Beginner Contest 117
C: Submission #4158140 - AtCoder Beginner Contest 117
D: Submission #4184409 - AtCoder Beginner Contest 117
D(別解法): Submission #4183962 - AtCoder Beginner Contest 117
D(嘘解法): Submission #4167642 - AtCoder Beginner Contest 117