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

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

<h1>Attack Survival</h1> 
<a href="https://atcoder.jp/contests/abc141/tasks/abc141_c">https://atcoder.jp/contests/abc141/tasks/abc141_c</a>

```python:practice.py
n,k,q = map(int, input().split())
points = [k]*n
for i in range(q):
    win = int(input())-1
    points[win] += 1
for point in points:
    if point-q > 0:
        print("Yes")
    else:
        print("No")
```

最初に正解者のポイントに１を追加し、後から全ての参加者から問題数と同じ数を引けば、問題で指示されている動作と同じことができます。

<h1>Go to School</h1> 
<a href="https://atcoder.jp/contests/abc142/tasks/abc142_c">https://atcoder.jp/contests/abc142/tasks/abc142_c</a>

```python:practice.py
n = int(input())
alist = list(map(int, input().split()))
rightOrder = [0]*n
for i, a in enumerate(alist):
    rightOrder[a-1] += (i+1)
print(*rightOrder)
```

enumerateとかいう便利すぎるbrotherを上手く使って、それぞれの値とindex番号受け取って上手いこと順番通りに並べ替えられます！


<h1>Slimes</h1> 
<a href="https://atcoder.jp/contests/abc143/tasks/abc143_c">https://atcoder.jp/contests/abc143/tasks/abc143_c</a>

```python:practice.py
n = int(input())
slimes = list(input())
cnt = 1
for i, slime in enumerate(slimes):
    if i != 0:
        if not slimes[i-1] == slimes[i]:
            cnt += 1
print(cnt)
```

最初の文字は絶対に残るのであらかじめcntの値を1にしておきます、すでにindex番号が０の時の処理は終わらせてあるので、0の時の処理はスキップしましょう。1より後の処理は、左隣の文字が現在の文字と違う場合にcntに１をつかしていく処理をslimesの文字の数だけ繰り返すして、結果を出力すればACできます。

<h1>Walk on Multiplication Table</h1> 
<a href="https://atcoder.jp/contests/abc144/tasks/abc144_c">https://atcoder.jp/contests/abc144/tasks/abc144_c</a>

```python:practice.py
import math
n = int(input())
ans = 0
lim = math.floor(math.sqrt(n))
while lim > 0:
    if n%lim == 0:
        print((lim-1)+(n//lim)-1)
        exit()
    lim -= 1
```

nまでの移動ということは、最終地点(a,b)はa*b=nになるはずです。なので全体の移動距離は((a-1)+(b-1))になります。　しかし全探索では計算量がO(n**2)になり制限時間に間に合わなくなってしまいます、計算量をO(n)でも間に合いません。　この場合は最小値なのでa<=√nにすることができます。最初にmathライブラリを使って、aの最大値を求めてからwhile文を回してnを割り切れるaの最大値を求め出します。aの値がわかれば、bの値はnの値からaを割るだけで求められるので計算量がO(√n)になり制限時間に間に合わせることができます！！

<h1>Average Length</h1> 
<a href="https://atcoder.jp/contests/abc146/tasks/abc145_c">https://atcoder.jp/contests/abc146/tasks/abc145_c</a>

```python:practice.py
import itertools 
import math

n = int(input())
points = []
for _ in range(n):
    point = list(map(int, input().split()))
    points.append(point)
num = list(range(n))
ptn = list(itertools.permutations(num))
sum_dist = 0
for p in ptn:
    for i in range(len(p)-1):
        a = p[i]
        b = p[i+1]
        x1 = points[a][0]
        x2 = points[b][0]
        y1 = points[a][1]
        y2 = points[b][1]
        sum_dist += math.sqrt((x2-x1)**2+(y2-y1)**2)
print(sum_dist/len(ptn))
```

nの制約が2≤N≤8なので、この場合は順列全探索が使えます、まず最初に全ての街の座標をpointsリストに格納します。次に移動順番の全てのパターンをitertools.permutations(num)を使って求めて,ptnリストに格納します。次に各パターンごとの距離を求め出してsum_distに加えます。　最後に平均の距離を求め出さないといけないのでsum_distをパターンの数で割ります。
参考にした記事
https://qiita.com/wihan23/items/107dfff1ecada60845b1

<h1>Buy an Integer</h1> 
<a href="https://atcoder.jp/contests/abc146/tasks/abc146_c">https://atcoder.jp/contests/abc146/tasks/abc146_c</a>

```python:practice.py
def is_ok(mid):
    if mid < 0:
        return True
    elif mid >= end:
        return False
    return a*mid + b*len(str(mid)) <= x

def binarySearch(ok, ng):
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok


a,b,x = map(int, input().split())
start = 0
end = 10**9+1
print(binarySearch(start,end))
```

最初に思いついたコードで提出したところTLEが出てしまい、２０分ほど考えたけど解放が1ミリも思い浮かばなかったので多分なんかアルゴリズム使ってるんやろな思って解説読んだら、案の定二分探索を使って解く問題でした。二分探索のテンプレートを見ながら書いたら意外と簡単に書けました、問題文も二分探索の記事を読んでから読み直してみると、二分探索臭プンプンでした。　すごい良い二分探索の練習になって個人的に大満足です！
本題の問題の解き方としては最初に問題文から商品の最大値と最小値を求め出します。この問題の場合は1から10**9なので、範囲は0と10**9+1になります（1と10**9を含むから）。　この二つの値から二分探索のテンプレートに沿って実装すると、かなり少ない計算量で解き切ることができます！

<h1>HonestOrUnkind2</h1> 
<a href="https://atcoder.jp/contests/abc147/tasks/abc147_c">https://atcoder.jp/contests/abc147/tasks/abc147_c</a>

```python:practice.py
from itertools import product

def judge(pro):
    flag = True
    for i in range(n):
        if pro[i]:
            for statement in statements[i]:
                if pro[statement[0]-1]!=statement[1]: 
                    flag = False
                    break
            if not flag:
                break
    if flag:
        return sum(pro)
    else:
        return 0

n = int(input())
statements = [[]for _ in range(n)]
for i in range(n):
    num = int(input())
    for j in range(num):
        statement = list(map(int, input().split()))
        statements[i].append(statement)
ans = 0
for pro in product((0,1), repeat = n):
    ans = max(ans, judge(pro))
print(ans)
```

Nの範囲が1≤N≤15なのでbit全探索で親切な人と不親切な人の全パターンを最初に全て洗い出します。　bit全探索についてはこの記事がすごい分かりやすいのでチェックしてみてください。　(https://qiita.com/u2dayo/items/68e35815659b1041c3c2)
def judge(pro):の中では、まずTrueのflag変数を矛盾が生じていないかを調べるために作ります。その後、proで作った仮定に従ってfor文を回します。for文の中で、親切な人と仮定した人がいるならば、その人の証言と仮定での証言を照らし合わせます。　もし、矛盾が生じるのならば、flagの値をFalseに書き換え処理を終わらせ、0を返します。もし矛盾が生じていないのならば、親切な人の人数を返します。最後にmaxメソッドを使って、最大値を求め出し、出力します。

<h1>Snack</h1> 
<a href="https://atcoder.jp/contests/abc148/tasks/abc148_c">https://atcoder.jp/contests/abc148/tasks/abc148_c</a>

```python:practice.py
import math
a,b = map(int, input().split())
lcm = (a*b)//math.gcd(a,b)
print(lcm)
```

A,Bどちらでも均等に配れるお菓子の最小個数は最小公倍数と同じ意味です。なので、mathモジュールと最小公倍数を求める公式(a*b)//math.gcd(a,b)を使うだけです。(小数の答えを求められてる場合は/)

<h1>Next Prime</h1> 
<a href="https://atcoder.jp/contests/abc149/tasks/abc149_c">https://atcoder.jp/contests/abc149/tasks/abc149_c</a>

```python:practice.py
import math
import bisect

def eratosthenes(n): 
    prime_list = []
    num_list=[i for i in range(2, n+1)] # 2以上n以下の整数を並べる
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0] # 倍数をふるい落とす

x = int(input())
max_lr = 10**6
er_list = eratosthenes(max_lr)
ind = bisect.bisect_left(er_list,x)
print(er_list[ind])
```

一応ACできたけど、絶対もっと良いやり方あるねコレ...説明すると、最初にエクストラネスの篩で10**6までの素数全部炙り出して、bisectでxより大きい素数のindex番号をbisect_leftを使って求め出して、最後に出力した。
絶対普通にxからfor文回してから全部
```python:practice.py
def is_prime(x):
    for i in range(2,x):
        if x%i == 0:
            return False
    return True
```
このメソッド使って求め出した方がコードも読みやすいし、計算量が少ない...

<h1>Count Order</h1> 
<a href="https://atcoder.jp/contests/abc149/tasks/abc149_c">https://atcoder.jp/contests/abc149/tasks/abc149_c</a>

```python:practice.py
import itertools

n = int(input())
p = tuple(map(int, input().split()))
q = tuple(map(int, input().split()))
nums = list(range(1,n+1))
patterns = list(itertools.permutations(nums))
a = patterns.index(p)
b = patterns.index(q)
print(abs(a-b))
```

nの範囲が2≤N≤8なので、なんとなく順列全探索を使うんだなーってのが分かります。なので最初に範囲が１からnまでのリストを作り、そのリストに入ってる数字の組み合わせを全パターン求め出してpatternsに格納しますこの時、各々のパターンはtuple型として格納されるので、pとqもtuple型として受け取っておくと楽です。全てのパターンを洗い出した後、index()メソッドを使って、pとqのindex番号(辞書順の大きさ)を取り出します。その後問題の指示通りに計算し、その結果を出力します！