EAFP

~ Easier to Ask for Forgiveness than Permission ~

Atcoder-ABC214をpythonで問題を解いてみた

目的

  • Atcoderで上を目指すべく頑張っている中でABC214を解いたので、解説してみる
    • pypy7.3を使って解いている

A問題

atcoder.jp

考察

  • 問題文通りに解けば良い

実装

N = int(input())

if 1 <= N and N <= 125:
    print(4)
elif 126 <= N and N <= 211:
    print(6)
else:
    print(8)

結果

B問題

atcoder.jp

考察

  • 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問題

atcoder.jp

考察

  • 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]
      • どちらか小さい方になる

f:id:kazu_0716:20210815021853p:plain
dp[i], dp[i+1] の遷移に関して

実装

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)なので、どうしようと思っていて終わった

atcoder.jp

考察

  • 最初は何も考えず、前に解いたダイクストラのコードをコピペした

    • これ、経路の長さじゃなくて、到達点までに通った経路の最大値の総和を求めることに気づく
  • DFSとかBFSで経路を探索しながら、f(u, v) の総和を出すにはどうすればいいか悩む(O(N2)では確実にTLEなので)

    • 多分、f(u, v)は同じものがあるので、賢く数え上げるんだろーなーくらいには思ったけど、どうすればいいかわからず時間切れ
    • DFSした上で、その計算するのも厳しそうだなーと思い、多分発想が間違ってるんだろうなと思って多くの時間を過ごしたw

f:id:kazu_0716:20210815023023p:plain
214D解いたときのメモ

解説を見てUnion Findを使って解くことを知る

note.nkmk.me

  • 正直、公式解説読んでも全く分からなかったw

    • 解説動画を見て「なるほど、非常に賢い!」と思ったw
  • 辺に着目したときに、それぞれの辺の先の要素数の掛け算と、辺の重みで計算できる

    • ここで、Union Findを使って、辺で繋がれる先々の要素数をグルーピングする
    • 繋ぐときは、unionで同じグループとする
  • その上で、小さいコスト順にsortした上で、上記を実行する
    • 辺の最大値を求めるので、小さい順に処理すれば、前の処理に遡って更新する必要がないため
      • 正直、sortするっていうのは、全く発想になくて、賢くて震えたのと、水色までの距離を感じた(今回のD問題は水色diff)

f:id:kazu_0716:20210815023454p:plain
214D 解説理解のメモ

実装

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出してしまったので、まだまだだと感じている