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

お疲れ様でした！

A - Colorful Transceivers

入力: $a\;b\;c\;d\quad(a,b,c,d \in \mathbb{Z};\, 1 \le a, b, c, d \le 100)$

出力: 会話可能なら"Yes", そうでないなら"No"

直接的にaさんとcさんが会話可能…abs(a-c) ≦ d

間接的にaさんとcさんが会話可能…abs(a-b) ≦ d ∧ abs(b-c) ≦ d

この2つのどちらかが成り立つならば会話可能である。

writeln((abs(a - c <= d) || ( abs(a - b) <= d && abs(b - c) <= d) ? "Yes" : "No");

感想: はい

B - Exponential

入力: $X\quad(X \in \mathbb{Z};\, 1 \le X \le 1000)$

出力: X以下の最大のべき乗数( $1^3, 6^4, 2^9$ のような、指数が2以上の数)

まず、1000以下のべき乗数すべてを含むリストを生成する。

処理としては、「まず、与えられた数(2 ≦ a ≦ 1000)を2乗して1000以下ならその数をリストにぶち込み、3乗して1000以下ならその数をリストにぶち込み、4乗して1000以下なら…」というようにしていき、1000より大きな数になったら次の数に移る。これを2から1000までやると欲しいリストの生成が終わる。

int[] arr;
arr ~= 1; // 1をforeachのところに入れると無限ループします＼(^o^)／
foreach(i; 2..1001) {
	auto a = i;
	auto b = a; // aにaをかけていくので、bに最初のaの値を保存する
	auto k = 2; // 指数

	a *= a; // 二乗する
	while(a <= 1000) {
		arr ~= a; // 1000以下のべき乗数であるから、リストに追加する
		k++; // 指数を1増やす
		a = b^^k; // bのk乗をaに代入する
	}
}

[1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144, 169, 196, 216, 225, 243, 256, 289, 324, 343, 361, 400, 441, 484, 512, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1000] が欲しいリストです。
後は、Xがリストに入っていたなら、その値を出力し、そうでないならXをデクリメントしてもう一度チェックすれば良いです。

auto X = readln.chomp.to!int;
while(true) {
	if(arr.canFind(X)) {
		X.writeln;
		return;
	}
	X--;
}

感想: リストを生成するとき、a^^2を繰り返すだけの処理を最初記述し、それに気づかず1WA。かなしみ。

C - K-th Substring

入力: $s\quad(1 \le |s| \le 5000)$
$K\,\bf(1 \le K \le 5)$

s は異なるsubstringをK個以上持つ

部分点: $|s| \le 50$ なデータセットに正解したら200点/300点がもらえる

$K\,\bf(1 \le K \le 5)$ 。何度でも書きます。 $K\,\bf(1 \le K \le 5)$ 。この問題はかなり容易な思考で解くことができて、単純に考えうるsubstringたちをリストに入れてsortしてuniqueしてK番目を出力すればいい(""を考慮するとK番目)。赤黒木を使っておけば、最後にsort&uniqueする必要すらないんですが、これだけでは部分点しかもらえません。

auto s = readln.chomp, K = readln.chomp.to!int;
auto rbt = new RedBlackTree!string("");
foreach(i; 0..s.length) {
	foreach(j; i..s.length+1) {
		rbt.insert(s[i..j]);
	}
}
rbt.array[K].writeln;

本当に何度でも書きますけど $K\,\bf(1 \le K \le 5)$ 、ですからね。つまり5文字以下のsubstringだけ考えておけばいいので、さっきのコードのinsert部の前に

if(j - i > 5) continue;

を入れるだけでACできてしまいます。
感想: 気づかなかった自分がかなしい。

Cの 1 ≦ K ≦ 5 pic.twitter.com/605ij3SnFp
— public_yusuke (@public_yusuke) 2018年5月12日

D - Equals

入力: $N \, M\, (2 \le N \le 10^5; \, 1 \le M \le 10^5)$
$p_1 \, p_2 \, \ldots \, p_N$ ( $p$ は $1$ から $N$ までの整数を並び替えた順列)
$x_1 \, y_1$
$x_2 \, y_2$
$\vdots$
$x_M \, y_M$
なお、これらの制約は

$1 \le x_j, y_j \le N$
$x_j \neq y_j$
$i \neq j \Rightarrow \{x_i, y_i\} \neq \{x_j, y_j\}$
入力は全て整数

さて、これはUnion Findの典型的な問題らしいです（コンテスト中に解けなかった）。そのため、まずはUnion Findがどのようなものか見ていきましょう。

Union find(素集合データ構造) from AtCoder Inc.

www.slideshare.net

どうやら、 $a \sim b, b \sim c \Rightarrow a \sim c$ であることを取り扱えるデータ構造になっているようです。これを使えば、 $p_i = i$ まで持っていけるかどうかを判断できます。操作は何度でもして良いというところがポイントです。
gist.github.com
これを用意しておきます。
そして、 $x_i - 1$ と $y_i - 1$ をuniteします。これで、どれとどれが交換可能なのかが記録されます。
次に、 $p_i - 1$ と $i$ が交換可能かを判定し、可能ならカウントをインクリメントします。最後にカウントを出力すれば終わりです。

auto uf = new UnionFind!int(N);
foreach(_; 0..M) {
	auto ip2 = readln.split.to!(int[]);
	uf.unite(ip2[0]-1, ip2[1]-1);
}
int res;
foreach(i; 0..N) {
	if(uf.same(p[i]-1, i) res++;
}
res.writeln;

感想: Union Findを知らなかった。すっごく便利でびっくりした。

A: Submission #2494881 - AtCoder Beginner Contest 097
B: Submission #2497541 - AtCoder Beginner Contest 097
C: Submission #2504417 - AtCoder Beginner Contest 097
D: Submission #2505891 - AtCoder Beginner Contest 097

TeXを使ってみたり、はてな記法でSyntax Highlightをさせてみたりしました。すごく便利。便利は正義。