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

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

<h1>171 One Quadrillion and One Dalmatians</h1>

https://atcoder.jp/contests/abc171/tasks/abc171_c

```python:practice.py
n = int(input())
ans = ""
while (n > 0):
    n-=1
    temp = 97 + (n % 26)
    ans += chr(temp)
    n //= 26
print(ans[::-1])
```

桁数はwhile文で決めていきます。２６で割れる回数が桁数になる感じです。while文の中で１を引いているのはunicodeの９７番が"a"になるので引かないと入力が1の時にbを出力してしまうからです。じゃあ、tempで足す値を96にしても動くんじゃねってなると思い試してみましたがzを出力するときに26%26=0によりユニコード番号96番の値が入ってきて、出力がおかしくなってしまうのでダメでした。ユニコードが定まったらchrメソッドを使ってansに文字を追加していきます。最後に26で割ります。これをnの値が0になるまで続けます（//=なのでnが26以下だったらnは０になる）
最後に取得した値を反転させます（正直なんでか分からない、誰か教えて）

<h1>172 Tsundoku</h1>

https://atcoder.jp/contests/abc172/tasks/abc172_c

```python:practice.py
from itertools import accumulate
import bisect

n,m,k = map(int, input().split())
alist = [0]+list(map(int,input().split()))
blist = list(map(int,input().split()))
alist = list(accumulate(alist))
blist = list(accumulate(blist))
ans = 0
for i in range(n+1):
    a = alist[i]
    leftT = k - a
    if leftT < 0:
        break
    b = bisect.bisect_right(blist, leftT)
    ans = max(ans, i+b)
print(ans)
```

この問題は総和を使った問題ですね。alistに[0]を追加しておくのは、aの本から一冊も読まないという選択もしたいからです。次にalistとblistをaccumulateを使って総和のリストにします（"本が残っている机を選び、その机の最も上に積まれた本を読んで机から取り除く"と問題文にあるから）。んで、やっとこさfor文をぶん回します。このfor文のiはalistから読む本の数を表しています。変数aにはalistの上からi冊を読むのにかかる時間が入り、blistの本を読むのにかけられる時間をleftTに格納します。もしleftTが０以下なら、alistからi冊を読むのにかかる時間が制限じかんより多くなってしまっているということなのでbreakをします。bisect_rightメソッドを使ってleftTの時間で読めるblistの本の数を求めます。そして最後にansの値とそれぞれのforループで求められた読める本の冊数を比べて大きいほうをansに入れていき、出力します。
bisectについて
https://qiita.com/ta7uw/items/d6d8f0ddb215c3677cd3

<h1>173 H and V</h1>

https://atcoder.jp/contests/abc173/tasks/abc173_c

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

def judge(pro1, pro2):
    S = [s_line[::] for s_line in s]
    for i in range(h):
        if pro1[i]:
            for j in range(w):
                S[i][j] = "!"
    for j in range(w):
        if pro2[j]:
            for i in range(h):
                S[i][j] = "!"
    cnt = 0
    for s_line in S:
        cnt += s_line.count("#")
    if cnt == k:
        return True
    return False

h,w,k = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans=0
for pro1 in  product((0,1), repeat=h):
    for pro2 in product((0,1), repeat=w):
        ans += judge(pro1,pro2)
print(ans)
```

この問題はbit全探索君の問題ですね。楽しいね。列or行を消すか消さないかの考え方でbit全探索をします。1≤H,W≤6をH,Wの値がそこまで大きくならないのでbit全探索ボーイが成立します。この問題ではまず行用と列用でproductを二重ループで使わないといけません。judge関数のところではまず、与えられたマス目の配置のコピーを用意します。その後、他のbit全探索の問題と同様にforループを回してpro1[i]の値が1ならば、その行の値を全て"!"に変えてしまいます。次に列用のforループを回してpro2[i]ならば、その列の値を全て"!"に変えてしまいます。次にfor文をもう一度使いSのマス目達を行ごとに区切り、行ごとの"#"の数を数え上げcntに追加していきます。最後にもし#の数がkの値と同じならTrue(1)を返し、違うのならばFalse(0)を返していきます。

<h1>174 Repsept</h1>

https://atcoder.jp/contests/abc174/tasks/abc174_c

```python:practice.py
n = int(input())
num = 0
for i in range(1,10**7):
    num*=10
    num+=7
    num%=n
    if num == 0:
        print(i)
        exit()
print(-1)
```

この問題は余りの 「足し算・引き算・掛け算をするたびに余りを取っても、結果が変わらない」 性質を使うらしいです。
正直１５分考えても解法が全く思いつかなかったのでunidayo師匠の記事を参考にしました。
普通にそっちみた方が早いので記事のリンクはっ付けておきますね...
uniちゃんのやつ
https://qiita.com/u2dayo/items/83faeb39ac14c63c8986
余りの性質について
https://xn--48s96ub7b0z5f.net/amari-goudoushiki/

<h1>175 Walking Takahashi</h1>

https://atcoder.jp/contests/abc175/tasks/abc175_c

```python:practice.py
x,k,d = map(int, input().split())
cnt = abs(x//d)
if cnt <= k:
    if x < 0:
        x += cnt*d
    elif x > 0:
        x -= cnt*d
    leftM = k-cnt
    if leftM % 2 == 0:
        print(x)
    else:
        ans = min(abs(x-d),abs(x+d))
        print(ans)
else:
    if x < 0:
        x += k*d
        print(abs(x))
    elif x > 0:
        x -= k*d
        print(abs(x))
```

正直このコードはちょっと不細工だね...多分どうせ最後にxを絶対値にしちゃうなら最初から絶対値にしちゃったほうがコードの短縮できそうだな。あとcntの数もminメソッドを使っちゃえば、多分if文で２回分余分にコードを書く必要なかった感はあるね。いろいろ改善点はありますが、必要な考え方を説明していきます。まず、絶対値をできるだけ小さくしたいということは、できるだけ0に近づきたいということです。（cnt=x//d（多分ここ改善できるね））。次に必要なのは0にできるだけ近づいた後に残っている行動回数です。もし偶数ならば行ったり来たりを繰り返せばいいだけなので、何もせずそのままの位置を出力するだけです。しかし、もし奇数ならば、正の方向に動いた場合の絶対値を負の方向に動いた場合の絶対値を比べてより小さい方を出力します。ではもし、0に限りなく近づくために必要な行動回数が、与えられた行動回数より小さい場合はどうするのか？フツーにできるだけ0に近づいてください（多分助けになってない、気合いで理解しろ!）

<h1>176 Step</h1>

https://atcoder.jp/contests/abc176/tasks/abc176_c

```python:practice.py
n = int(input())
alist = list(map(int, input().split()))
cnt = 0
for i in range(n-1):
    if alist[i] > alist[i+1]:
        cnt += (alist[i]-alist[i+1])
        alist[i+1] += (alist[i]-alist[i+1])
print(cnt)
```

正味B問題レベルやね。一つ前の人と高さを比べて、小さければ、差分をcntをその人に加えるを人数分繰り返していけば、ACできるよー。1≤N≤2×10**5だからTLEにはならない（計算量はO(N-1)多分...）

<h1>177 Sum of product of pairs</h1>

https://atcoder.jp/contests/abc177/tasks/abc177_c

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

mod = 10**9+7
n = int(input())
alist = list(map(int, input().split()))
numlist = [0]+alist
numlist = list(accumulate(numlist))
ans = 0
for i in range(n-1):
    ans += (alist[i]*(numlist[-1]-numlist[i+1]))
print(ans%mod)
```

最初、馬鹿みたいに全てのパターンをitertoolsのcombinationで洗い出して、凸って行ったら案の定、TLEでボコされたよね。しばらく解法考えたけど分かんなかったから調べたら、この問題総和の問題らしいね。
A1×(A2+A3+A4+A5)
A2×(A3+A4+A5)
A3×(A4+A5)
A4×(A5)
こういう感じの考え方をするのが大切らしい。この形でやったらO(N-1多分...)になってTLEしないんよね。この考えみたい時、天才やんってなってもうたわ。めちゃくちゃ納得できるやんけコレェなったわ。んで、それをこの考え方を適応するために必要なんだ総和ですね。例えばA1×(A2+A3+A4+A5)の(A2+A3+A4+A5)の部分はA5までの合計値引くA1ってことだから、総和を使って、簡単に求められる（総和の最大値からかける値までの総和を引く（numlist[i+1]にしてるのはnumlistに０を追加しているから））。

<h1>178 Ubiquity</h1>

https://atcoder.jp/contests/abc178/tasks/abc178_c

```python:practice.py
mod = 10**9+7
n = int(input())
print(((10**n)-(2*(9**n))+8**n)%mod)
```

この問題は、直接条件を満たすパターンの数を求めるより、全体から条件を満たさないパターンの数を引いた値を求める方が簡単です。まず、条件に0≤Ai<=9とあるので、全体のパターン数は10**nになることがわかります。次に9の入っていないパターンの数は9**nになり、0の入っていないパターンの数も9**nになります。しかし、(10**n)-(2*(9**n))ではうまくいきません（０も９も入っていないパターンを２回引いてしまっているから）。なので最後に0も９も入っていないパターン数8**nを足してあげてmodで割った余りを出力してあげればACできます。

<h1>179 A x B + C</h1>

https://atcoder.jp/contests/abc179/tasks/abc179_c

```python:practice.py
n = int(input())
cnt = 0
for a in range(1,n):
    cnt += (n-1)//a
print(cnt)
```

この問題ではaの値を固定して考えます。aごとのbの値のパターンは(n-1)//a通り考えられます。(n-1)//aで得た数をcntに足し続けて出力します。
例えばnが１００の時の正整数のパターンの一部ですが
24 1 76
24 2 52
24 3 28
24 4 4
25 1 75
25 2 50
25 3 25
aの値が24の時は4つのパターンがあるのに、aの値が25になった瞬間にパターン数が3つになっているのがわかります。これが(n-1)//aが成立する証拠です。同様に33と34のところでも、考えられるパターン数が変わってきます。

<h1>180 Cream puff</h1>

https://atcoder.jp/contests/abc180/tasks/abc180_c

```python:practice.py
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())
divisors = make_divisors(n)
for divisor in divisors:
    print(divisor)
```

この問題はnの約数を全て洗い出して、出力すればACできます。約数列挙のプログラムは
https://qiita.com/LorseKudos
さんのを借りてきました。ありがとうございます。
使った記事
https://qiita.com/LorseKudos/items/9eb560494862c8b4eb56