超初心者が適当に選んだC問題を解きまくってみた【Python】

解き方を忘れないためにまとめてるだけなのでコードはめちゃくちゃ不細工です、ここもっと良くできるよって場所あったら教えていただけるとありがたいです！！

116 Grand Garden

practice.py

def judge(hlist):
    if len(hlist)==0:
        return 0
    mini = min(hlist)
    idx = hlist.index(mini)
    hlist = [h-mini for h in hlist]
    return mini + judge(hlist[:idx]) + judge(hlist[idx+1:])

n = int(input())
hlist = list(map(int, input().split()))
print(judge(hlist))

この問題で必要な考え方は、最初に一番背の低い花の必要な数だけ全体に水を与えて、その後その花のindex番号でリストを分割していくことです。そして分割した後のリストの中での、一番小さい花の高さを見つけて同じことをやっていくだけです。　そのために再起関数を使っていきました！
再起関数について

117 Streamline

practice.py

n,m = map(int, input().split())
mlist = list(map(int, input().split()))
cnt = max(mlist) - min(mlist)
if n >= m:
    print(0)
    exit()
mlist.sort()
tmp = []
for i in range(m-1):
    tmp.append(abs(mlist[i+1]-mlist[i]))
tmp.sort()
print(cnt-sum(tmp[m-n:]))

この問題で必要な考え方は、最小の位置にある駒と最大の位置にある駒の距離から、できるだけ大きい隣り合った駒同士の距離を初期位置として選べる駒の数だけ引いていくことです。　まず、全ての駒の位置などの与えられた情報を受け取っていきましょう。その後、nの数がmの数より大きいならば、駒を一つも動かす必要がないので0を出力して、処理を終わらせてしまいしょう。もし、上のケースに引っかからなかった時にはそれぞれの隣り合った駒の距離をtmpリストに格納して行きましょう(隣合わせるためにsortを使っていく)　得た距離にもできるだけ大きい距離を取り除きたいので、sortを使っていきましょう。　最後に上で求めたcntの数から取り除ける最大の数の合計を引いた値を出力してACできます。

118 Monsters Battle Royale

practice.py

import math
n = int(input())
alist = list(map(int,input().split()))
ans = alist[0]
for i in range(1,n):
    ans = math.gcd(ans,alist[i])
print(ans)

結論から言うと、この問題の答えは全てのモンスターの体力の最大公約数です。　例えば、入力例1を使って説明してみると、先頭のモンスターから後ろの方のモンスターと体力の大きい方のモンスターを一方的攻撃していきます。すると10⇨8⇨6⇨4⇨2⇨0、2がずっと10をなぶり続けるとなって最終的には二つの数字の最大公約数2が残ります。　こんな感じでやっていけば答えに辿り続けます。　入力例2では、5,13の最大公約数1があり、1,8の最大公約数...みたいに続けていくと答えの1が残ります。　最大公約数はmathライブラリのgcdを使えば簡単に求められます。

122 GeT AC

practice.py

from itertools import accumulate

n,q = map(int, input().split())
s = input()
cnt = [0]*n
for i in range(n-1):
    if (s[i],s[i+1]) == ("A","C"):
        cnt[i+1] = 1
cnt = list(accumulate(cnt))
for i in range(q):
    l,r = map(int, input().split())
    print(cnt[r-1]-cnt[l-1])

この問題は累積和を使うことで解くことができます。文字列主体の問題なので、イメージがつきにくいかもしれませんが累積和でいけちゃいます(なぜ２回言った？)まずは累積和に必要不可欠なメソッドをaccumulateを使うために、数字を含んだlistを使ってあげましょう。中にぶち込む数字はACの連続があるかどうかです。判定のためにn-1でfor文を回していきましょう。連続があったら、Aは入ってるけどCは入ってないよを防ぐために、n+1の方に1を追加してあげます。これで準備は完了です。そしてaccumulateで累積和していきます。最後に出力をするために、lとrの値を受け取って、lとrの範囲の間なのでl-1(index番号は0から始まるから)までで出てくるACの数から、r-1までで出てくるACの数を引いてACです。

123 Five Transportations

practice.py

import math
n = int(input())
trans_capa = [int(input()) for _ in range(5)]
print(math.ceil(n/min(trans_capa))+4)

この問題で必要な考え方は、一番運べる人数が少ない交通機関です。その人数が最短で都市6まで辿り着ける人の人数になります。　そして、その数に基づいてグループ分けをしていきます。例を出してみると、nの数が6で一番運べる人数が少ない交通機関の運べる人数が2人だとすると、最短で辿り着ける2人のグループ、2番目に最短で辿り着ける2人のグループ、一番遅く辿り着ける2人のグループを3つのグループが作れます。その3つのグループが1分差で続々と到着していくので、答えはn/一番運べる人数が少ない交通機関の結果の切り上げた数(nが5で、2人の時にもグループが3つ作られるから)そして、誰も都市6にたどり着いていない期間の4分を答えに足して出力をすればACできます！