Atcoder-ABC218をpythonで解いてみた
目的
- Atcoderで上を目指すべく頑張っている中でABC218を解いたので、解説してみる
- pypy7.3を使って解いている
A問題
考察
- 問題文通りに解けば良い
実装
N = int(input()) S = input() if S[N-1] == "o": print("Yes") else: print("No")
結果
B問題
考察
- 問題文通りに解けば良い
- ACSIIコードを利用する(a=97, b=98, ... となる)
実装
P = list(map(int, input().split())) ans = [] for i in range(len(P)): ans.append(chr(P[i]+96)) print(*ans,sep="")
結果
C問題
考察
- 各図形をトリミングして考えれば良さそう
- 平行移動に関しては、トリミング結果と同一であれば良い
90度回転を3度行い、基の図形と同様になるかを確認する
トリミングは、図形の左上詰で考える
#が含むx, y座標の最小値、最大値をそれぞれ取得し、座標を変換する
実装
提出したコードをリファクタしたもの
N = int(input()) S, T = [], [] def set_points(l): min_x, max_x, min_y, max_y = 300, -1, 300, -1 for i in range(N): s = list(input()) for j in range(len(s)): if s[j] == "#": l.append([j, i]) min_x = min(min_x, j) max_x = max(max_x, j) min_y = min(min_y, i) max_y = max(max_y, i) return min_x, max_x, min_y, max_y def convert(l, min_x, max_x, min_y, max_y): shape = [[0] * (max_x - min_x + 1) for _ in range((max_y - min_y + 1))] for x, y in l: x -= min_x y -= min_y shape[y][x] = 1 return shape min_xs, max_xs, min_ys, max_ys = set_points(S) min_xt, max_xt, min_yt, max_yt = set_points(T) s = convert(S, min_xs, max_xs, min_ys, max_ys) t = convert(T, min_xt, max_xt, min_yt, max_yt) flag = False for _ in range(4): if s == t: flag = True break s = list(map(list, zip(*s[::-1]))) if flag: print("Yes") else: print("No")
結果
D問題
考察
解説では、対角線上の2点を求めていたが、別のアプローチを取った
- 長方形の左下の点(P1)を定める
- P1のx座標の中のどれかが、同じ点がP2となる
- P1のy座標の中のどれかが、同じ点がP3となる
- P4 = (P3x, P2y)が、存在するか確認し、あればcountする
実装
from itertools import combinations N = int(input()) X, Y = {}, {} ans = 0 for _ in range(N): x, y = map(int, input().split()) if x in X: X[x].add((x, y)) else: X[x] = set([(x, y)]) if y in Y: Y[y].add((x, y)) else: Y[y] = set([(x, y)]) for x in X: xset = X[x] for p1, p2 in combinations(xset, 2): yset = Y[p1[1]] yset -= set([p1, p2]) for p3 in yset: if (p3[0], p2[1]) in Y[p2[1]]: ans += 1 print(ans)
結果
E問題
考察
本番中は時間なくて解けなかった
- 今回は、コストの小さい順に各nodeをUninFind-Treeで結合していく
- 経路がマイナスなものは、結合する
- それぞれのnodeの親が違う場合も結合する
- それ以外の場合は、edgeを切っても良いので、コストとして加算する
- 結合しない
実装
class UnionFind(): def __init__(self, n): self.n = n self.parents = [-1] * n def find(self, x): if self.parents[x] < 0: return x else: self.parents[x] = self.find(self.parents[x]) return self.parents[x] def union(self, x, y): x = self.find(x) y = self.find(y) if x == y: return if self.parents[x] > self.parents[y]: x, y = y, x self.parents[x] += self.parents[y] self.parents[y] = x def same(self, x, y): return self.find(x) == self.find(y) N, M = map(int, input().split()) uf = UnionFind(N) edges = [tuple(map(int, input().split())) for _ in range(M)] edges.sort(key=lambda x: x[2]) ans = 0 for a, b, c in edges: if c < 0 or not uf.same(a-1, b-1): uf.union(a-1, b-1) else: ans += c print(ans)
結果
まとめ
- 今回は、D問題まで解けた！次も頑張るぞ！
- 人生2度目のD問題解くのに成功し、非常に嬉しい
