【どこよりもわかりやすい】Atcoder ABC218 C・D問題 Python3解説

**ABC218**の**C,D**問題を、**Python3**で解説します！

ょゎょゎな筆者でもわかる、読みやすさを重視した、**初心者**向け解説です(´・ω・｀)

ゆっくり見ていってね(｀・ω・´)ｷﾘｯ

# 目次
[1. C問題 - Shapes](#-c問題-shapes)
[2. D問題 - Rectangles](#-d問題-rectangles)

# C問題 『Shapes』

回転移動とか平行移動とか言われたら、頭がこんがらがるよね(´・ω・｀)
でも落ち着いて解いたら大丈夫(｀・ω・´)

### 考え方

そもそも、'#'の数が違ったら、絶対一致しないのでアウト。

$N≦200$ なので、全探索でOK。
0度、90度、180度、270度回転させたもの4つをそれぞれ平行移動させて、一致するかどうか確かめる。

平行移動は、一番左上の'#'の位置によって、どれぐらい動かせば良いかわかる。

### コード

```python:C.py
n = int(input())

#入力を受け取るついでに、'#'の数を数えておく
S = []
cnt_S = 0
for i in range(n):
    s = list(input())
    S.append(s)
    for ss in s:
        if ss == '#':
            cnt_S += 1

T = []
cnt_T = 0
for i in range(n):
    t = list(input())
    T.append(t)
    for tt in t:
        if tt == '#':
            cnt_T += 1

#'#'の数が違ったら、アウト
if cnt_S != cnt_T:
    print('No')
    #print(1)
    exit()

#一番左上の'#'の位置を返す関数
def find_left_top(square):
    for i in range(n):
        for j in range(n):
            if square[i][j] == '#':
                return i, j

#90度回転させる関数
def rotation_90(square):
    s_prime = [['.' for i in range(n)] for j in range(n)]

    for i in range(n):
        for j in range(n):
            s_prime[j][n-i-1] = square[i][j]

    return s_prime

#図形が一致するかどうかを返す関数
def is_same(S, T):
    Si, Sj = find_left_top(S)
    Ti, Tj = find_left_top(T)

    #TのSからのずれを求める
    offset_i = Ti-Si
    offset_j = Tj-Sj

    for i in range(n):
        for j in range(n):
            ii = i+offset_i
            jj = j+offset_j
            
            if 0<=ii<n and 0<=jj<n:
                if S[i][j] != T[ii][jj]:
                    return False
            else:
               if S[i][j] == '#':
                    return False
    
    return True

for i in range(4):
    if is_same(S, T) == True:
        print('Yes')
        exit()
    S = rotation_90(S) #Sを90度回転させる

print('No')
```

# D問題 『Rectangles』

### 考え方

まず、「**長方形の対角の2点が定まれば、他の2点も定まる**」ことに気づくかどうか。

対角の2点を $(x_1,y_1), (x_2,y_2)$ とすると、 $(x_1,y_2), (x_2,y_1)$ が存在すれば、長方形が存在する。

$N≦2000$ より、$O(N^3)$ だと間に合わないので、$(x_1,y_2), (x_2,y_1)$ が存在するかどうかは、**二分探索**で求めれば、間に合う(｀・ω・´)

二分探索するときは、頂点のタプルを要素にもつリストを、`無名関数lambda`でソートすればよい。
まず $y$ 順にソートして、それから $x$順にソートすればよい。

>無名関数lambdaについて（他の方のqiita）
https://qiita.com/nagataaaas/items/531b1fc5ce42a791c7df

対角の2点と他の2点を二重に数えてしまうので、最後は2で割るのをお忘れなく！

### コード

```python:D.py
n = int(input())

#xyに点を格納していく
xy = []
for i in range(n):
    x, y = map(int, input().split())
    xy.append((x, y))

#頂点を、まずyの順でソート、それからxの順でソート
xy.sort(key=lambda x: x[1])
xy.sort(key=lambda x: x[0])

#二分探索で、点が存在するかどうかを返す関数
def binary(x, y):
    ok = 0
    ng = n
    while ng-ok > 1:
        m = (ok+ng)//2
        if xy[m][0] < x:
            ok = m
        elif xy[m][0] > x:
            ng = m
        else:
            if xy[m][1] <= y:
                ok = m
            elif xy[m][1] > y:
                ng = m
    if x == xy[ok][0] and y == xy[ok][1]:
        return True
    else:
        return False

#答えを0で初期化
cnt = 0

for i in range(n-1):
    for j in range(i+1,n):
        x1, y1, x2, y2 = xy[i][0], xy[i][1], xy[j][0], xy[j][1]
        if x1==x2 or y1==y2: #対角の点になっていなければ次のループへ
            continue
        if binary(x2,y1) and binary(x1,y2): 
            cnt += 1

#二重に数えているので2で割る
print(cnt//2)
```

# まとめ
最後まで見てくれてありがとう(´・ω・｀)
今回はむずかったよね(´・ω・｀)
これからも自分の勉強がてらABCのC,D問題とか、過去問の解説上げてくかも。
来週も頑張ろうね(｀・ω・´)ｷﾘｯ