🦁

AtCoder ABC214 個人的メモ

6 min read

所感

abc3完

https://atcoder.jp/users/m193/history/share/abc214

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")

D - Sum of Maximum Weights

愚直に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)

参考

主客転倒

https://atcoder.jp/contests/typical90/tasks/typical90_am
https://github.com/E869120/kyopro_educational_90/blob/main/editorial/039.jpg

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

https://atcoder.jp/contests/dp/tasks/dp_q
以下PDFの「3 探索順の変更」
https://drive.google.com/file/d/1WC7Y2Ni-8elttUgorfbix9tO1fvYN3g3/view

F - Substrings

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

とりあえず計算量は気にせず解法を考える。
dp[i]を文字列Si番目までの文字を使って作れる文字列の集合とする。
この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の場合で新しく作った文字列が既出の文字列と重複していないかを判定するときのみである。
つまり、新しく作った文字列の内で既出の文字列と重複している個数が分かるように情報を持っていればおk。
これは各iで末尾のアルファベットごとの文字列の個数が分かれば良い。

というわけでdp[i][j]Si文字目までの文字を使って文字列の最後の文字が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)

Discussion

ログインするとコメントできます