【AtCoder】ABC180の参加記録．~感想と解法~【python】

ABC179に引き続き，連続での参加となります．

かなり久しぶりのABC開催に加えて，自分も1ヶ月くらい競プロから離れていたので，前回よりも多く解けるか不安でした．

それでもなんとか4完しました．

A~D問題を見た限り，いつものABCより難易度低めだったのかな(E,Fは知らない)．

A問題：box

N個のボールが入った箱からA個取り出してB個入れて，箱に何個入ってますか．という問題．

問題文そのままに書けばAC．

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

n,a,b=input2()
print(n-a+b)

B問題：Various distances

マンハッタン距離，ユークリッド距離，チェビシェフ距離をそれぞれ求めて，それを出力．

特に制約が厳しいわけでもないので，そのまま計算すればAC．

ちなみに，各距離については以下の記事がわかりやすいので，どうぞ．

ちょっと距離についてまとめてみた。 - Qiita

「ロマンティック数学ナイトボーイズ」の発表をするにあたって、距離空間の記事を書こうと思います。距離ってなによ？GLSLやレイマーチングなど、3D数学をされていると、図形の形を表す数式の方程式だと思います。だた、今回は、数...

import math

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

# マンハッタン距離
def manh(X):
	ans=0
	for x in X:
		ans+=abs(x)
	return ans

# ユークリッド距離
def euc(X):
	ans=0
	for x in X:
		ans+=x**2
	return math.sqrt(ans)

# チェビシェフ距離
def cheb(X):
	ans=0
	for x in X:
		ans=max(ans,abs(x))
	return ans

n=int(input())
x=input_array()

print(manh(x))
print(euc(x))
print(cheb(x))

C問題：Cream puff

N個のシュークリームがあって，それを均等に分けられる人数を全て列挙せよという問題．

もし6個のシュークリームがある時は6人，3人，2人，1人だと均等に分けられるよねって話．

注意したいのが，計算量．0(N)だと間に合わないので，少し計算を工夫しないといけない．

「約数　列挙　高速」とかで検索すると以下の記事が出てくるので，これを参考にすれば良い

約数を高速で列挙するコード(Python) - Qiita

約数を高速で列挙するコードです(計算量$O(\sqrt{N})$)問題の制約が^9$でも間に合います。ほぼ自分用のメモとして投稿(@yucatioさんの指摘を受け，小さい約数のリストと大きい約数のリストを最後に結合する方法...

最後は以下のコードでAC．

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n=int(input())
ans=make_divisors(n)
for a in ans:
	print(a)

D問題：Takahashi Unevolved

「chokudaiさん，ペットだったんだ．．．」

それはさておき．

強さXの高橋くんが居て，「① 強さがA倍になるジム」と「 ②強さがB増えるジム」があり，高橋くんを強さY未満になるまでに何回ジムに通わすことができるか(どれだけ経験値をガメれるか)という問題．「どれだけジムに通わせられるか」ということから，ジムを選択する際に「強さの増加数が低いジムを選択する」ことが重要(ここでの増加数とは，ジムi-1回目とi回目のときの強さの差を示す)．

入力例として，「5 100 2 24」を考える．①を選択すると強さxは「x=5*2(=10)」．②を選択すると「x=5+24(=29)」．この時，①を選択した方がxの増加率が低いため，①のジムを選択．これをxがy以上になるまで続ける．ただし，制約が10**18ということで，普通にやると間に合わない．

ここで，数字が大きくなるにつれて，掛け算よりも足し算の方が増加数は低くなるんじゃないかということに気付く．まずは①のジムに通い始め，強さの増加数が②よりも大きくなった場合，①に通うのをやめて②に通い続ける．

結果，以下のコードでAC．

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())
  
x,y,a,b=input2()
count=0
while (x*a-x)<=b:
	if x*a>=y:
		break
	x=x*a
	count+=1

tmp=(y-x)//b
if (x+b*tmp)>=y:
	tmp-=1
print(count+tmp)