ABC112参加記録 - notepad.exe

久々にABCで全完できた回でした。今回は練習もかねて初めてRubyで出ました。

A - Programming Education

1行だけ受け取って分岐して出力するだけの問題。

B - Time Limit Exceeded

時間T以内に帰れる方法でコストが最小なものを出力する問題。
入力[c, t]のペアでリストをもってT以下でフィルターをかけます。残ったリストの中にあるcの最小値を出力して、フィルターをかけた時にリストの長さが０であればその時はTLEを出力して完成。

提出コード

C - Pyramid

問題ページ

ピラミッドの高さと中心座標を求める問題。
中心座標は101*101個なので全探索できます。各候補座標に対して仮の高さを一度計算してその高さとしたときに与えられているすべての座標に矛盾がないか調べます。矛盾がないか調べるときに候補座標から十分に距離が遠いもの（本来は高さがマイナスになるもの）を都度除外してから矛盾のチェックをしないとWAになってしまうので、その点で苦労しました。

提出コード

D - Partition

問題ページ

$N$ 個の整数の和が $M$ になるときにそれらの整数の最大公約数の最大値を求める問題。 $a_i$ が $k$ の倍数であるとき $M$ も $k$ の倍数であるので、 $k$ の候補は $M$ の約数となります。
$k$ が $M$ の約数であるとき、 $N \leq \frac{M}{k}$ であれば問題の制約を満たせるので、約数を全探索すれば答えを見つけられます。約数の片方は必ず $\sqrt{M}$ 以下であるので1から $\sqrt{M}$ までループすれば十分間に合います。
答えの候補ですが、 $k$ が $M$ の約数であるとき $M/k$ も答えの候補になりうることがあるので、それを忘れるとWAになります。

提出コード