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

A - Programming Education

入力:
$1$
または
$2$
$A$
$B$
制約:
$N$ は1または2
$\displaystyle{A}\in\mathbb{Z};{1}\le{A}\le{9}$
$\displaystyle{B}\in\mathbb{Z};{1}\le{B}\le{9}$

出力: $N = 1$ のとき、'Hello World'と出力し、 $N = 2$ のとき、 $A + B$ を出力する。

今回は珍しいことに処理の分岐をする必要がありました。

N = readln.chomp.to!int;
if(N == 1) {
	writeln("Hello World");
} else {
	auto A = readln.chomp.to!int, B = readln.chomp.to!int;
	writeln(A + B);
}

感想: やるだけです。問題文がヤバいなあって感じ。

B - Time Limit Exceeded

入力:
$N\ T$
$c_1\ t_1$
$c_2\ t_2$
$\vdots$
$c_N\ t_N$
出力: コストが最小となる経路のコストを出力
制約:
$\displaystyle{N},{T},{c}_{{i}},{t}_{{i}}\in\mathbb{Z}$
$\displaystyle{1}\le{N}\le{100}$
$\displaystyle{1}\le{T}\le{1000}$
$\displaystyle{1}\le{c}_{{i}}\le{1000}$
$\displaystyle{1}\le{t}_{{i}}\le{1000}$
$\displaystyle{i}\ne{j}\Rightarrow{\left({c}_{{i}},{t}_{{i}}\right)}\ne{\left({c}_{{j}},{t}_{{j}}\right)}$

まず、 $T$ 以内に帰宅できない経路については弾きます。この条件を満たすコストの中での最小値を出力すればよいです。

int[] times;
foreach(i; 0..N) {
	/* 入力を読み込む。 */
	if(t <= T) times ~= c;
}
if(times.length != 0) writeln(times.reduce!min);
else writeln("TLE");

感想: 'TLE'のときのケースについて処理するのを忘れてしまうと
'WA'するので気をつけましょう。

C - Pyramid

入力:
$\displaystyle{N}$
$\displaystyle{x}_{{1}}\ {y}_{{1}}\ {h}_{{1}}$
$\displaystyle{x}_{{2}}\ {y}_{{2}}\ {h}_{{2}}$
$\displaystyle{x}_{{3}}\ {y}_{{3}}\ {h}_{{3}}$
$\displaystyle\vdots$
$\displaystyle{x}_{{N}}\ {y}_{{N}}\ {h}_{{N}}$

出力: $\displaystyle{C}_{{X}}\ {C}_{{Y}}\ {H}$

制約:
$\displaystyle{N},{x}_{{i}},{y}_{{i}},{h}_{{i}}\in\mathbb{Z}$
$\displaystyle{1}\le{N}\le{100}$
$\displaystyle{0}\le{x}_{{i}},{y}_{{i}}\le{100}$
$\displaystyle{0}\le{h}_{{i}}\le{10}^{9}$
$\displaystyle{i}\ne{j}\Rightarrow{\left({x}_{{i}},{y}_{{i}}\right)}\ne{\left({x}_{{j}},{y}_{{j}}\right)}$
$\displaystyle{C}_{{X}}\ {C}_{{Y}}\ {H}$ はちょうど1つに特定される

このような制約や条件が複雑な問題は、全探索をすることを考えます。
具体的には、今回は $\displaystyle{C}_{{X}}\ {C}_{{Y}}\ {H}$ の3つの値について全探索すればよいです。

foreach(posY; 0..101)
{
	foreach(posX; 0..101)
	{
		foreach(H; h.reduce!min..h.reduce!min+201)
		{
			bool flag = true;
			foreach(i; 0..N)
			{
				auto dist = max(0, H-abs(posX-x[i])-abs(posY-y[i]));
				if(dist != h[i])
				{
					flag = false;
					break;
				}
			}
			if(flag)
			{
				writefln("%d %d %d", posX, posY, H);
				return;
			}
		}
	}
}

感想: コンテスト中に解けなかった。「基本は全探索」この言葉を忘れてはいけない。あと、実行時間の制約も見ておくべきだと思った。

D - Partition

入力: $N\ M$
出力: $\displaystyle \gcd{{\left({a}\right)}}$ の最大値
制約:
$\displaystyle{N},{M}\in\mathbb{Z}$
$\displaystyle{1}\le{N}\le{10}^{5}$
$\displaystyle{N}\le{M}\le{10}^{9}$

サンプルにない例を見てみましょう。
$\displaystyle{N}={2},{M}={195}$ としてみます。この場合、出力は65になります。

195を素因数分解してみると、 $\displaystyle{195}={3}\cdot{5}\cdot{13}$ となります。
ここで注目したいのは、 $\displaystyle{5}\cdot{13}={65}$ が出力になっていることです。
では $3$ はどこにいったのか、と考えてみると、実は $\displaystyle{\left({a}_{{1}},{a}_{{2}}\right)}={\left({65},{130}\right)},{\left({130},{65}\right)}$ の場合が考えられることから、それぞれ $65$ を1つか2つずつ取っていることがわかります。
よって、「N以上でMを割りきれる最小の数」を探して、その値でMを割った値を出力すればいい、という方針が立ちます。なお、この値を $k$ とすると、探索すべきkの範囲は $\displaystyle{N}\le{k}\le\frac{M}{{2}}$ で十分です。

ただし、このやり方だと、テストケースにはないものの、一番計算に時間がかかるような「Nが2でMが $10^9$ 以下の素数」などのパターンだと多分間に合わなくなってしまいます。
ジャッジ側が少しだけ情けを与えてくれたためにACすることができました。

int k = N;
while(k <= M / 2) {
	auto r = M % k;
	if(r == 0) {
		writeln(M / k);
		return;
	}
	k++;
}
writeln(1);

感想: 割と単純明快なコードでACすることができました。
C問題より簡単に感じましたが、chokudaiさん曰く「それはAtCoderで遊んでいる層が数学に強い傾向にあるためであって、一般的にはC < Dという難易度になっているのは間違いないはず」とのことでした。
確かに全探索することを思いつけば簡単だったのかも…?

A: Submission #3341345 - AtCoder Beginner Contest 112
B: Submission #3342324 - AtCoder Beginner Contest 112
C: Submission #3357731 - AtCoder Beginner Contest 112
D: Submission #3348620 - AtCoder Beginner Contest 112