AtCoder Beginner Contest 180 備忘録

AtCoder Beginnrer Contest 180の備忘録です。

問題はこちら↓

AtCoder Beginner Contest 180 - AtCoder

今回はABCD4完でした。

・A問題:box

N 個のボールが入った箱から A 個取り出して B 個ボールを入れた時のボールの数を求める。

解答例(Python)
https://atcoder.jp/contests/abc180/submissions/17481045

・B問題:Various distances

N 次元空間内の点 x1 ~ xN が与えられるので原点からのマンハッタン距離、ユークリッド距離、チェビシェフ距離をそれぞれ求める。それぞれの距離の求め方は問題文にある通りなので、それぞれ計算して求めればよい。

解答例(Python)
https://atcoder.jp/contests/abc180/submissions/17480860

・C問題:Cream puff

N 個のシュークリームを平等に分けられる人数を求める。平等に分けられるという事は N を割り切れると言えるので、割り切れる数：約数を全て求めて出力すればよい。ただし、N≦10^12 なので全て試すとTLEとなるため高速で約数を列挙できるアルゴリズムを使う必要がある。i = 1 から N^0.5+1 までを全て試し割りをして割り切れたら i と N // i を記録していく事で O(√N) で約数を全て列挙することができる。

解答例(Python)
https://atcoder.jp/contests/abc180/submissions/17481336

・D問題:Takahashi Unevolved

ペットを飼っており、はじめその強さは X で経験値は 0 である。このペットに対して特訓をすることで強さを A 倍するか B を加えて経験値を 1 増やすことができる。強さが Y を超えないように強さをあげた時、経験値の最大値を求める。
出来るだけ多く特訓する方が経験値を最大化出来るので、A 倍するか B を加えるかどちらか強さの増加量の小さい方を選んで特訓する方がよい。ただし、愚直にシミュレーションしてしまうとTLEとなってしまうため、まずは A 倍する増加量が B を加える増加量より少ない間 A 倍し続け回数をカウントしておく。そして、B の増加量の方が少なくなった時点で残りの強さで何回 B を加えられるか計算してそれにカウントを加えたものが答えとなる。ただし、B を加える回数を計算した際に割り切れた場合強さが Y になっているため答えから 1 を引く必要があることに注意する。

解答例(Python)
https://atcoder.jp/contests/abc180/submissions/17481644