AtCoder Regular Contest 106 (A,B問題) の感想
ARC106、全然できませんでした!問題は画像として貼り付けてあり、最後にリンク貼ってます。先に解きたい人は解いてから見てねー。(前回の記事を見てAtCoderの問題解いてみた人が2人いて、競プロ仲間が増えて嬉しいです。)
A問題
見た瞬間に全探索を思いつきました。(それくらいしか武器がない。)適当に100乗くらいまで考えてればくらいになるでやんしょーってやったんですが、50乗くらいで良かったみたいです。地味に「正整数」って条件を見落としてWA出しました。
import sys N = int(input()) for i in range(1,100): for j in range(1,100): if 3**i + 5**j == N: print(i,j) sys.exit() print(-1)
B問題
パッと見て分からなかったのですが、手を動かして見ると、つながっている各ノードのaとbの総和が同じになればいいなーと気づきます。つながっているとかつながってないという情報を実装するために、Union Find 木を使えばいいかなー(それくらいしかグラフを知らない。)ということでポチポチ。コピペ。
note.nkmk.me
この記事すごいお世話になってます。
それぞれの木のの総和が同じか判定するために、それぞれのノードの根にを足していくとで計算できます。(本番はこれができなくて、空集合を用意して、ノードがメンバーであるような木を取り出して全部のを足して判定して、終わったらそれぞれのノードの番号を集合に追加して重複がないように‥とかやってたらPyPy3で38AC6TLEとかなっちゃいました。経験っす。)
import sys 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 size(self, x): return -self.parents[self.find(x)] def same(self, x, y): return self.find(x) == self.find(y) def members(self, x): root = self.find(x) return [i for i in range(self.n) if self.find(i) == root] def roots(self): return [i for i, x in enumerate(self.parents) if x < 0] def group_count(self): return len(self.roots()) def all_group_members(self): return {r: self.members(r) for r in self.roots()} def __str__(self): return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots()) N, M = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) c, d = [0]*M, [0]*M for i in range(M): c[i], d[i] = map(int, input().split()) c[i] -= 1 d[i] -= 1 uf = UnionFind(N) for i in range(M): uf.union(c[i], d[i]) B = [0]*N A = [0]*N #print(uf.roots()) for i in range(N): tmp = uf.find(i) A[tmp] += a[i] B[tmp] += b[i] if A != B: print("No") sys.exit() print("Yes")
感想
茶色パフォ(671)でレートが30上がりましたー。いえい。
ARCに出るたびにB問題もう少しって言ってますが、今回こそもう少しな気がしたので次は勝つ。勝つまで続ければ負けん!
来週のARCとABCのために、茶色問題解きます。