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

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

<h1>191 Digital Graffiti</h1>

https://atcoder.jp/contests/abc191/tasks/abc191_c

```python:practice.py
h,w = map(int, input().split())
S = []
for _ in range(h):
    s = input()
    S.append(s)
ans = 0
for row in range(h-1):
    for col in range(w-1):
        tmp = []*4
        tmp.append(S[row][col])
        tmp.append(S[row+1][col]) 
        tmp.append(S[row][col+1])
        tmp.append(S[row+1][col+1])
        if tmp.count("#") == 1 or tmp.count("#") == 3:
            ans += 1
print(ans)
```

15分考えたが全く解法が浮かんでこなかったのでunidayo先生の記事を参考にさせてもらいました。
っぱunidayo先生だよな
https://qiita.com/u2dayo/items/71280b8f832a8981b88c

<h1>192 Kaprekar Number</h1>

https://atcoder.jp/contests/abc192/tasks/abc192_c

```python:practice.py
n,k = input().split()
for _ in range(int(k)):
    num1 = sorted(n,reverse=True)
    num2 = sorted(n)
    n = str(int(''.join(num1))-int(''.join(num2)))
print(n)
```

この問題では主にnを文字列として扱います。まず、k回for文を回します。for文の中ではnum1に各桁の数字を大きい順に並び替えてできる整数を入れて、num2には各桁の数字を小さい順に並び替えてできる整数を入れます。num1とnum2はリストの状態になるので、nを更新するタイミングでjoinメソッドを使って、一度文字列に変換してあげた後に、四則演算をするためにint型に変換し、num1からnum2を引き終わったら、次の処理を楽にするためにもう一度str型に変換してあげましょう。幸いkの値が大きくならないのでTLEせずに行けます。

<h1>193 Unexpressed</h1>

https://atcoder.jp/contests/abc193/tasks/abc193_c

```python:practice.py
n = int(input())
anslist = set()
for i in range(2,10**5+1):
    num = i**2
    while num <= n:
        anslist.add(num)
        num *= i
print(n-len(anslist))
```

この問題は1≤N≤10**10だから全探索できんやん、おわたってなるかもしれませんが、実は全探索の問題です。2乗3乗の数を求めてくる問題なので、for文の中で2乗にしてしまうことを考えると10**5+1まで調べ上げれば、答えが出せます。ただ、重複は作りたくないので、条件をクリアした、数をset型のリストにぶち込みます。(16だと4**2と、2**4で表せるので、重複が生まれてしまう)最後に全体の数から、anslistの要素数を引けばACです！

<h1>194 Squared Error</h1>

https://atcoder.jp/contests/abc194/tasks/abc194_c

```python:practice.py
from collections import Counter
n = int(input())
alist = list(map(int, input().split()))
counter = Counter(alist)
ans = 0
for i in range(-200, 201):
    for j in range(i+1, 201):
        x = counter[i]
        y = counter[j]
        ans += x*y*(i-j)**2
print(ans)
```

unidayoさんの力を借りたよ、早く自立したい... unidayoさんによると、この問題の重要なポイントは"各数字が何回出現するかだけが答えに影響して、どこに出てくるかは関係ない"らしいです。そして、問題の制約で　-200<=Ai<=200であるということです。なので簡単にリストの要素の重複回数をカウントできる便利なCounterメソッドを使い数を上手く調べ上げ、for文を問題の制約に基づいてrange(-200, 201)とrange(i+1, 201)で回していき。最後に、counter内でのiとj出現回数分(i-j)**2をansに追加してあげればACできるというわけです(iかjの数字がcounter内で一回も出現しない時は掛け算内に0が一度出てくることによりansに追加される値が0になるので上手くいきます)。

<h1>195 Comma</h1>

https://atcoder.jp/contests/abc195/tasks/abc195_c

```python:practice.py
n = int(input())
leng = len(str(n))
num = leng / 3
cnt = 0
if num > 1:
    cnt += n-999
if num > 2:
    cnt += n-999999
if num > 3:
    cnt += n-999999999
if num > 4:
    cnt += n-999999999999
if num > 5:
    cnt += n-999999999999999
print(cnt)
```

超ぶさいくなコードさんこんにちは！3桁ごとにカンマが入ってくるのでnの桁数を３で割った数を使って、どれだけカンマがつく数字があるかを判定しましょう。(//じゃなくて/にしているのはちょうど3桁時と4桁以上の時を見分けられるようにするため。)かなりだるいやり方なのですが、私はfor文の構造を考えるのがだるかったのでif文を5個作るとかいう脳筋プレーで突破しました(nの桁数は最大で16桁だから)。判定のところで=を入れていないのは、もしnum>=1にしてしまうと、ちょうど3桁の時にnumの値がちょうど1になり、if num>=1の中の処理が動いてしまい、WAになるからです（一度それでWAした...）しかし、>にするとちょうど3の時のケースが上手く弾かれてACできます。cnt+=n-999なのは、範囲内でのカンマの入る数字の数がnの数-1000(num > 1の時)+1になるからです。
正直もっと良いコードにできた。他の人のコード調べて、次はもっとよくできるようにしよう

<h1>196 Doubled</h1>

https://atcoder.jp/contests/abc196/tasks/abc196_c

```python:practice.py
n = int(input())
leng = len(str(n))//2
if leng == 0:
    leng+=1
num = int(str(n)[:leng])
ans = 0
if len(str(n)) % 2 == 0:
    for i in range(1,num+1):
        if int(str(i)*2) <= n:
            ans += 1
    print(ans)
    exit()
if len(str(n)) % 2 != 0:
    for i in range(1,num*10+1):
        if int(str(i)*2) <= n:
            ans += 1
    print(ans)
```

この問題のめんどくさいところはまず、桁数が奇数の場合と偶数の場合で処理をすこーしだけ変えないといけないところと、1桁の時にエラーがnum=int(str(n)[:leng])のところでエラーが出てしまうので、エラーのパターンを察知してif文を使って、エラーを回避できるようにすることが必要です。そして奇数の場合の処理は前半の桁数を1増やしてあげないといけません。この問題は前半の数列から、数を求めるだけなので、for文で回すのは10**（桁数の数の半分）だけなので、nが10**12でも12を6にできTLEにはなりません。実際のfor文の中ではiの数字をstr型に直してから、後半の数を*2で作り出して、その数がnの数より小さければansに1を追加します
このコードも、もっとシンプルにできそう...

<h1>197 ORXOR</h1>

https://atcoder.jp/contests/abc197/tasks/abc197_c

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

INF = 1<<60

def judge(pro):
    pro = pro + (1,)
    ret = 0
    curr = 0
    for i in range(n):
        curr |= alist[i]
        if pro[i]:
            ret ^= curr
            curr = 0
    return ret

n = int(input())
alist = list(map(int, input().split()))
ans = INF
for pro in product((0,1), repeat=n-1):
    ans = min(ans, judge(pro))
print(ans)
```

この問題はbit全探索で行けちゃいます。多分1≤N≤20からなんとなーく予想できると思います。この問題では、どこでxorの為に数字を区切るかという考え方でbit全探索をしていきます。repeatの数がn-1なのは区切りの数で考えているからです。judge関数の中では、まず最初にproに(1,)を追加しています。これは問題の性質上、絶対に1回はxorをしないといけないからです。その後はorで区切った用の変数retとxorで区切った時用の変数currを用意しときます。他のbit全探索と同様にfor文を回します。まずcurrの数とalistの数字でorの処理をします。次にもしpro[i]がTrueだったらretとcurrの値でxorの処理をし、その後currの値をリセットします。全ての処理が終わった後にretの値を返して、ansの値と比べて、低い数字を選びます。

<h1>198 Compass Walking</h1>

https://atcoder.jp/contests/abc198/tasks/abc198_c

```python:practice.py
import math

R,X,Y = map(int, input().split())
dist = math.sqrt(X**2+Y**2)
if dist < R:
    print(2)
else:
    print(math.ceil(dist/R))
```

この問題で大切になるのはスタート地点から目的地までの距離です。なので、まずdist変数にユークリッド距離の公式を使って求めた距離を格納します。次に、実際の移動回数を求めす。もし例題1のようにピッタリと割り切れる数ならば、そのまま出力すればいいのですが、例題2のように割り切れないケースがほとんどだと思います。その場合には少数を切り上げて出力します。(実質dist//R+1、ceilを使っているのは例題1のようなピッタリと割り切れるケースにも対応できるから)。考え方としてはまずは一直線に目的地の近くまでいきます。そして最後の一回でうまいこと調整するみたいな感じです。この問題の穴と下はdistがRより小さい場合です。その場合は1回でいけるやん、アンパイやんとなりガチですが、実は目的地を飛び越えてしまうので、1回飛んだ後に、調整のためにもう一度とぶ必要があるので2を出力します。

<h1>199 IPFL</h1>

https://atcoder.jp/contests/abc199/tasks/abc199_c

```python:practice.py
def get_idx(x):
    if x < n:
        return 0, x
    else:
        return 1, x-n

n = int(input())
s = input()
q = int(input())
first = list(s[:n])
second = list(s[n:])
s = [first,second]
for i in range(q):
    t,a,b = map(int, input().split())
    a -= 1
    b -= 1
    if t == 1:
        ai,aj = get_idx(a)
        bi,bj = get_idx(b)
        s[ai][aj], s[bi][bj] = s[bi][bj], s[ai][aj]
    else:
        s[0],s[1] = s[1], s[0]
ans = ''.join(s[0]) + ''.join(s[1])
print(ans)
```

B問題解くノリで凸ったら案の定TLEで弾かれた、unidayoさんの力つかわせてもらった、高速化のテクニックをもっと勉強しないといけないとすごい実感した問題だった...リストで処理するというところまではたどり着けたけど、多分処理の方法が非効率すぎてTLE出ちゃったね。
https://qiita.com/u2dayo/items/7a702cf4fdd93b056fd8#c%E5%95%8F%E9%A1%8Cipfl

<h1>200 Ringo's Favorite Numbers 2</h1>

https://atcoder.jp/contests/abc200/tasks/abc200_c

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

n = int(input())
alist = list(map(int, input().split()))
alist = [a%200 for a in alist]
alist = Counter(alist)
ans = 0
for num in alist.values():
    if num > 2:
        ans += (((num)*(num-1))//2)
    else:
        ans += num-1
print(ans)
```

この問題を解くために必要な考え方はAi−Ajは200の倍数であるということはAiを200で割った時のあまりがAjを200で割った時のあまりと等しいということです。まず、alistの値をすべて200で割った時の余りの数に変換し、数を調べ上げるためにCounterメソッドを使いました。for文の中ではnumが2より大きい場合のパターン数はnumの数から2個を選ぶのと等しいので、(((num)*(num-1))//2)になります。2以下の場合は単純にnum-1でおけです。