ABC218のC,D問題を、Python3で解説します！
ょゎょゎな筆者でもわかる、読みやすさを重視した、初心者向け解説です(´・ω・｀)
ゆっくり見ていってね(｀・ω・´)ｷﾘｯ
目次
1. C問題 - Shapes
2. D問題 - Rectangles
C問題 『Shapes』
回転移動とか平行移動とか言われたら、頭がこんがらがるよね(´・ω・｀)
でも落ち着いて解いたら大丈夫(｀・ω・´)
考え方
そもそも、'#'の数が違ったら、絶対一致しないのでアウト。
$N≦200$ なので、全探索でOK。
0度、90度、180度、270度回転させたもの4つをそれぞれ平行移動させて、一致するかどうか確かめる。
平行移動は、一番左上の'#'の位置によって、どれぐらい動かせば良いかわかる。
コード
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で割るのをお忘れなく！
コード
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問題とか、過去問の解説上げてくかも。
来週も頑張ろうね(｀・ω・´)ｷﾘｯ