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

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

<h1>224 Triangle</h1>

https://atcoder.jp/contests/abc224/tasks/abc224_c

```python:practice.py
n = int(input())
points = [list(map(int, input().split())) for _ in range(n)]
nums = [i for i in range(n)]
cnt = 0
for i in range(n):
    x1,y1 = points[i]
    for j in range(i+1,n):
        x2,y2 = points[j]
        for k in range(j+1,n):
            x3,y3 = points[k]
            if (y2-y1)*(x3-x1) != (y3-y1)*(x2-x1):
                cnt += 1
print(cnt)
```

この問題は基本的にfor文を回して3点を選んであげれば良いのですが、唯一三角形が成立しない場合として、選んだ3点がすべて同じ直線に位置している時です(傾きが同じ)。なので全ての点の位置を洗い出した後に、(y2-y1)/(x2-x1)=(y3-y1)/(x3-x1)を変形した形の(y2-y1)*(x3-x1) = (y3-y1)*(x2-x1)を使って判定していきます。(変形する前の形のままでやるとZeroDivisionErrorの為の処理もしないといけないくて面倒だから)

<h1>225 Calendar Validator</h1>

https://atcoder.jp/contests/abc225/tasks/abc225_c

```python:practice.py
n,m = map(int, input().split())
blist = [list(map(int, input().split())) for _ in range(n)]
row = (blist[0][0]-1)//7
left = row*7+1
right = left+6
for i in range(m):
    if blist[0][i] < left or blist[0][i] > right:
        print("No")
        exit()

for i in range(n):
    for j in range(m-1):
        if blist[i][j+1] - blist[i][j] != 1:
            print("No")
            exit()
for i in range(n-1):
    if blist[i+1][0] - blist[i][0] != 7:
        print("No")
        exit()
print("Yes")
```

Yesになるための条件は3つあります。1つ目は、2行にまたがらないことです(例えば、5,6,7,8,9とかだと2行になってしまっているのでダメです、remember!mの制約は1<=m<=7) 2つ目は、1行の中の数が連続している(1,2,3,4みたいに、逆に1,4,5,7だと1,4の所が連続していないからだめ！) 3つ目は、上の行と下の行の差が7である。今回は逆に条件にそっていなかったら、Noを返して処理を終わらせるようにしています！2つ目と3つ目の処理は簡単なので、なんとか理解してください。ちょっとややこしいのが1番目の条件の処理なので、少し詳しく解説していきます。まず、1行目の数がAの何行目なのかを(blist[0][0]-1)//7で判定します(1を引いているのは、もしblist[0][0]の値が7の時、2行目扱いにされてしまうから(ふつーにめんどくさかったので、0行目から始まる想定で処理してます。なので0行目は1行目ということです。))　そして、上の処理で求めた値に従って、その週の１日目と最終日をleft = row*7+1とright = left+6で求め出して、for文を回して、判定しておわおわりです！

<h1>226 Martial artist</h1>

https://atcoder.jp/contests/abc226/tasks/abc226_c

BFSバージョン

```python:practice.py
from collections import deque
n = int(input())
T = [0]*(n+1)
learns = [[]]
for i in range(1,n+1):
    T[i],k,*alist = map(int, input().split())
    learns.append(alist)
done = [False]*(n+1)
done[n] = True
q = deque()
q.append(n)
ans = 0
while len(q) > 0:
    i = q.popleft()
    ans += T[i]
    for j in learns[i]:
        if not done[j]:
            done[j] = True
            q.append(j)
print(ans)
```

DFSバージョン

```python:practice.py
n = int(input())
T = [0]*(n+1)
learns = [[]]
for i in range(1,n+1):
    T[i],k,*alist = map(int, input().split())
    learns.append(alist)
done = [False]*(n+1)
toDo = [n]
done[n] = True
ans = 0
while toDo:
    i = toDo.pop()
    ans += T[i]
    for j in learns[i]:
        if not done[j]:
            done[j] = True
            toDo.append(j)
print(ans)
```

この問題は、BFSでもDFSでも基本的にやることは変わらないので、好みの方を選んでください。違いとしてはdequeを使うか使わないかレベルの小さな違いです。まずは、実際にDFS,BFSを回す前に必要な情報を受け取っていきましょう。受け取り終わったら、回すための準備を受け取った情報から始めていきましょう。まずは既に習得済みの技を管理するためのdoneリストを用意しておきます。次に、筒(que)の初期値としてnを入れておきましょう(ゴールから逆算していくイメージでやっていくから)。そして、done[n]もTrueに変えておきましょう。いよいよ、アルゴリズムの処理に移っていきます！　まずは筒の一番左にある数字を抜き出して、その技の習得にかかる時間をansに追加しておきましょう。そして、技を習得するために必要な技をfor文を回して、特定していきます！　もし、まだ習得が完了していなかったら筒(toDo)にぶち込んでおきましょう！
分かり易いBFSの解説動画
https://youtu.be/WyJvs9hL9Yc
分かり易いDFSの解説動画
https://youtu.be/VUoZ_WU90sM

<h1>227 ABC conjecture</h1>

https://atcoder.jp/contests/abc227/tasks/abc227_c

```python:practice.py
n = int(input())
ans = 0
for i in range(1,n+1):
    if i * i * i > n:
        break
    for j in range(i,n+1):
        if i * j * j > n:
            break
        ab = i * j
        mini = j
        maxe = n // ab
        ans += maxe - mini + 1
print(ans)
```

この問題は、aの値に制約があるというところまで辿り着けたが、bにも制約があるというところまで到達できなかったので、毎度お馴染みのunidayo先生の記事を見てきました...
すごくわかりやすいので、そっちを見てください、早くunidayo離れしてえなぁ...
https://qiita.com/u2dayo/items/da81f102d12724882a19#c%E5%95%8F%E9%A1%8Cabc-conjecture

<h1>228 Final Day</h1>

https://atcoder.jp/contests/abc228/tasks/abc228_c

```python:practice.py
n,k = map(int, input().split())
points = []
for _ in range(n):
    P = list(map(int, input().split()))
    p = sum(P)
    points.append(p)
points_damy = sorted(points)
limit = points_damy[-k]
for point in points:
    if point == limit:
        print("Yes")
    elif (limit-300) <= point:
        print("Yes")
    else:
        print("No")
```

なんか、B問題見たいな可愛い子です。　まずは全ての情報を得てから、昇順でsortします。次に、上位k内に入れるギリギリの点数を-kで取り出します。最後にfor文を回して、各テストの満点が300点なので、ギリギリの点数から300を引いた点数より、3回目のテスト終了時点での点数が大きいかどうかを判定して、Trueならyesを返していきます。

<h1>229 Cheese</h1>

https://atcoder.jp/contests/abc229/tasks/abc229_c

```python:practice.py
n,w = map(int, input().split())
cheeses = [list(map(int, input().split())) for _ in range(n)]
cheeses.sort(reverse=True)
ans = 0
for cheese in cheeses:
    if w >= cheese[1]:
        ans += cheese[0]*cheese[1]
        w -= cheese[1]
    else:
        ans += cheese[0]*w
        break
print(ans)
```

この問題はチーズの価値が大きいチーズをできるだけのせるだけの問題です。そのために欠かせないのがsortです、全てのデータを受け取ったら、即sort(reverse=True)で降順にします（幸い、配列の1番目の要素なので楽々できる）　並び替えたら、置けるだけ価値の高いチーズを乗せてくだけでACできます！

<h1>230 X drawing</h1>

https://atcoder.jp/contests/abc230/tasks/abc230_c

```python:practice.py
n,a,b = map(int, input().split())
p,q,r,s = map(int, input().split())
h = q-p+1
w = s-r+1
for i in range(p,q+1):
    ans = []
    for j in range(r,s+1):
        if (i-j==a-b) or (i+j==a+b):
            ans.append("#")
        else:
            ans.append(".")
    print(''.join(ans))
```

ふつーに、B問題解く感覚で馬鹿みたいにやってたら、案の定TLEになって10分ぐらい考えたけど訳分からんかったから、unidayoさんの力を借りたら、めちゃくちゃスゲェってなった話だよね。灰diff上位問題は安定して解けるようになってきたけど、まだ茶diffがあんまし解けないから、これが壁やね。頑張ろ...

unidayoさんの天才コード
https://qiita.com/u2dayo/items/316cfd601283232cdc56#c%E5%95%8F%E9%A1%8Cx-drawing