ABC112 参加記録&解説
AtCoder Beginner Contest 112 - AtCoder
結果は26分台全完で42位。まあまあ。
A - Programming Education
解法
分岐してそれぞれ処理。年商10億円突破楽しみにしています。
ACコード
B - Time Limit Exceeded
解法
求めたいコストを として、ループを回して であれば を で置き換える、を繰り返します。
の初期値としては、どの よりも大きい値を設定しておくとよいです。今回であれば1001や10000など。ここから一度も更新されなければ TLE
という判定ができます。
ACコード
C - Pyramid
解法
ちょっとだけ設定が複雑に見えますが、条件として与えられる点の数 、中心座標の候補が であることから全探索が可能です。中心座標を全探索します。
中心座標 を固定した時、その中心座標について「全ての条件を満たすようなピラミッドの高さ が存在するか?」を調べます。もしそのような が存在すれば、制約より解は1組だけしか存在しないため、見つかったものを出力して終了すればよいです。
条件となっている点 を順番に見ていきます。式を見やすくするため、 から中心までのマンハッタン距離を と表記します。問題文中の式は と書き換えられます。
中心を固定し、条件となっている点 を1つチェックし、その高さが となるために中心の高さ が満たすべき条件を考えます。その条件は、 のときとそうでないときで以下の図のように異なります。
- のとき
- このとき、これを満たす はただ1つであり、 より である。
- のとき
- このとき、これを満たす の候補は1つに絞られない。ただし、「 は 以下である」という条件は満たされる必要がある。 がこれより大きいと が正になり、すなわち も正になってしまうため。
これを全ての点について調べ、矛盾がなければそれを出力して終了です。矛盾があれば、次の中心座標を試します。これを繰り返せば、制約上どこかで解が見つかります。
ACコード
- (Ruby)Submission #3345654 - AtCoder Beginner Contest 112
- (C++)Submission #3373403 - AtCoder Beginner Contest 112
D - Partition
解法
の公約数を とします。このとき、以下の2つが成り立つことが必要です。
- は の約数である。
- であることから、 である。
逆にこれらを満たす時は、 個の を最低1個ずつ適当に に割り振れば、 は の公約数になります。
つまりこれら2つの条件を満たす中で最大の が、求めたい「最大公約数の最大値」です。
ということで、まず の約数を列挙しましょう。素因数分解を使う方法もありますが、1から までの整数で割ってみる方法が楽です。 もし で割り切れたら、その と が約数になるので、これを集めます。
約数が列挙できたら、 を満たすものだけを抜き出し、その中の最大値が答えです。制約 より は必ず条件を満たすので、解無しとなる可能性はないです。
ACコード
最後に
前回のABCオンリー回も、Dは約数絡みの問題でしたね。最近の流行り?