ABC112 参加記録＆解説

AtCoder Beginner Contest 112 - AtCoder

結果は26分台全完で42位。まあまあ。

f:id:betrue12:20181006213126p:plain

A - Programming Education

解法

分岐してそれぞれ処理。年商10億円突破楽しみにしています。

ACコード

（Ruby）Submission #3341720 - AtCoder Beginner Contest 112

B - Time Limit Exceeded

解法

求めたいコストを $c$ として、ループを回して $t_{i} \le T$ であれば $c$ を $\min(c, c_{i})$ で置き換える、を繰り返します。

$c$ の初期値としては、どの $c_{i}$ よりも大きい値を設定しておくとよいです。今回であれば1001や10000など。ここから一度も更新されなければ TLE という判定ができます。

ACコード

（Ruby）Submission #3342869 - AtCoder Beginner Contest 112

C - Pyramid

解法

ちょっとだけ設定が複雑に見えますが、条件として与えられる点の数 $N \le 100$ 、中心座標の候補が $0 \le C_{x}, C_{y} \le 100$ であることから全探索が可能です。中心座標を全探索します。

中心座標 $(C_{x}, C_{y})$ を固定した時、その中心座標について「全ての条件を満たすようなピラミッドの高さ $H$ が存在するか？」を調べます。もしそのような $H$ が存在すれば、制約より解は1組だけしか存在しないため、見つかったものを出力して終了すればよいです。

条件となっている点 $(x_{i}, y_{i})$ を順番に見ていきます。式を見やすくするため、 $(x_{i}, y_{i})$ から中心までのマンハッタン距離を $d_{i} = |C_{x} - x_{i}| + |C_{y} - y_{i}|$ と表記します。問題文中の式は $h_{i} = \max(H - d_{i}, 0)$ と書き換えられます。

中心を固定し、条件となっている点 $(x_{i}, y_{i})$ を1つチェックし、その高さが $h_{i}$ となるために中心の高さ $H$ が満たすべき条件を考えます。その条件は、 $h_{i} = 0$ のときとそうでないときで以下の図のように異なります。

f:id:betrue12:20181009200752p:plain

のとき
- このとき、これを満たす $H$ はただ1つであり、 $H - d_{i} = h_{i}$ より $H = d_{i} + h_{i}$ である。
のとき
- このとき、これを満たす $H$ の候補は1つに絞られない。ただし、「 $H$ は $d_{i}$ 以下である」という条件は満たされる必要がある。 $H$ がこれより大きいと $H - d_{i}$ が正になり、すなわち $h_{i}$ も正になってしまうため。