ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

ABC112 参加記録&解説

AtCoder Beginner Contest 112 - AtCoder

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

f:id:betrue12:20181006213126p:plain

A - Programming Education

A - Programming Education

解法

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

ACコード

B - Time Limit Exceeded

B - Time Limit Exceeded

解法

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

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

ACコード

C - Pyramid

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

これを全ての点について調べ、矛盾がなければそれを出力して終了です。矛盾があれば、次の中心座標を試します。これを繰り返せば、制約上どこかで解が見つかります。

ACコード

D - Partition

D - Partition

解法

 a_{1}, ..., a_{N} の公約数を  d とします。このとき、以下の2つが成り立つことが必要です。

  •  d a_{1} + ... + a_{N} = M の約数である。
  •  a_{i} \ge d であることから、  M = a_{1} + ... + a_{N} \ge Nd である。

逆にこれらを満たす時は、 \frac{M}{d} 個の  d を最低1個ずつ適当に  a_{i} に割り振れば、  d a_{1}, ..., a_{N} の公約数になります。

つまりこれら2つの条件を満たす中で最大の  d が、求めたい「最大公約数の最大値」です。

ということで、まず  M の約数を列挙しましょう。素因数分解を使う方法もありますが、1から  \lfloor\sqrt{M}\rfloor までの整数で割ってみる方法が楽です。 もし  i で割り切れたら、その  i \frac{M}{i} が約数になるので、これを集めます。

約数が列挙できたら、  Nd \le M を満たすものだけを抜き出し、その中の最大値が答えです。制約  N \le M より  d = 1 は必ず条件を満たすので、解無しとなる可能性はないです。

ACコード

最後に

前回のABCオンリー回も、Dは約数絡みの問題でしたね。最近の流行り?