0件ヒットしました
    2021-03-06

    【Python】ABC194 解説

    ABC194に参加しました. 結果は55477477位パフォーマンス18451845!!.
    今回はA~C問題がいつもより難しくてびっくりしました.

    ABC194_ranking

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

    A - I Scream

    問題文が難しすぎる…
    きちんと読めれば、題意のままに実装するだけ。

    A, B = map(int, input().split())
    C = A + B
    if C >= 15 and B >= 8:
        ans = 1
    elif C >= 10 and B >= 3:
        ans = 2
    elif C >= 3:
        ans = 3
    else:
        ans = 4
    print(ans)

    B - Job Assignment

    仕事AAと仕事BBに割り当てる従業員の組み合せを全探索する。
    同一人物を割り当てたときは終了時間の算出式が変わる。

    N = int(input())
    AB = [tuple(map(int, input().split())) for _ in range(N)]
    
    ans = float('inf')
    for i in range(N):
        ai, bi = AB[i]
        for j in range(N):
            aj, bj = AB[j]
            time = ai + bj if i == j else max(ai, bj)
            ans = min(ans, time)
    print(ans)

    C - Squared Error

    難しくてびっくりしちゃった。
    DやEよりも時間を要した。。

    考え方は以下。

    • {Ai}\{A_i\}を左から順に見ていく。
    • C[n]=既に登場した数値C[n] = \text{既に登場した数値} nの個数 \text{の個数} とすると、すべてのnnについてC[n](Ain)2C[n] * (A_i - n)^2 を計算すればよい。
    • 計算量は、AiA_iVV種類存在するときO(NV)6107\mathcal{O}(NV) \simeq 6 * 10^7程度。
    from collections import Counter
    
    
    N = int(input())
    A = map(int, input().split())
    C = Counter()
    ans = 0
    for a in A:
        for k, v in C.items():
            ans += v * ((k - a) ** 2)
        C[a] += 1
    print(ans)

    D - Journey

    確率漸化式の典型のような問題。

    • 連結成分数がnnのときの期待値をfnf_nとおく。求めたいのはf1f_1であり、fN=0f_N = 0である。
    • nn個が連結しているとき、次の操作で連結済みの頂点が選ばれる確率をPSP_S、未連結の頂点が選ばれる確率をPTP_Tとすると、これらは以下のように求められる。

    PS=nNP_S = \frac{n}{N}
    PT=NnNP_T = \frac{N - n}{N}

    • そして、fnf_nfn+1f_{n + 1}の間には以下の漸化式が成り立つ。

    fn=(fn+1)PS+(fn+1+1)PTf_n = (f_n + 1)P_S + (f_{n + 1} + 1)P_T \cdots \text{①}
    右辺第一項は連結済みの頂点を選んだ場合、第二項は未連結の頂点を選んだ場合である。

    • \text{①}式を変形すると、以下の式となるため、n=N1,,1n = N - 1, \dots, 1を順に計算していけばよい。

    fn=PS+(fn+1+1)PT1PSf_n = \frac{P_S + (f_{n+1} + 1)P_T}{1 - P_S}

    N = int(input())
    f = 0
    for n in range(N - 1, 0, -1):
        Ps, Pt = n / N, (N - n) / N
        f = (Ps + (f + 1) * Pt) / (1 - Ps)
    print(f)

    E - Mex Min

    Segment Treeを利用して解いた。
    実行時間制限が4sec4secなんだね。。他にもっと厳しい問題があるので、そっちでも緩和お願いします。

    • 数列AAを左から順に見ていく。
    • Bi={Ai,Ai+1,,Ai+M1}B_i = \{A_i, A_{i + 1}, \dots , A_{i + M - 1}\}とする。
    • まず、mex(Bi)mex(B_i)を求めるには、以下の条件を満たす長さNNの数列{Ci}\{C_i\}の要素の最小値を求めれば良い。

    数値jjBiB_iに存在するとき、Cj=INFC_j = INF
    存在しない時、 Cj=jC_j = j
    (ただし, INF=max(A)+1INF = max(A) + 1)

    • Seg木を用いればこの問合せ処理はO(logN)\mathcal{O}(\log{N})である。
    • そして、mex(Bi+1)mex(B_{i + 1})については、Seg木を更新すればよい。更新内容はAiA_iを削除・Ai+MA_{i + M}

    を追加である。削除については、Counterを利用してBi+1B_{i+1}中の要素数が00になるかどうかを管理する。

    from collections import Counter
    
    
    class SegmentTree():
      """割愛
      """
    
    
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    INF = max(A) + 1
    C = Counter()  # C: {Ai, ..., A_i+M-1} に含まれる数値とその個数
    st = SegmentTree([i for i in range(N)], min, INF)
    
    # i = 0 での初期化処理
    for i in range(M):
        a = A[i]
        C[a] += 1
        st.update(a, INF)  # 数値が存在するときは INF として更新
    ans = st.get(0, N)  # i = 0 のときのmex
    for i in range(1, N - M + 1):  # i = 1, ..., N-M+1 まで順に見ていく
        a_del = A[i - 1]  # a_del: 削除する数値
        C[a_del] -= 1
        if C[a_del] == 0:  # カウントが0のときのみseg木を更新
            st.update(a_del, a_del)
        a_add = A[i + M - 1]  # a_add: 追加する数値
        C[a_add] += 1
        if C[a_add] == 1:  # 新しく追加された場合のみseg木を更新。ちょっとした高速化。
            st.update(a_add, INF)
        ans = min(ans, st.get(0, N))
    print(ans)

    ## F - Digits Paradise in Hexadecimal 解説AC。

    桁DPは検討したけど、計算量を減らす工夫がまったく思いつかなかった。。。
    思いついたとしても、例外の考慮事項が多すぎて実装がかなり難しい。

    MOD = 10 ** 9 + 7
    N, K = input().split()
    K = int(K)
    L = len(N)
    
    '''
    dp[i][j]: 以下の条件を全て満たす数値の数
        - N未満
        - 「上位0~i桁がすべて0」ではない
    '''
    dp = [[0] * (K + 1) for _ in range(L + 1)]
    C = set()
    for i, n in enumerate(N):
        crt, nxt = dp[i], dp[i + 1]
        n = int(n, 16)
        # dpテーブル内での遷移
        for j in range(K + 1):
            here = crt[j]
            # 既に登場したj種類の数字を使う場合
            nxt[j] += here * j
            nxt[j] %= MOD
            # これまでに登場していない数字を使う場合
            if j < K:
                nxt[j + 1] += here * (16 - j)
                nxt[j + 1] %= MOD
        # 「i - 1桁目 まで N と同じ」数値の考慮
        for j in range(i == 0, n):
            nj = len(C) + (j not in C)
            if nj <= K:
                nxt[nj] += 1
        # i - 1 桁目まで all 0 の数値の考慮
        if i > 0:
            nxt[1] += 15
        C.add(n)
    cnt = dp[L][K]
    cnt += (len(set(N)) == K)  # N自身の考慮
    print(cnt % MOD)

    まとめ

    早解きに助けられた!