Atcoder-ABC214をpythonで問題を解いてみた
目的
- Atcoderで上を目指すべく頑張っている中でABC214を解いたので、解説してみる
- pypy7.3を使って解いている
A問題
考察
- 問題文通りに解けば良い
実装
N = int(input()) if 1 <= N and N <= 125: print(4) elif 126 <= N and N <= 211: print(6) else: print(8)
結果
B問題
考察
- S<=100, T<=10000 なので、a, b, cを100以下にして全文探索すれば良さそう
- 1003 = 106 なので、時間内に終わると考えた
愚直に3重ループを書く
一瞬、数式に着目して賢く解けるんじゃないか?とも思ったけど、早く解くことを優先した
- 実際、3変数なのでそんなもんないw
実装
S, T = map(int, input().split()) ans = 0 for a in range(101): for b in range(101): for c in range(101): if a + b + c <= S and a * b * c <= T: ans += 1 print(ans)
結果
C問題
考察
- N<=200,000 なので、2重ループは無理そう
せいぜいO(NlogN)以内で解かなければなれないと思った
i, i+1の間には2つの関係性がありそう(dp[i], dp[i+1]をそれぞれi番目のすぬけ君が初めて宝石をもらう時刻とする)
- dp[i+1] = dp[i] + Si
- dp[i+1] = T[i+1]
- どちらか小さい方になる
- ここで、dp[1] (実際は0-indexedで解いたのでdp[0])が、dp[N]によって更新されることを見落としWA
- 上記の図の通り、更新される可能性があるので、更新した後、もう一度ループを回した(O(2N)なので、問題ないと判断)
実装
N = int(input()) S = list(map(int, input().split())) T = list(map(int, input().split())) dp = [0] * N dp[0] = T[0] for i in range(1, N): dp[i] = min(dp[i - 1] + S[i - 1], T[i]) dp[0] = min(dp[0], dp[N - 1] + S[N - 1]) for i in range(1, N): dp[i] = min(dp[i - 1] + S[i - 1], T[i]) print(*dp, sep="\n")
結果
D問題
BFSとかで、f(i, j) は求められても、馬鹿正直に計算するとO(N2)なので、どうしようと思っていて終わった
考察
最初は何も考えず、前に解いたダイクストラのコードをコピペした
- これ、経路の長さじゃなくて、到達点までに通った経路の最大値の総和を求めることに気づく
DFSとかBFSで経路を探索しながら、f(u, v) の総和を出すにはどうすればいいか悩む(O(N2)では確実にTLEなので)
- 多分、f(u, v)は同じものがあるので、賢く数え上げるんだろーなーくらいには思ったけど、どうすればいいかわからず時間切れ
- DFSした上で、その計算するのも厳しそうだなーと思い、多分発想が間違ってるんだろうなと思って多くの時間を過ごしたw
解説を見てUnion Findを使って解くことを知る
正直、公式解説読んでも全く分からなかったw
- 解説動画を見て「なるほど、非常に賢い!」と思ったw
辺に着目したときに、それぞれの辺の先の要素数の掛け算と、辺の重みで計算できる
- ここで、Union Findを使って、辺で繋がれる先々の要素数をグルーピングする
- 繋ぐときは、unionで同じグループとする
- その上で、小さいコスト順にsortした上で、上記を実行する
- 辺の最大値を求めるので、小さい順に処理すれば、前の処理に遡って更新する必要がないため
- 正直、sortするっていうのは、全く発想になくて、賢くて震えたのと、水色までの距離を感じた(今回のD問題は水色diff)
- 辺の最大値を求めるので、小さい順に処理すれば、前の処理に遡って更新する必要がないため
実装
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)] N = int(input()) uf = UnionFind(N) ans = 0 edges = [] for _ in range(N-1): u, v, w = map(int, input().split()) edges.append((u-1, v-1, w)) edges.sort(key=lambda x: x[2]) for u, v, w in edges: size1 = uf.size(u) size2 = uf.size(v) uf.union(u, v) ans += size1 * size2 * w print(ans)
結果
まとめ
今回のD問題は難しく、手が出なかった感じがした
- UnionFindは汎用性高そうなので、関連する類題を解こうと思った
前回もC問題で、WAしてしまったので、1回で解けるようにしたい
- 今回は気合入れてメモ書いてからやったが、WA出してしまったので、まだまだだと感じている