超初心者がAtcoder ProblemsのC問題を151回から160回までをpythonで解いてみた

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

<h1>Welcome to AtCoder</h1>

https://atcoder.jp/contests/abc151/tasks/abc151_c

```python:practice.py
n,m = map(int, input().split())
ac = [False]*n
wa = [0]*n
for i in range(m):
    q, r = input().split()
    q = int(q)
    if r == "WA" and (not ac[q-1]):
        wa[q-1] += 1
    elif r == "AC":
        ac[q-1] = True
numAc = 0
numWa = 0
for i in range(n):
    if ac[i]:
        numAc += 1
        numWa += wa[i]
print(numAc, numWa)
```

この問題は問題文をよく読まないとWAになってしまいます。私も半分飛ばして読んでいたら、見事にWAの罠にかかりましたよ、楽しいね。　"高橋君のペナルティ数は、高橋君が AC を 1 回以上出した各問題において、初めて AC を出すまでに出した WA の数の総和です。"　この文の<h3>ACを一回以上出した</h3>というところが引っ掛けポイントです。コレにさえ気づければ、実装は簡単です。　まずacを既にしているかどうかを確認するためにfalseが入ったリストと、acが出るまでのwaの数が入ったリストを用意しておきます。次にm回分結果を受けとって、もし結果がWAかつ、まだacが出ていなかったらwaに数を足していきます。もし初めてacが出たら、falseをtrueに変えます。最後に引っ掛けポイントの"ACを一回以上出した"の部分を実装していきます。

<h1>Low Elements</h1>

https://atcoder.jp/contests/abc152/tasks/abc152_c

```python:practice.py
N = int(input())
P = list(map(int, input().split()))
cnt = 1
mini = P[0]
for p in P[1:]:
    if p <= mini:
        cnt += 1
        mini = p
print(cnt)
```

まず絶対に最初の数字は条件を満たすことが<=であることから分かります、なのでcntの初期値を1にしておきます。次に検査した数字の中で一番小さい数字を格納するmini変数を作っておきます。最初はP[0]の値しか検査していないのでminiにはP[0]を入れておきます。　次に1からNまでの値をチェックしていきます。もし条件に合う数字が出てきた場合はcntに１を足してminiの値を更新していきます。（常に現在地より左側が大きくないと条件に合わないから）最後にcntの数を出力をすれば完了です。全探索ではO(n**2)に二乗になり時間に間に合いません...

<h1>Fennec vs Monster</h1>

https://atcoder.jp/contests/abc153/tasks/abc153_c

```python:practice.py
n,k = map(int, input().split())
hlist = sorted(list(map(int, input().split())), reverse=True)
total = sum(hlist)
if k >= n:
    print(0)
    exit()
total -= sum(hlist[:k])
print(total)
```

まず必殺技は数が大きい相手に使うようにしましょう。なのでsorted(リスト名, reverse=True)で数が大きい順に並び替えましょう。その後、全てのモンスターの体力の合計値が入ったtotalから必殺技を使って倒せるモンスターの体力値の合計を引きましょう（indexエラーを防ぐためにkがnより大きかった時の処理を上に書いておく）　最後に残ったモンスターの体力値を出力します（最小の攻撃回数=必殺技で倒せなかったモンスターの体力の合計値であるから）、最初にfor文をk回分回してしまって、TLEになりました...気をつけような。なるべくC問題ではfor文を使わないように意識するのがTLEを出さないコツかもしれんな...

<h1>Distinct or Not</h1>

https://atcoder.jp/contests/abc154/tasks/abc154_c

```python:practice.py
n = int(input())
alist = set(list(map(int, input().split())))
if n == len(alist):
    print("YES")
else:
    print("NO")
```

この問題は正直B問題レベルですね。Aの配列の中の全ての数が違うということは、Aの持ってる数字の種類数がnの値と同じことなので、一度setでリストの重複を全て消してしまいましょう。その後、set型にしtalistの要素数とnの値を比べて同じならyesを違うならnoを出力しましょう！

<h1>Poll</h1>

https://atcoder.jp/contests/abc155/tasks/abc155_c

```python:practice.py
from collections import Counter

n = int(input())
S = []
for i in range(n):
    S.append(input())
counter = Counter(S)
maxe = counter.most_common()[0][1] 
words = []
for w, c in counter.items():
    if c == maxe:
        words.append(w)
for word in sorted(words):
    print(word)
```

まずリストの中にある単語の出現回数を簡単に調べてくれる便利なCounterとかいう最高のbroをインポートしましょう。Counterが何か分からないbroは、便利だから使い方調べてくれや
https://note.nkmk.me/python-collections-counter/
まずcounterを使って一番多く出てきた単語の出現回数をmost_commonメソッドを使って調べ上げましょう。次にmost_commonで取得した回数と同じ回数出てきた単語を洗い出してwordsリストに格納しましょう。最後に辞書順に並べ替えたwordsリストをもとにfor文を回して出力していきましょう！

<h1>Rally</h1>

https://atcoder.jp/contests/abc156/tasks/abc156_c

```python:practice.py
n = int(input())
xlist = list(map(int, input().split()))
mini = min(xlist)
maxe = max(xlist)
ans = 10**9
for i in range(mini, maxe+1):
    total = 0
    for x in xlist:
        temp = ((x-i)**2)
        total += temp
    ans = min(ans, total)
print(ans)
```

B問題みたいな感じで全探索するだけでいけちゃいますね（範囲はxlistの中の最小値から最大値の間、この範囲外が答えの地点になることはnothing to much オーマイゴッドファーザー降臨です）。ansに絶対に超えられることのないぐらい大きい数字を設定し。先に述べた範囲内でfor文を回し、それぞれのポイントにより消費される体力の総和をxlistを元にしたfor文を回して求めていきます。消費体力の総和を求め終わったら、minメソッドを使って現在の最小値より少ない消費量かどうかを調べ出します。もしそうならばansの値を置き換えます！

<h1>Guess The Number</h1>

https://atcoder.jp/contests/abc157/tasks/abc157_c

```python:practice.py
n,m = map(int, input().split())
conds = []
for i in range(m):
    temp = list(map(int, input().split()))
    conds.append(temp)
if n == 1:
    start = 0
else:
    start = 10**(n-1)
for i in range(start,10**n):
    i = str(i)
    judge = True
    for cond in conds:
        if not judge:
            break
        if i[cond[0]-1] != str(cond[1]):
            judge = False
    if judge:
        print(i)
        exit()
print(-1)

```

この問題は実装とかアルゴリズムがむずいとかじゃなくて、問題文がちょっと複雑で理解するのが面倒系の問題ですね。本当に滅びてほしいです...まず、味噌なのは1≤N≤3とNの値がそこまで大きくならないので全探索でパターンを調べまくれることです。私は全探索で最初にNで指定された桁数の数字を全て洗い出しました(startのところで条件分岐をしているのはnが1桁の時に0も含めないといけないから)。そして判定を楽にするためにiのデーター型をstr型に変換し、s,cの条件で矛盾がなく条件に当てはまっている数字があるかを判定していきます。もし当てはまる数字が見つかったのならば、出力してexit()で処理を終了します。もし見つからずに全ての処理が回り切ってしまった場合には-1を出力します。

<h1>Tax Increase</h1>

https://atcoder.jp/contests/abc158/tasks/abc158_c

```python:practice.py
a,b = map(int, input().split())
for i in range(1,10**5):
    if int(i * 0.08) == a and int(i * 0.1) == b:
        print(i)
        exit()
print(-1)
```

この問題はaとbの数があまり大きくなることはないので十分に大きい数字で全探索を回せばいけます。判定方法は問題文のとうりにやればいいので、簡単にACできます。

<h1>Maximum Volume</h1>

https://atcoder.jp/contests/abc159/tasks/abc159_c

```python:practice.py
l = int(input())
print((l/3)**3)
```

この問題はなんと2行でACできてしまいます！立方体の体積の公式は(縦*横)*高さなので、一番体積が大きくなるのは縦、横、高さが同じ値を持っている時です。その値として最大なのは与えられた長さの合計/3です。公式と一辺の長さをうまいこと組み合わせていけばたった2行でACできてしまいます。fabulous!!(海外のおばちゃん風)

<h1>Traveling Salesman around Lake</h1>

https://atcoder.jp/contests/abc160/tasks/abc160_c

```python:practice.py
k,n = map(int, input().split())
alist = list(map(int,input().split()))
ans = 10**9
dist = []
for i in range(n-1):
    dist.append(alist[i+1]-alist[i])
dist.append(abs(alist[0]+(k-alist[-1])))
print(sum(dist)-max(dist))
```

この問題は円形の湖が舞台なので、一つだけ通らなくて良い区間を選べます。なので、全ての家の区間をfor文を回して調べ上げます。そして最初の家から最後の家まで湖を逆に回ってたどり着くための距離をabs(alist[0]+(k-alist[-1]))で求め出します。（ここがプラスなのは0の地点から最初の家までの距離と0(湖なので一周の距離から引いて計算する)から最後の家の距離を足したものが求めているものだから）、そして最後に区間の合計値から一番大きな区間の値を引いて出力します（最小の距離にするには一番長い距離の移動を省略することが最適だから）