土曜21時は AtCoder！ ABC-only 回に参加したので解説を書いていきます。私はC完でした。

AtCoder Beginner Contest 112

問題リスト：

A - Programming Education

問題概要：N=1 なら Hello World を出力せよ。N=2 なら A+B を出力せよ。

解説：最初に1行目を読み込んでから条件分岐し、N=2 のときだけ2~3行目を読み込むようにします。

提出：

入力の個数が毎回異なる問題は珍しいですね。

B - Time Limit Exceeded

問題概要：自宅への経路がいくつか与えられる。i 番目の経路は t 時間かかり、コスト c かかる。経路を1つ選んで T 時間以内に自宅に到達できるか判定せよ。可能なら、最小のコストを求めよ。

解説：時間が T より大きい経路は無価値なので削除します。経路が1つも残らなければダメです。少なくとも1つ残ったら、残った経路のコストの最小値が答えです。

提出：

C - Pyramid

問題概要：中心座標 (X, Y) にピラミッドが1つある。座標 (x, y) におけるピラミッドの高さを後述の h(x, y) で表し、中心の高さを H = h(X, Y) とおく。座標 (x, y) と高さ h の組み合わせがいくつか与えられて、h = h(x, y) が成り立つ。このとき X, Y, H の組み合わせは1つに絞られた。X, Y, H を求めよ。

h(x, y) = H - |x - X| - |y - Y|

解説：X, Y の範囲 (0≤ X,Y ≤100) と「組み合わせが必ず特定できる」という条件が強力なので、これをうまく使えば意外と単純に解けます。

X, Y の範囲は狭いので全列挙できます。ピラミッドの中心座標 (X, Y) が決まったとき、与えられた条件 h(x, y) = h がすべて成り立つなら座標 (X, Y) は答えです。というのも、これが答えじゃなかったら組み合わせの特定ができないからです。

各 x, y, h について、h > 1 なら H - |x-X| - |y-Y| = h から H の値が1つに決まります。h = 0 のときは max の影響で、等号 = ではなく不等号 ≤ になります。これらの条件に合致する H の値がちょうど1つならOK。

コーディングの話になりますが、H としてありえる値の最大値と最小値を変数として持ち、条件ごとに更新するのがよいと思いました。(詳細は提出をご覧ください。) このときは H の最大値が 10^9 + 200 であることに注意です。

提出：

D - Partition

問題概要：整数 N, M が与えられる。長さ N の数列 a は正の整数からなり、和が M に等しい。a の要素の最大公約数の最大値を求めよ。

解説：N = 1 なら a = (M) しかなく、最大公約数は M です。N ≥ 2 を考えます。

仮に最大公約数の最大値を g とおくと、数列は a = (g, g, ..., g, k・g) の形にできます。最後の要素で帳尻を合わせるわけです。総和の式は

M
= (N-1) g + k g       (k≥1)
= (N+k-1) g           (k≥1)
= c g                 (c≥N, k=c-N+1)

と変形できます。こうすると答えは、M の約数 g の中で、c=M/d ≥ N が成り立つものの最大値です。

計算量について考えます。d が M の約数なら c = M/d も約数です。だから d≤√M の範囲で d を列挙して、同時に c = M/d も列挙すれば、すべての約数が列挙できます。M≤10^9 で √M 回のループは2秒もかからないので大丈夫です。

提出 (コンテスト終了後)：