超初心者がAtcoder ProblemsのC問題を134回から140回までをpythonで解いてみた【記憶喪失した時用】

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

Exception Handling

　https://atcoder.jp/contests/abc134/tasks/abc134_c

practice.py

n = int(input())
nums = [int(input()) for _ in range(n)]
new_nums = sorted(nums)
highest = new_nums[-1]
if len(new_nums) > 1:
    second_highest = new_nums[-2]
for i in range(n):
    if nums[i] == highest:
        print(second_highest)
    else:
        print(highest)

最初にリストを昇順に並べ替えて、一番大きい値を取得します。次にもしリストの要素数が1より大きい場合は二番目に大きい値も取得します(もし要素数が1の時に、この動作を行うとindex errorが出てしまう...)、次にfor文を回して消される値が一番大きい値と同じであるのなら二番目に大きい値を出力し、それ以外ならば一番大きい値を出力していきます！

City Savers

https://atcoder.jp/contests/abc135/tasks/abc135_c

practice.py

n = int(input())
cities = list(map(int, input().split()))
heros = list(map(int, input().split()))
cnt = 0
for i in range(n):
    if heros[i] == cities[i]:
        cnt += cities[i]
    elif heros[i] > cities[i]:
        cnt += cities[i]
        heros[i] -= cities[i]
        if heros[i] >= cities[i+1]:
            cnt += cities[i+1]
            cities[i+1] = 0
        else:
            cnt += heros[i]
            cities[i+1] -= heros[i]
    else:
        cnt += heros[i]
print(cnt)

正直この問題はB問題のように求められていることを素直に実行していけば解ける問題です。この問題で一番効率の良いモンスターの倒し方は、まずヒーローと同じインデックス番号の街のモンスターをすべて倒してから次の街のモンスターを残った力で倒せるだけ倒すという方法なので。その処理を問題文の条件に沿って実装していけば解けます！

Build Stairs

https://atcoder.jp/contests/abc136/tasks/abc136_c

practice.py

n = int(input())
numlist = list(map(int, input().split()))
for i in range(n-1):
    if abs(numlist[i]-numlist[i+1]) > abs(numlist[i]-(numlist[i+1]-1)):
        numlist[i+1] -= 1
    if numlist[i] > numlist[i+1]:
        print("No")
        exit()
print("Yes")  

まずそれぞれの値をリストの値を絶対値を元に-1をするかそのままにしておくか決定します、その後に単調非減少なのでそれぞれの値が左の値以上かを判定します、もしFalseならば"No"を出力して計算量をできるだけ減らすためにexit()で処理を終了させます。

Green Bin

https://atcoder.jp/contests/abc137/tasks/abc137_c

practice.py

n = int(input())
words = [''.join(sorted(input())) for _ in range(n)]
dict = {}
for i in range(n):
    if words[i] in dict:
        dict[words[i]] += 1
    else:
        dict[words[i]] = 1
print(sum(dict[d]*(dict[d]-1)//2 for d in dict)) 

まずそれぞれの文字列が合致しているかの判定を楽に行うためにsortで順番を整えます、その後に辞書方の変数を作成しfor文を回して辞書方の中に同じ要素がすでに存在していたら、文字列の値に１を足します、存在していなかったら文字列を辞書方に追加します。最後にそれぞれのdictの値から２個取り出すときのパターンの合計（dict[d]の値✖️dict[d]-1を２で割ることにより求められる）を足してsumメソッドで全体の合計数を求め出して出力します。

Alchemist

https://atcoder.jp/contests/abc138/tasks/abc138_c

practice.py

n = int(input())
values = sorted(list(map(int, input().split())))
while len(values) > 1:
    created = (values[0] + values[1])/2
    values.pop(0)
    values.pop(0)
    values.insert(0,created)
print(created)

小さい数から合成していった方が最終的に大きい数になるので最初にsortで順番を整えます、その後valuesの要素数が1以下になるまでwhile文を回します。while文の中では最初に0番目の要素と1番目の要素を合成し、その後0番目と１番目の要素は問題の使用上消えてしまうのでpopを使ってリストから取り除きます、その後先に作った値をリストにぶち込みます。

Lower

https://atcoder.jp/contests/abc139/tasks/abc139_c

practice.py

n = int(input())
hlist = list(map(int, input().split()))
ans = 0
cnt = 0
for i in range(1,n):
    if hlist[i-1] >= hlist[i]:
        cnt += 1
    else:
        ans = max(cnt, ans)
        cnt = 0
    if i == (n-1):
        ans = max(cnt,ans)
print(ans)

全探索をしているとO(N**2)になり時間に間に合わなくなってしまうので左端から移動の連続数を数えていきます、そうすることで計算量をO(N)にすることができ時間内に解き切れます。連続数を求めるためにfor文を(1からn)の範囲で回していきます。現在地をi-1として右隣以上の高さにあるか判定します、もしtrueならばcntに１を足し、もしfalseならば現時点での最大値と比べ、その後にcntの値を一度リセットします。そしてiが右端にあるのならば、これ以上飛び移ることができないので最大値と現在の連続数を比べてfor文を終了します。

Maximal Value

https://atcoder.jp/contests/abc140/tasks/abc140_c

practice.py

n = int(input())
blist = list(map(int, input().split()))
sum = 0
for i in range(n):
    if i == 0:
        sum += blist[i]
    elif i == (n-1):
        sum += blist[i-1]
    else:
        sum += min(blist[i-1],blist[i])
print(sum)

全ての可能性を試すと制限時間に間に合わなくなってしまうので、入力例から法則を見つけ出します。この問題の場合、A1にはB1の値が入りAnにはB(n-1)の値が入り、それ以外の場合はAiにmin(B(i-1),Bi)の値が入ります。
例えば入力3の場合はA1に０が入り、A2に０、A3に１０、A4に１０、A5に１０、A6に23ていったように数が入っていきます、全てリストに入れてから計算するのは面倒なのでsum変数に値を足していきます。