0件ヒットしました
    2020-11-15

    【Python】ABC183 解説

    ABC183に参加しました. 結果はA~E5完893893位パフォーマンス14851485.
    F問題も解けそうだったんですが、collections.Counterの仕様の理解不足でTLETLEになってしまい撃沈。。 もったいなかった。

    ranking_abc183

    以下, A~F問題の解説およびPython解答例です.

    A - ReLU

    DeepLearningではおなじみのRectifiedLinearUnitRectified Linear Unit関数。 「近年のDeepLearningのブレイクスルーは本質的にはReLUReLU関数の発見だけ」と言った専門家がいるとかいないとか。

    x = int(input())
    ans = x if x >= 0 else 0
    print(ans)

    B - Billiards

    • S=(x1,y1)S = (x_1, y_1), 点G=(x2,y2)G = (x_2, y_2)としたとき、点S=(x1,y1)S' = (x_1, -y_1)をとり、直線SGS'Gxx軸の交点が答えとなる.
    • 直線SGS'Gの傾きをa=y2(y1)x2x1a = \frac{y_2 - (-y_1)}{x_2 - x_1}とする。
    • すると直線SGS'Gの式は y(y1)=a(xx1)y - (-y_1) = a(x - x_1)と表すことができる。
    • xx軸との交点はy=0y = 0を代入したときのxxの値のため, x=x1(y1)ax = x_ 1 - \frac{(-y_1)}{a} である。
    x1, y1, x2, y2 = map(int, input().split())
    
    a = (y2 - (-y1)) / (x2 - x1)
    
    x = x1 - (-y1) / a
    print(x)

    C - Travel

    N8N \leq 8と小さいため全探索を考える。
    C問題といえば全探索。

    from itertools import permutations
    
    
    N, K = map(int, input().split())
    T = [list(map(int, input().split())) for _ in range(N)]
    
    cnt = 0  # cnt: 移動時間がちょうどKとなる経路の数
    for path in permutations(range(1, N)):
        cost = 0  # cost: 移動時間
        crt = 0  # crt: 現在地点の都市番号
        for nxt in path:
            cost += T[crt][nxt]
            crt = nxt
        cost += T[crt][0]  # 都市0に戻ってくることを忘れずに
        cnt += (cost == K)
    print(cnt)

    D - Water Heater

    いもす法の簡単な問題。

    • 長さ max(Ti)+1max(Ti) + 1 の配列dpを用意して, 各Si,Ti,PiS_i, T_i, P_iごとにdp[Si]dp[S_i] += PiP_i, dp[Ti]dp[T_i] -= PiP_iとする。
    • 配列dpの累積和を順に計算し一度でもWWを上回った場合は答えが’No’となる。
    import sys
    from itertools import accumulate
    
    
    N, W = map(int, input().split())
    M = 2 * (10 ** 5)
    dp = [0] * (M + 1)
    for _ in range(N):
        s, t, p = map(int, sys.stdin.readline().split())
        dp[s] += p
        dp[t] -= p
    
    ans = 'Yes' if max(accumulate(dp)) <= W else 'No'
    print(ans)

    E - Queen on Grid

    公式解説と同じ考え方で。

    • マス(i,j)(i, j)へ移動する方法の数 ==
      縦の移動: マス(i1,j)(i - 1, j)から移動 + マス(i2,j)(i - 2, j)から移動 + \cdots
      ++ 横の移動: マス(i,j1)(i, j - 1)から移動 + マス(i,j2)(i, j - 2)から移動 + \cdots
      ++ 斜めの移動: マス(i1,j1)(i - 1, j - 1)から移動 + マス(i2,j2)(i - 2, j - 2)から移動 + \cdots
    • よって、縦・横・斜めの累積和を管理していけば計算量を落とせる。
    H, W = map(int, input().split())
    grid = [input() for _ in range(H)]
    MOD = 10 ** 9 + 7
    
    dp = [[0] * W for _ in range(H)] # dp[i][j]: マス(i, j)に到達する方法の数
    dpU = [[0] * (W + 1) for _ in range(H + 1)] # dpU: 縦方向の累積和 (Up方向)。H列目・W行目は番兵。
    dpL = [[0] * (W + 1) for _ in range(H + 1)] # dpL: 横方向の累積和 (Left方向)。H列目・W行目は番兵。
    dpS = [[0] * (W + 1) for _ in range(H + 1)] # dpS: 斜め方向の累積和 (Slant方向)。H列目・W行目は番兵。
    
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '.':  # マス(i, j)が道のときのみ移動可能
                L = dpL[i][j - 1]  # L: 横方向からの移動方法。dp[i][j - 1]通り。
                U = dpU[i - 1][j]  # U: 縦方向からの移動方法。dp[i - 1][j]通り。
                S = dpS[i - 1][j - 1] # S: 斜め方向からの移動方法。dp[i - 1][j - 1]通り。
                
                # マス(i, j)に移動する方法の数を計算
                here = dp[i][j]
                here += L + U + S
                here %= MOD
                
                # 各セルを更新する
                dp[i][j] = here
                dpL[i][j] = (L + here) % MOD
                dpU[i][j] = (U + here) % MOD
                dpS[i][j] = (S + here) % MOD
    
    print(dp[-1][-1])

    F - Confluence

    UnionFindの変則問題。

    • UnionFindUnionFind木を以下のように実装する。
    • 親ノードはcollections.Counterを保持する。このCounterCounterで当該グループのクラス: 所属人数\text{クラス: 所属人数}のペアを管理する。
    • 子ノードは親ノードのノード番号を保持する(通常のUnionFindUnionFind木と同じ)
    • グループ同士の結合の処理(UnionFind.union())では、CounterCounterの項目数(len(Counter)len(Counter))を比較し小さい方を大きい方に結合させる(通常のUnionFindUnionFind木の逆。通常は大きい方を小さい方に結合させる。)

    結局これだけ?楽勝じゃん!っと思ったが、union()の実装でハマった。。。
    みなさんは以下の方法1~3のうちどれが計算量が少ないかわかるだろうか?

    A = Counter('-省略-')
    B = Counter('-省略-')
    
    # 方法1
    A += B
    
    # 方法2
    for k, v in B.items():
      A[k] += v
    
    # 方法3
    A.update(B)

    なんと、方法1O(max(len(A),len(B)))\mathcal{O}(max(len(A), len(B))), 他の方法ではO(len(B))\mathcal{O}(len(B))なのである!(今回の経験からの個人的推測)

    というわけで今回のlessons learnedは,

    2つのCounterCounterの結合の際は, 「+=」は厳禁!update()を使え! 2020, Ma-r-co et.al.

    import sys
    from collections import Counter
    
    
    class UnionFind():
        def __init__(self, n, C):
            # 初期化処理では各ノードにCounterを持たせる
            self.parents = [Counter([C[i]]) for i in range(n)]
    
        def find(self, x):
            # Counterインスタンス --> そのノードは親
            # int --> そのノードは子
            if isinstance(self.parents[x], Counter):
                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 len(self.parents[x]) < len(self.parents[y]):
                x, y = y, x
            # update()を使う!!! 超重要!!!
            self.parents[x].update(self.parents[y])
            self.parents[y] = x
    
    
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    query = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
    
    uf = UnionFind(N, C)
    
    for t, *V in query:
        if t == 1:
            a, b = V
            a -= 1; b -= 1
            uf.union(a, b)
        else:
            x, y = V
            x -= 1
            print(uf.parents[uf.find(x)][y])

    くそ〜〜全完したかった〜〜!!!