AtCoder Beginner Contest 112の解説

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