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

A - Duplex Printing

入力: $N$
出力: 必要な最小の紙の枚数
制約:

$N$ は整数
$1 \le N \le 100$

$\displaystyle{\left\lceil{\frac{N}{{2}}}\right\rceil}$ ですね。（2で割って切り上げ）

ceil(N.to!float / 2).writeln;

ちなみに、

writeln((N+1)/2)

でもいけると思います。
感想: 切り上げ時は浮動小数点数に変換させることを忘れないように。

B - Bingo

入力:
$\displaystyle{A}_{{{1},{1}}}\ {A}_{{{1},{2}}}\ {A}_{{{1},{3}}}$
$\displaystyle{A}_{{{2},{1}}}\ {A}_{{{2},{2}}}\ {A}_{{{2},{3}}}$
$\displaystyle{A}_{{{3},{1}}}\ {A}_{{{3},{2}}}\ {A}_{{{3},{3}}}$
$N$
$b_1$
$\vdots$
$b_N$
出力: ビンゴが達成されているならば 'Yes' を、そうでないならば 'No'
制約:

入力は全て整数
$\displaystyle{1}\le{A}_{{{i},{j}}}\le{100}$
$\displaystyle{A}_{{{i}_{{i}},{j}_{{1}}}}\ne{A}_{{{i}_{{2}},{j}_{{2}}}}\ {\left({\left({i}_{{1}},{j}_{{1}}\right)}\ne{\left({i}_{{2}},{j}_{{2}}\right)}\right)}$
$1 \le N \le 10$
$1 \le b_i \le 100$
$\displaystyle{b}_{{i}}\ne{b}_{{j}}\ {\left({i}\ne{j}\right)}$

ビンゴカードの数字の羅列を一次元配列に入れることを考えてみました。

0 1 2
3 4 5
6 7 8

のように添字を対応させました。
すると、ビンゴであるためには縦、横または斜めの列に穴が開いていればよく、これらの列は
[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]
で表すことができます。

auto arr2 = new bool[](9);
foreach(i; 0..N) {
	auto b = ri;
	foreach(j; 0..9) {
		if(A[j] == b) arr2[j] = true;
	}
}
auto arr = [
	[0,1,2],
	[3,4,5],
	[6,7,8],
	[0,3,6],
	[1,4,7],
	[2,5,8],
	[0,4,8],
	[2,4,6]
];
foreach(v; arr) {
	bool flag = true;
	foreach(k; v) {
		if(!arr2[k]) flag = false;
	}
	if(flag) {
		writeln("Yes");
		return;
	}
}
writeln("No");

感想: 実装をちょっとだけ頑張る問題で、ABC向きだったと思います。

C - Guess The Number

入力:
$N\ M$
$s_1\ c_1$
$\vdots$
$s_M\ c_M$
出力: 条件を満たす最小の整数が存在するならそれを、存在しないならば '-1'
制約:

入力は全て整数
$1 \le N \le 3$
$0 \le M \le 5$
$1 \le s_i \le N$
$0 \le c_i \le 9$

制約より、全探索で十分高速に解けます。したがって、0から999までの整数を下から検証していって、条件を満たす整数があればそれを出力して終了するプログラムを作ることを考えます。なければ '-1' を出力です。
0から999までの検証する整数を文字列に変換したものを $S$ とします。
一つ目の条件「十進表記で丁度 $N$ 桁である。」は、文字列 $S$ の長さから簡単に確認できます。
二つ目の条件「左から数えて $s_i$ 桁目は $c_i$ である。 $(i = 1, 2, \dots, M)$ 」は、文字列 $S$ の $s_i - 1$ 番目の文字が $c_i$ であるか調べればよいです。(0-indexed)

int[] S, C;
foreach(i; 0..M) {
	auto ip2 = readAs!(int[]), s = ip2[0], c = ip2[1];
	S ~= s;
	C ~= c;
}
foreach(i; 0..(10 ^^ (N))) {
	auto st = i.to!string;
	if(st.length != N) continue; // 一つ目の条件
	bool flag = true;
	foreach(k; 0..M) { // 二つ目の条件
		if(!(st[S[k]-1] - '0' == C[k])) flag = false;
	}
	if(flag) {
		writeln(i);
		return;
	}
}
writeln(-1);

感想: 全探索するだけですが、苦戦していた方が多かったようでした。制約をよく読んで簡単に考えられると良かったかもしれません。

D - Friend Suggestions

入力:
$N\ M\ K$
$A_1\ B_1$
$\vdots$
$A_M\ B_M$
$C_1\ D_1$
$\vdots$
$C_K\ D_K$
出力: 人 $i = 1, 2, \dots, N$ にとっての友達候補の数
制約:

入力は全て整数
$2 \le N \le 10^5$
$0 \le M \le 10^5$
$0 \le K \le 10^5$
$1 \le A_i, B_i \le N$
$A_i \ne B_i$
$1 \le C_i, D_i \le N$
$C_i \ne D_i$
友達関係かつブロック関係であることはない
一つの友達関係、またはブロック関係が重複して入力に表れることはない

「友達候補」とは、

自分自身は友達候補にならない
ブロック関係にある人同士ではない
友達関係にある人同士ではない
人 $A$ さんと $B$ さんがいたとき、 $A$ さんの友達の友達の……の友達が $B$ さんである

……と定義されます。（厳密な定義は問題文を読んでください）

入力例3をノートに描いてみると、人 $i$ にとっての友達候補の数は、

(人 i が友達経由で繋がっている人たちの数)
- (人 i が友達経由で繋がっている人たちの中で友達関係にある人の数)
- (人 i が友達経由で繋がっている人たちの中でブロック関係にある人の数)
- (自分自身の数(つまり 1))

で求められることがわかります。人を頂点、友達関係を辺とした無向グラフを考えると、これは

(頂点 i の連結成分の大きさ)
- (頂点 i の次数)
- (頂点 i と同じ連結成分に含まれている頂点 j で、頂点 i と頂点 j がブロック関係にあるような j の数)
- 1

と言い換えられます。「連結成分の大きさ」や、「同じ連結成分に含まれているか」を高速に判定するため、UnionFindを用いました。

auto friendUF = new UnionFind!int(N);
int[][] farr = new int[][](N, 0); // farr[i]: 頂点 i と友達関係にある頂点の配列
int[][] barr = new int[][](N, 0); // barr[i]: 頂点 i とブロック関係にある頂点の配列

foreach(i; 0..M) {
	auto ip2 = readAs!(int[]), A = ip2[0], B = ip2[1];
	friendUF.unite(A-1, B-1);
	farr[A-1] ~= B-1;
	farr[B-1] ~= A-1;
}
foreach(i; 0..K) {
	auto ip3 = readAs!(int[]), C = ip3[0], D = ip3[1];
	barr[C-1] ~= D-1;
	barr[D-1] ~= C-1;
}

ulong[] res;
foreach(i; 0..N) {
	auto n = farr[i].length;
	auto tmp = friendUF.size(i) - n;
	foreach(v; barr[i]) {
		if(friendUF.same(v, i)) tmp--;
	}
	res ~= (tmp - 1);
}
writefln("%(%d %)", res);

感想: UnionFind の良い練習問題では？と思いました。

A: Submission #10426662 - AtCoder Beginner Contest 157
B: Submission #10431636 - AtCoder Beginner Contest 157
C: Submission #10435013 - AtCoder Beginner Contest 157
D: Submission #10448653 - AtCoder Beginner Contest 157