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.
ちなみに,各距離については以下の記事がわかりやすいので,どうぞ.

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)だと間に合わないので,少し計算を工夫しないといけない.
「約数 列挙 高速」とかで検索すると以下の記事が出てくるので,これを参考にすれば良い


最後は以下のコードで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)
感想(懺悔コーナー)
今回はC問題まで10分,D問題は15分くらいで書き終えました.
ただD問題の条件分岐でしょーもないミスをしていたので,そこで時間を取られました.
前回もそうでしたが,C問題やD問題で計算量(オーダ)が間に合わないって人は,とりあえず問題ケースを紙に書いてみるといいかもしれません.3,4個くらい問題ケースを考えてみて,そこから法則性を見つけると言ったことをすると,案外うまくいったりします.
とはいえ4完できたのはよかった.そろそろE問題も挑戦しようかな.
コメント