0件ヒットしました
    2020-12-13

    【Python】ABC185 解説

    ABC185に参加しました. 結果はA~D,F5512271227位パフォーマンス13561356.
    E問題以外は普段よりも簡単だったと思います。

    ranking_abc185

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

    A - ABC Preparation

    A1,A2,A3,A4A_1, A_2, A_3, A_4の最小値が答え。
    Pythonであればワンライナーで書ける。

    print(min(map(int, input().split())))

    B - Smartphone Addiction

    各カフェに到着した時出発する時それぞれのバッテリー残量を計算し、一度でも00以下になったら答えはNo

    N, M, T = map(int, input().split())
    C = [tuple(map(int, input().split())) for _ in range(M)]
    C.append((T, T))  # 時刻Tに自宅に到着する 
    
    t = 0  # t: 現在時刻
    battery = N  # battery: バッテリー残量
    res = True # res: 0以下になるかどうか
    for a, b in C:
        battery -= a - t
        res &= (battery > 0)
        battery = min(N, battery + b - a)
        res &= (battery > 0)
        t = b
    ans = 'Yes' if res else 'No'
    print(ans)

    C - Duodecim Ferra

    • この問題は「LL個のボールを1212個の区別された箱に入れる(ただし各箱に最低1個)」の場合の数と等しい。
    • 各箱に最初に1個ずつボールを入れておくことにすれば、「L12L - 12個のボールを1212個の区別された箱に入れる」場合の数となる。
    • すなわち, L12+11C11=L1C11{}_{L - 12 + 11} \mathrm{C}_{11} = {}_{L - 1} \mathrm{C}_{11}
    from math import factorial
    
    
    L = int(input())
    print(factorial(L - 1) // factorial(L - 12) // factorial(11))

    D - Stamp

    • マス目全体をMM個の青マスによってM+1M+1個の領域に分けることができる。
    • 各領域の白マスの個数をBiB_iとする。なお, B0B_0A1A_1の左側の領域、BMB_MAMA_Mの右側の領域である。
    • BiB_iがすべて00のときは, 全体が青色になっているため答えは00
    • BiB_i00以外が含まれているとき, 00を除いた最小値をkkとすると、スタンプの大きさはkkである。
    • そして, 各領域でスタンプを押す回数は Bik\lceil \frac{B_i}{k} \rceil で求めることができる。
    • ただし、M=0M = 0のときは例外で、答えは必ず11である。
    N, M = map(int, input().split())
    A = list(map(lambda x: int(x) - 1, input().split()))
    
    if M == 0:  # M == 0のときは例外
        ans = 1
    else:
        A.sort()
        B = [0] * (M + 1)  # Bi: 各領域の白マスの個数
        B[0] = A[0] - 0
        for i in range(1, M):
            B[i] = A[i] - A[i - 1] - 1
        B[M] = (N - 1) - A[M - 1]
    
        if all(b == 0 for b in B):  # 白マスが存在しない場合は答えは0
            ans = 0
        else:
            k = min(b for b in B if b != 0)  # k: 0を除いたBiの最小値 (= スタンプの大きさ)
            ans = sum((b + k - 1) // k for b in B)
    print(ans)

    E - Sequence Matching

    解説AC。

    最長共通部分文字列(LCS: Longest Common Subsequence)の類題か。

    • dp[i][j]:=dp[i][j] := AAii文字目, BBjj文字目まででA,BA', B'を作った場合のコストの最小値 とする。
    • (i,j)(i, j)では以下の3種類の操作ができる。

    1.Ai,BjA_i, B_jを両方とも残す
    2.AiA_iを消す
    3.BjB_jを消す

    • このとき、それぞれ以下のコストを要する。

    1.Ai==BjA_i == B_jのときは00、そうでないときは11
    2.1文字削除するため11
    3.1文字削除するため11

    • したがって、遷移式は以下のようになる

    1.dp[i][j]dp[i1][j1]+(Aidp[i][j] \leftarrow dp[i - 1][j - 1] + (A_i != Bj)B_j)
    2.dp[i][j]dp[i1][j]+1dp[i][j] \leftarrow dp[i - 1][j] + 1
    3.dp[i][j]dp[i][j1]+1dp[i][j] \leftarrow dp[i][j - 1] + 1

    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    LA = len(A)
    LB = len(B)
    
    INF = float('inf')
    dp = [[INF] * (LB + 1) for _ in range(LA + 1)]
    dp[0][0] = 0
    for i in range(LA + 1):
        for j in range(LB + 1):
            here = dp[i][j]
            if i > 0 and j > 0:
                here = min(here, dp[i - 1][j - 1] + (A[i - 1] != B[j - 1]))
            here = min(here, dp[i - 1][j] + 1)
            here = min(here, dp[i][j - 1] + 1)
            dp[i][j] = here
    print(dp[LA][LB])

    F - Range Xor Query

    過去最易のF問題と思われる。
    これがE問題だったらDifficultyが茶色になってたんじゃないかな。

    単純な「1点更新, 区間取得」のためSegmentTreeで解ける。

    from operator import xor
    import sys
    
    
    class SegmentTree():
        def __init__(self, A, dot, e):
            """
            Parameters
            ----------
            A : list
                対象の配列
            dot :
                Segment function
            e : int
                単位元
            """
            # 省略
        
        def update(self, i, c):
            # 省略
        def get(self, l, r):
            # 省略
    
    
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    st = SegmentTree(A, xor, 0)
    ans = []
    for i in range(Q):
        t, x, y = map(int, sys.stdin.readline().split())
        x -= 1
        if t == 1:
            st.update(x, y)
        else:
            cnt = st.get(x, y + 1)
            ans.append(cnt)
    print(*ans, sep='\n')

    まとめ

    今の実力ではE問題は解けなかったな。。
    最近はコンテスト中に水色Diffが解けることが少なくなってきた。