ABC214 参加記録

• 4完0ペナ 33分でした
• 最近全く精進できていませんでしたが結果オーライでよかったです。

A - New Generation ABC

新しい問題形式にちなんだ内容でしたね。記載通りのルールに従って実装します。

N = int(input())
if N <= 125:
    print(4)
elif N <= 211:
    print(6)
else:
    print(8)

B - How many?

見た目が難しい問題です。制約を見ると は非負整数で和が 以下になることがわかります。 ということで、雑に としてループさせると計算量は くらいになるので、これで回して数え上げてしまいます。

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 or a*b*c > T:
                break
            ans += 1
print(ans)

C - Distribution

これもひと工夫要る問題でした。

宝石は高橋くんが配ります。そのタイミングと、宝石が隣の人から回ってくるタイミングを比較することが第一方針です。

「宝石が隣の人から回ってくるタイミング」について考えるために、高橋くんの宝石配布時間が最も早いものを考えてみます。 例えば高橋くんが 1 番の人に最も早く宝石を渡すとき、2番の人は高橋くんから受け取るか、1番の人から回ってくるかのどちらかです。次の人は、これらのうち早いタイミングで来た方だけ考えれば良いことがわかります。

ということで、高橋くんの宝石配布時間が最も早いところから順繰りに比較することで、 番目の人が初めて宝石をもらう時刻を調べることができます。これは なので間に合います。

N = int(input())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
tidx = T.index(min(T))

ans = [float('inf')] * N
ans[tidx] = T[tidx]

for k in range(1, N):
    ans[(tidx+k)%N] = min(T[(tidx+k)%N], ans[(tidx+k-1)%N] + S[(tidx+k-1)%N])

print(*ans, sep='\n')

D - Sum of Maximum Weights

和の問題です。典型的なパターンを掴んだのか早めに解くことができました。

木の頂点2つ を選んだときの最短パス上に含まれる辺の重みの最大値 について次の和を求めます。

言い換えると、ある重み が最短パス上で最大の重みとして何回出てくるか？となります。

これを考えるにあたって、計算対象がパスの重みの最大値であることから、与えられた辺の重みの小さい方から考えていくのが良さそうです。下記の図のようなイメージです。

数え上げのイメージ

最も右の図において、 となるパスの数は、 の連結する前の頂点数の掛け算で計算できます。 連結した頂点数の管理には unionfind を使えば良いです。全体の計算量は です。

提出コード

class UnionFind():
    """
    unionfind を扱うクラス (0-index)

        Parameters:
        -----------
        n: int
            管理するデータの要素数
    """
    def __init__(self, n:int):
        """
        Parameters:
        -----------
        n: int
            要素数
        parents: list
            各要素が属する親の要素番号
        grouping: set
            親番号の集合
        rank: list
            親の rank を保持するためのリスト
        size: list
            親の size を保持するためのリスト
        """
        self.n = n
        self.parents = [-1]*n
        self.grouping = set(range(n))
        self.rank = [0]*n
        self.size = [1]*n


    def find(self, x:int) -> int:
        """
        要素 x の親の要素を見つけるメソッド

        Parameters:
        -----------
        x: int
            要素番号
        
        Returns:
        --------
        int
            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:int, y:int) -> None:
        """
        要素 x, y の属するグループを結合するメソッド
        
        Parameters:
        -----------
        x, y: int
            結合対象の要素番号
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            # rank(x)の方が小さい場合は, xをくっつけて, y を親にする
            self.size[y] += self.size[x]
            self.parents[x] = y
            self.grouping.difference_update(set([x]))
        else:
            # そうでないときは, y をくっつけて, x を親にする
            self.size[x] += self.size[y]
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.grouping.difference_update(set([y]))


    def msize(self, x:int) -> int:
        """
        要素 x の属するグループの大きさを返すメソッド

        Parameters:
        -----------
        x: int
            要素番号
        
        Returns:
        --------
        int
            x の属するグループの大きさ(要素数)
        """
        return self.size[self.find(x)]


def main():
    N = int(input())
    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])
    uf = UnionFind(N)

    ans = 0
    for u, v, w in edges:
        ans += w * uf.msize(u) * uf.msize(v)
        uf.union(u, v)
    print(ans)


if __name__ == "__main__":
    main()

E - Packing Under Range Regulations

計算量が厳しく思いつきませんでした。