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

A - ABC333

入力: $\displaystyle{A}\ {B}\quad{\left({1}\le{A},{B}\le{3},{\left\lbrace{A},{B}\right\rbrace}\subset\mathbb{Z}\right)}$
出力: $\displaystyle{A}\times{B}\times{C}$ が奇数となるような $1$ 以上 $3$ 以下の整数 $C$ が存在するならば'Yes'を、そうでなければ'No'を出力

まず、Cの値を掛けるとき、Cが偶数だとしたら、 $\displaystyle{A}\times{B}\times{C}$ は偶数になってしまいますから、仮に出力が'Yes'となるならば、掛けるCの値は $1$ か $3$ です。
後はAとBの値に着目します。 $A$ と $B$ の値が与えられたとき、少なくとも1つの数が偶数ならば、この条件を満たすことはできません。よって、最終的には $A$ と $B$ の偶奇を判定すればよいとわかります。

if((A * B) % 2 == 0) writeln("No");
else writeln("Yes");

感想: ごく普通のA問題でした。

B - Shiritori

入力:
$N$
$W_1$
$W_2$
$\vdots$
$W_N$
制約は: $\displaystyle{\left({2}\le{N}\le{100}\right)}$ 、 $W_i$ は英小文字からなる長さ $1$ 以上 $10$ 以下の文字列
出力: 高橋くんのどの発言もしりとりのルールを守っていたなら'Yes'を、そうでなければ'No'を出力

しりとりで大事なルールは2つあります。

まだ発言されていない単語のみ使える
発言した単語の先頭の文字は直前の単語の末尾と一致する

この2つのどちらかが成り立っていなければ、しりとりは成立しません。

では、「まだ発言されていない単語のみ使える」をまず実装してみましょう。
今回の制約では $\displaystyle{2}\le{N}\le{100}$ ということもあって、わざわざ赤黒木を使う必要はありません。普通に配列を用意して、そこに発言の内容を格納しておき、発言の正当性を判定するときにはfor文で過去の発言とダブっていないか判定すればよいです。

string[] m;

// 判定するときのコード(SはW_i)
foreach(j; m) {
	if(S == j) {
		writeln("No");
		return;
	}
}

次に、「発言した単語の先頭の文字は直前の単語の末尾と一致する」を実装しましょう。
これは、毎回の入力ごとにその発言の末尾の文字を変数にもっておけばできます。

dchar last;

// 判定するときのコード(SはW_i)
if(last == S[0]) {
	last = S.back;
} else {
	writeln("No");
	return;
}

また、 $W_1$ のときは自由な発言ができるので、これも考慮して実装します。

auto N = readln.chomp.to!int;
dchar last;
string[] m;
foreach(i; 0..N) {
	auto S = readln.chomp;
	if(i==0) {
		m ~= S;
		last = S.back;
		continue;
	}
	if(last == S[0]) {
		last = S.back;
	} else {
		writeln("No");
		return;
	}
	foreach(j; m) {
		if(S == j) {
			writeln("No");
			return;
		}
	}
	m ~= S;
}
writeln("Yes");

感想: 自分語りになりますが、実はコンテスト前の金曜日に友達としりとりをしながら下校していて、その後電車に乗っているときにしりとりの妥当性を判定するプログラム(まさにこれっぽい!)を考えていたので、これが出題されたときには驚きました。

C - Skip

入力:
$\displaystyle{N}\ {X}$
$\displaystyle{x}_{{1}}\ {x}_{{2}}\ \ldots{x}_{{N}}$
出力: 全ての都市を $1$ 度以上訪れることのできる $D$ の最大値

可能な移動は、

座標 $y$ から座標 $y + D$ に移動する
座標 $y$ から座標 $y - D$ に移動する

とあり、しかも移動は何度でもできるので、

座標 $y$ から座標 $y + nD$ に移動する $\displaystyle{\left({n}\in\mathbb{Z}\right)}$

という操作ができるといえます。

また、座標 $X$ から移動を開始する、とありますが、利便性のためにすべての座標に関して $\displaystyle{\left|{x}_{{i}}-{X}\right|}$ で上書きします。
入力例で試してみましょう。
入力例1で上書きをしてみると、配列は $\displaystyle{\left[{2},{4},{8}\right]}$ となります。
入力例2では、 $\displaystyle{\left[{48},{24},{24}\right]}$ となり、
入力例3では、 $\displaystyle{\left[{999999999}\right]}$ となります。
ここで着目すべきことは、それぞれの出力が、これら配列の要素の最大公約数になっている、ということです。
実際、上書きした配列を元に考えてみると、正整数 $D$ の最大値を求める上で「可能なだけ一気に移動する」「全ての都市を1度以上訪れる」を成り立たせるためには、各要素の最大公約数を求めればいいことがわかります。
よって、コードは次のようになります。

auto ip = readln.split.to!(int[]), N = ip[0], X = ip[1];
auto x = readln.split.to!(int[]).map!(i => i - X).map!(i => i.abs);
auto c = x[0];
foreach(i; x[1..$]) {
	c = gcd(i, c);
}
c.writeln;

感想: 最近はすぐに「これはgcdを使いそうな問題だな」とかそういう気づきをすぐに得られるようになってきたので嬉しい。

D - Make Them Even

入力:
$\displaystyle{H}\ {W}$
$\displaystyle{a}_{{{11}}}\ {a}_{{{12}}}\ \ldots{a}_{{{1}{W}}}$
$\displaystyle{a}_{{{21}}}\ {a}_{{{22}}}\ \ldots{a}_{{{2}{W}}}$
$\displaystyle\vdots$
$\displaystyle{a}_{{{H}{1}}}\ {a}_{{{H}{2}}}\ \ldots{a}_{{{H}{W}}}$
制約は: 入力はすべて整数である、 $\displaystyle{\left({1}\le{H},{W}\le{500},{0}\le{a}_{{{i}{j}}}\le{9}\right)}$
出力: 偶数枚のコインが置かれたマスの数が最大となるような操作の列を次の形式で出力する
$N$
$\displaystyle{y}_{{1}}\ {x}_{{1}}\ {y}'_{{1}}\ {x}'_{{1}}$
$\displaystyle{y}_{{2}}\ {x}_{{2}}\ {y}'_{{2}}\ {x}'_{{2}}$
$\displaystyle\vdots$
$\displaystyle{y}_{{N}}\ {x}_{{N}}\ {y}'_{{N}}\ {x}'_{{N}}$
1行目の $N$ は操作の回数を表す $0$ 以上 $\displaystyle{H}\times{W}$ 以下の整数である。
$\displaystyle{i}+{1}\ {\left({1}\le{i}\le{N}\right)}$ 行目には $i$ 回目の操作を表す整数 $\displaystyle{y}_{{i}},{x}_{{i}},{y}'_{{i}},{x}'_{{i}}\ {\left({1}\le{y}_{{i}},{y}'_{{i}}\le{H},{1}\le{x}_{{i}},{x}'_{{i}}\le{W}\right)}$ を出力する。
これは、マス $\displaystyle{\left({y}_{{i}},{x}_{{i}}\right)}$ にあるコインのうち $1$ 枚を上下左右に隣接するマス $\displaystyle{\left({y}'_{{i}},{x}'_{{i}}\right)}$ に移動させる操作を表す。

まず、この操作はどのような順番でやっても結果には影響しません。入力例1で左上からfor文を回すように見ていき、もしもそのマスのコインの数が奇数ならば、上下左右に隣接したマスを見て、そのマスにコインを渡す、という操作をすればいいです。

また、出力のために、移動の情報は保持しておく必要があります。今回はContというTupleを用意しました。

alias Cont = Tuple!(int, "sx", int, "sy", int, "gx", int, "gy");
auto ip = readln.split.to!(int[]), H = ip[0], W = ip[1];
auto a = readMatrix!int(H, W); // オレオレライブラリにあります。下の提出URL参照
ulong cnt;
Cont[] conts;

auto dx = [1,0,-1,0], dy = [0,1,0,-1];
foreach(i; 0..H) {
	foreach(j; 0..W) {
		foreach(k; 0..4) {
			auto ry = i + dy[k], rx = j + dx[k];
			if(0 <= ry && ry < H && 0 <= rx && rx < W &&
				a[i][j]%2 != 0) {
				a[ry][rx]++;
				a[i][j]--;
				cnt++;
				conts ~= Cont(i+1, j+1, ry+1, rx+1);
				continue;
			}
		}
	}
}
cnt.writeln;
conts.each!(i => writefln("%d %d %d %d", i.sx, i.sy, i.gx, i.gy));

感想: このコードはどの出力例とも異なった出力をしますが、それでもACします(それはそう)。最近の激ムズD問題からやっと開放された、そんな気持ちでいっぱいでした。

A: Submission #3151081 - AtCoder Beginner Contest 109
B: Submission #3165977 - AtCoder Beginner Contest 109
B(コンテスト中の赤黒木バージョン): Submission #3152791 - AtCoder Beginner Contest 109
C: Submission #3165996 - AtCoder Beginner Contest 109
D: Submission #3157410 - AtCoder Beginner Contest 109