0件ヒットしました
    2021-01-23

    【Python】ABC189 解説

    ABC189に参加しました. 結果は3329302930位パフォーマンス942942
    泣きたい

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

    2021/01/24 F問題の解説を追加

    A - Slot

    setの大きさで判定する。

    C = set(input())
    ans = 'Won' if len(C) == 1 else 'Lost'
    print(ans)

    B - Alcoholic

    小数の扱いに注意。
    全体に100100をかけて整数の範囲で判定できるようにする。

    N, X = map(int, input().split())
    IN = [tuple(map(int, input().split())) for _ in range(N)]
    x = 0
    for i, (v, p) in enumerate(IN):
        x += v * p
        if x > 100 * X:
            ans = i + 1
            break
    else:
        ans = -1
    print(ans)

    C - Mandarin Orange

    解けなかった。。泣きたい。
    O(108)\mathcal{O}(10^8) は間に合わないと勘違いしてた。

    N = int(input())
    A = list(map(int, input().split()))
    INF = float('inf')
    ans = 0
    for l in range(N):
        m = INF
        for r in range(l, N):
            m = min(m, A[r])
            cnt = (r - l + 1) * m
            ans = max(ans, cnt)
    print(ans)

    D - Logical Expression

    メモ化再帰で解いた。

    • dp(i,j)dp(i, j): yi=jとなるxの組(x0,,xi)の個数y_i = j\text{となる}x\text{の組}(x_0,\dots,x_i)\text{の個数}とする。 j=0or1j=0 \text{or} 1である。
    • 求めたい答えはdp(N,1)dp(N, 1)である。また, 初期条件はdp(0,0)=dp(0,1)=1dp(0, 0) = dp(0, 1) = 1 である。
    • dp(i,j)=k0dp(i1,0)+k1dp(i1,1)dp(i, j) = k_0 * dp(i - 1, 0) + k_1 * dp(i - 1, 1)
      と表すことができ, Si1S_{i - 1}jjの値に応じて係数k0,k1k_0, k_1を求めればよい。
    • 例えば, Si1=’OR’,j=1S_{i - 1} = \text{'OR'}, j = 1のときは,
      yi1=0のときyi1orxi=1y_{i-1} = 0 \text{のとき} \rightarrow y_{i-1} \text{or} x_i = 1となるxix_i11通り
      yi1=1のときyi1orxi=1y_{i-1} = 1 \text{のとき} \rightarrow y_{i-1} \text{or} x_i = 1となるxix_i22通り
      よって, k0=1,k1=2k_0 = 1, k_1 = 2である。
    import sys
    sys.setrecursionlimit(10 ** 6)
    
    
    def dfs(i, j):
        global N
        if (i, j) not in memo:
            if i == 0:
                ret = 1
            else:
                zero, one = dfs(i - 1, 0), dfs(i - 1, 1)
                if j == 0:
                    if P[i - 1] == 'AND':
                        ret = one + 2 * zero
                    else:
                        ret = zero
                else:
                    if P[i - 1] == 'AND':
                        ret = one
                    else:
                        ret = 2 * one + zero
            memo[(i, j)] = ret
        return memo[(i, j)]
    
    
    N = int(input())
    P = [input() for _ in range(N)]
    memo = {}
    ans = dfs(N, 1)
    print(ans)

    E - Rotate and Flip

    行列計算があったのでNumpyを使って実装したら4問ほどTLETLE
    Pypyに書き直す時間はなく撃沈。もったいなかった…
    次の機会に向けて行列まわりのライブラリを作っておこうかな

    • 各操作は以下のように行列で表すことができる。
      操作11: (010100001)\begin{pmatrix}0&1&0 \\ -1&0&0 \\ 0&0&1 \end{pmatrix}, 操作22: (010100001)\begin{pmatrix}0&-1&0 \\ 1&0&0 \\ 0&0&1 \end{pmatrix}
      操作33: (102p010001)\begin{pmatrix}-1&0&2p \\ 0&1&0 \\ 0&0&1 \end{pmatrix}, 操作44: (100012p001)\begin{pmatrix}1&0&0 \\ 0&-1&2p \\ 0&0&1 \end{pmatrix}
    • Ti:i回目までの操作を表す行列T_i: i\text{回目までの操作を表す行列}とする。
      Ti=opiTi1T_{i} = op_i \cdot T_{i - 1}
      によりTiT_iを事前計算しておく。
    • すると点(x,y)(x, y)ii回目の操作後の座標(xi,yi)(x_i, y_i)は以下の式により求められる。
      (xiyi1)=Ti(xy1)\begin{pmatrix}x_i \\ y_i \\ 1 \end{pmatrix} = T_i \cdot \begin{pmatrix}x \\ y \\ 1 \end{pmatrix}
    import sys
    
    
    def mul(S, sizeS, T, sizeT):
        ''' 行列積 S @ T を計算する
        S, T: 1次元行列
        sizeS, sizeT: [row数, col数]
    
        Sc == Tr 必須
    
        Returns: [Sr, Tc]の1次元行列
        '''
        Sr, Sc, Tr, Tc = *sizeS, *sizeT
        N = Sr * Tc
        ret = [0] * (N)
        for i in range(N):
            x, y = divmod(i, Tc)
            L = S[Sc * x: Sc * (x + 1)]
            R = [T[Tc * j + y] for j in range(Tr)]
            tmp = sum(a * b for a, b in zip(L, R))
            ret[i] = tmp
        return ret
    
    
    N = int(input())
    P = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    M = int(input())
    OP = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
    Q = int(input())
    query = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
    
    op1 = [0, 1, 0, -1, 0, 0, 0, 0, 1]
    op2 = [0, -1, 0, 1, 0, 0, 0, 0, 1]
    op3 = [-1, 0, 0, 0, 1, 0, 0, 0, 1]  # op3[2]に2pが入る
    op4 = [1, 0, 0, 0, -1, 0, 0, 0, 1]  # op4[5]に2pが入る
    
    three = (3, 3)
    one = (3, 1)
    T = [None] * (M + 1)
    T[0] = [1, 0, 0, 0, 1, 0, 0, 0, 1]
    for i, op in enumerate(OP):
        j = op[0]
        if j == 1:
            S = op1
        elif j == 2:
            S = op2
        elif j == 3:
            S = op3
            S[2] = 2 * op[1]
        else:
            S = op4
            S[5] = 2 * op[1]
        T[i + 1] = mul(S, three, T[i], three)
    
    for a, b in query:
        b -= 1
        z = P[b] + [1]
        tmp = mul(T[a], three, z, one)
        print(tmp[0], tmp[1])

    F - Sugoroku2

    解説AC。

    考え方は以下の通り。

    • dp[i]:iマス目からスタートした時のルーレットを回す回数の期待値dp[i]: i\text{マス目からスタートした時のルーレットを回す回数の期待値} とおく。
    • 遷移は以下の式で表すことができる。
      dp[N]=0dp[N] = 0
      dp[i]={j=1Mdp[i+j]M+1(通常マス)dp[0](振り出しマス)dp[i] = \begin{cases} \sum_{j=1}^M \frac{dp[i + j]}{M} + 1 & (\text{通常マス}) & \cdots \text{①} \\ dp[0] & (\text{振り出しマス}) & \cdots \text{②} \end{cases}
    • ここで、dp[0]dp[0]を求めるのにdp[0]dp[0]の値が必要、という状態になり自己循環に陥ってしまう。
    • そこで、dp[0]=xdp[0] = x と置くと計算ができる。これは\text{①}の式が必ずax+bax + b という11次式の形となるため、最終的に以下の方程式を解けばよいからである。
      dp[0]=ax+bx=ax+bx=b1a\begin{aligned} & dp[0] &= ax + b \\ \Leftrightarrow & x &= ax + b \\ \Leftrightarrow & x &= \frac{b}{1 - a} \end{aligned}
    • xxと置く」って、どうやってコーディングするの?と疑問をもつかもしれないが、Pythonであればax+bax + ba,ba, bをプロパティにもつクラスを作ればよい。
      (a1x+b1)+(a2x+b2) (a1,b1)+(a2,b2)=(a1+a2,b1+b2)(a_1x + b_1) + (a_2x + b_2) \rightarrow (a_1, b_1) + (a_2, b_2) = (a_1 + a_2, b_1 + b_2)
    class f():
        '''
        ax + b を表すクラス
        和・差およびスカラー除算を定義する
        '''
        def __init__(self, a, b):
            self.a = a
            self.b = b
    
        def __add__(self, other):
            return f(self.a + other.a, self.b + other.b)
    
        def __sub__(self, other):
            return f(self.a - other.a, self.b - other.b)
        
        def __truediv__(self, value):
            return f(self.a / value, self.b / value)
    
    
    N, M, K = map(int, input().split())
    A = [0] * (N + 1)
    for a in map(int, input().split()):
        A[a] = 1
    
    x = f(1, 0)     # 1 * x + 0
    zero = f(0, 0)  # 0 * x + 0
    one = f(0, 1)   # 0 * x + 1
    dp = [zero] * (N + M + 1)
    S = zero  # dp[i] + dp[i + 1] + ... + dp[i + M] の累積和
    for i in range(N - 1, -1, -1):
        if A[i]:
            dp[i] = x
        else:
            dp[i] = S / M + one
        S += dp[i]
        S -= dp[i + M]
    
    a, b = dp[0].a, dp[0].b
    if a + pow(10, -6) > 1:  # a == 1 のときはゴール不可。誤差を考慮して不等式で実装する。
        print(-1)
    else:
        print(b / (1 - a))

    まとめ

    マジで落ち込む。。。