🦁

AtCoder ABC214 個人的メモ

2021/08/16に公開

Python

競技プログラミング

AtCoder

tech

所感

abc3完

A - New Generation ABC

N = int(input())

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

B - How manyb

S, T = map(int, input().split())

ans = 0
for a in range(S + 1):
    for b in range(S + 1):
        for c in range(S + 1):
            if a + b + c <= S and a * b * c <= T:
                ans += 1

print(ans)

C - Distribution

問題文通りにシミュレーション
円周上になっているので2周する。

N = int(input())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
INF = 10 ** 18

ans = [INF] * N
for i in range(N):
    ans[i] = min(T[i], ans[i - 1] + S[i - 1])
for i in range(N):
    ans[i] = min(T[i], ans[i - 1] + S[i - 1])

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

愚直に $i,j$ を $_NC_2$ 通りを調べるのは無理。
各辺ごとにその辺の重みを最大値とする頂点の組み合わせの個数が $O(1)$ で分かれば良さそう。
そのためには $f(u,v)$ と頂点の個数が $O(1)$ で分かれば良い。
ここで辺の無いN個の頂点に辺を1つずつ追加していく事を考える。
各辺を追加することによって連結される2つの連結成分の大きさからその辺を通る頂点の組み合わせが求めることができる。
この時、辺を重みの小さい順に追加していくとする。
すると、新しく追加される辺は現在の辺の中での最大の重みになっている。
よって、上記の様にシミュレーションすれば $f(u,v)$ と頂点の個数を求めることができる。
頂点の連結と連結成分の大きさを求めるのにunion-findを用いれば1辺当たり $O(logN)$ で求まるので十分高速。

union-find

class UnionFind:
    """Union-Find(素集合データ構造(disjoint-set data structure)に対しての操作)"""

    def __init__(self, n: int):
        """
        Constructer(Initialize parameter in this class)

        Parameters
        ----------
        n : int
            Number of node

        Yields
        -----
        root : list
            When value is postive, express root of the node.
            When it is negative, express this node is root and size of set.
        """

        self.root = [-1] * n

    def find(self, x: int) -> int:
        """
        Search root of node x

        Parameters
        ----------
        x : int
            node x

        Returns
        -------
        x : int
            Root of node x
        """

        if self.root[x] < 0:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]

    def unite(self, x: int, y: int) -> bool:
        """
        Unite two set including node x and node y into one set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        unite_result : bool
            False : Already two node include same set.
            True  : United
        """

        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        return True

    def is_same(self, x: int, y: int) -> bool:
        """
        Determine if x and y are in same set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        result : bool
            Determining result
        """

        return self.find(x) == self.find(y)

    def size(self, x: int) -> int:
        """
        Return size of set including node x.

        Parameters
        ----------
        x : int
            Node number

        Returns
        -------
        Size of set : int
        """

        return self.root[self.find(x)] * -1

from operator import itemgetter

N = int(input())
edge = [list(map(int, input().split())) for _ in range(N - 1)]  # 整数を入力

edge.sort(key=itemgetter(2))
union = UnionFind(N + 1)

ans = 0
for u, v, w in edge:
    ans += union.size(u) * union.size(v) * w
    union.unite(u, v)
print(ans)

参考

主客転倒

小さい順に見ていくことで最大値の計算を省略

以下PDFの「3 探索順の変更」

F - Substrings

よくわかんないけど自力acしちゃった

とりあえず計算量は気にせず解法を考える。
$dp[i]$ を文字列 $S$ の $i$ 番目までの文字を使って作れる文字列の集合とする。
このdpの遷移は以下のようになる。

$i=1$ の場合
$S$ の1文字目 $S_1$ からなる文字列(1個)
$i=2$ の場合
$S_1$ からなる文字列と $S_2$ からなる文字列(合わせて2個)
$i\geq 2$ の場合
$dp[i]$ は以下の3つの場合から既出の文字列を除いた集合
1. $dp[i-1]$ のすべての文字列
2. $dp[i-2]$ の文字列に $S_i$ を追加した文字列
3. $S_i$ のみからなる文字列(1個)

このdpを実行できれば解が得られるが、実際には文字列の集合がとても大きくなり実行できなそう。
そのため、保持する情報をもっと小さくする必要がある。
既出の文字列の集合の情報が必要になるのは上記の遷移の内 $i\geq 2$ の場合で新しく作った文字列が既出の文字列と重複していないかを判定するときのみである。
つまり、新しく作った文字列の内で既出の文字列と重複している個数が分かるように情報を持っていればおｋ。
これは各 $i$ で末尾のアルファベットごとの文字列の個数が分かれば良い。

というわけで $dp[i][j]$ を $S$ の $i$ 文字目までの文字を使って文字列の最後の文字が $j(0\leq j\leq 25)$ (25はアルファベットの個数)の場合の数とする。
この時の $dp[i-1]$ から $dp[i]$ への遷移を考えてみる。
重複を無視すると、新しく作れる文字列の個数は $1+\sum _{j=0}^{25}dp[i-2][j]+dp[i-1][j]$ となる。
これは上述の $i\geq 2$ の場合の 1. 2. 3. と同じ。
ここから重複分を引くのだが、それは $dp[i-1][S_i]$ である。
$S_i$ を既出の文字列の末尾に追加してできる新しい文字列の末尾は当然 $S_i$ である。
$S_{i-1}$ までで末尾が $S_i$ となっている文字列の個数は $dp[i-1][S_i]$ に記録されている。
よってこれを引けば重複分を除くことができる。

従って、遷移式は以下のようになる。
遷移の場合分けは上記のやつと同じ。

$j=S[i]$ の場合
$dp[i][j]=(\sum _{k=0}^{25}dp[i-1][k]) +1-dp[i-1][j]$
(0~25は全てのアルファベットのこと)
$j\not ={S[i]}$ の場合
$dp[i][j]=dp[i-1][j]$

こんなかんじで実装して提出したらacできた。

重複を防ぐために文字列の末尾を保持するdpってどっかでやった気がするけどどこだか思い出せない

S = input()
N = len(S)
alphabet_num = 26
MOD = 10 ** 9 + 7

# dp[i][j]:=i文字目までを見て、最後にアルファベットjを使う場合の数
dp = [0] * (alphabet_num)
# sum(dp[i])をメモ(各iでsum(dp[i])を求めるとtleするのでメモしておく)
row_sum = [0] * (N + 2)  # N+2の+2は番兵
for i in range(N):
    j = ord(S[i]) - ord("a")      # j:=アルファベットS[i]を表すインデックス

    row_sum[i] = row_sum[i - 1]   # 1. dp[i-1]のすべての文字列の個数
    row_sum[i] += row_sum[i - 2]  # 2. dp[i-2]の文字列にS[j]を追加した文字列の個数
    row_sum[i] += 1               # 3. $S$の$i$文字目のみからなる文字列(1個)
    row_sum[i] -= dp[j]           # 重複分を除く
    row_sum[i] %= MOD

    # dp配列を使いまわしているので1.のdp[i-1]は既に加算済み
    dp[j] = 0                     # 重複分dp[j]を引く(dp[j]-dp[j]=0)
    dp[j] += row_sum[i - 2]       # 2.
    dp[j] += 1                    # 3.
    dp[j] %= MOD

print(sum(dp) % MOD)