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

    【Python】ABC195 パナソニックプログラミングコンテスト 解説

    ABC195に参加しました. 結果は4411271127位パフォーマンス14061406.
    難しかったですね。。

    ABC195_ranking

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

    A - Health M Death

    やはりA問題はこれくらいシンプルじゃないと。

    M, H = map(int, input().split())
    print('Yes' if H % M == 0 else 'No')

    B - Many Oranges

    過去最難のBB問題、ですよね?
    WWがキログラムであることも地味に難易度を上げている。

    A, B, W = map(int, input().split())
    W *= 1000
    m, M = 1 << 32, 0
    for i in range(pow(10, 6) + 1):
        if A * i <= W <= B * i:
            m = min(m, i)
            M = max(M, i)
    if M > 0:
        print(m, M)
    else:
        print('UNSATISFIABLE')

    C - Comma

    難しくてびっくりしちゃった。

    • 桁数ごとに存在する数の個数をカウントする。高々1515桁なので十分に間に合う
    def f(k, N):
        '''N以下のk桁の数の個数を返す
        '''
        M = min(pow(10, k), N + 1)
        return M - pow(10, k - 1)
    
    
    N = input()
    L = len(N)
    N = int(N)
    ans = 0
    for i in range(1, 6):  # コンマをi個持つとき
        for k in range(3 * i + 1, 3 * i + 4):  # その数は 3*i+1桁 ~ 3*i+3桁の数である
            if k <= L:  # 桁数はNの桁数以下でなければならない
                cnt = f(k, N)  # cnt: N以下のk桁の数の個数
                ans += cnt * i
    print(ans)

    D - Shipping Center

    難しそうな雰囲気を出しつつ、実は愚直に実装するだけで解ける問題。
    計算量の見積り力が問われる問題かな?

    • 価値の大きな荷物から順に、使える箱のなかで大きさ最小の箱に入れる。
    import sys
    from operator import itemgetter
    
    
    N, M, Q = map(int, input().split())
    WV = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
    X = list(map(int, input().split()))
    query = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
    
    WV.sort(key=itemgetter(1), reverse=True)  # 荷物を価値の大きな順にソートしておく
    
    for L, R in query:
        L -= 1; R -= 1
        box = sorted(X[:L] + X[R + 1:])  # box: 使える箱。小さい順にソートする
        done = [1] * len(box)  # done[i]: i番目の箱が使えるかどうか
        ans = 0
        for w, v in WV:
            for i, x in enumerate(box):  # 大きさの小さい箱から順に格納可能かをチェックする
                if done[i] and w <= x:
                    done[i] = 0
                    ans += v
                    break
        print(ans)

    E - Lucky 7 Battle

    解説AC。

    • nnラウンド目が終了したときの数TT77で割った余りをrnr_{n}とする。
    • nnラウンド目がTakahashi君の手番のとき、Takahashi君は10rn110r_{n-1} もしくは 10rn1+Sn10r_{n-1} + S_n を選び、rnr_nを自分の有利な数にしようと試みる。
    • 一方で、手番がAoki君のとき、Aoki君はrnr_nがTakahashi君の不利な数になるように選ぶ。しかし 10rn110r_{n-1}10rn1+Sn10r_{n-1} + S_n のどちらを選んでも最終的にTakahashi君が勝つときは、どうしようもない。(これをどうしようもない操作とでも呼ぼう)。
    • したがって、Takahashi君の作為的な操作Aoki君のどうしようもない操作のみで77の倍数を作ることができればTakahashi君の勝ち、そうでなければAoki君の勝ちである。
    N = int(input())
    S = list(map(int, input()))
    X = input()
    MOD = 7
    dp = [[0] * MOD for _ in range(N + 1)]  # dp[i][r]: iラウンド目が終了時点で余りrのときTakahshi君は勝てるか?
    dp[N][0] = 1  # 全ラウンド終了時点でr=0であればTakahashi君の勝ち
    for i in range(N - 1, -1, -1):
        s = S[i]
        if X[i] == 'T':  # Takahashi君の手番のとき
            for j in range(MOD):
                J = (j * 10) % MOD
                dp[i][j] = (dp[i + 1][J] | dp[i + 1][(J + s) % MOD])  # どちらかでも勝てればよい
        else:  # Aoki君の手番のとき
            for j in range(MOD):
                J = (j * 10) % MOD
                dp[i][j] = (dp[i + 1][J] & dp[i + 1][(J + s) % MOD])  # どうしようもない操作のときのみTakahashi君の勝ち
    print('Takahashi' if dp[0][0] else 'Aoki')

    ## F - Coprime Present 解説AC。

    解き方の検討すらつかなかった。。
    gcd(n,m)<=AB<=72gcd(n, m) <= A - B <= 72 という制約に気付けるかどうか。

    まず、基本的な考察は以下。

    • まず、「どの相違なる2枚についても互いに素」「どの相違なる2枚についても共通する素因数を持たない」\text{「どの相違なる2枚についても互いに素」} \Leftrightarrow \text{「どの相違なる2枚についても共通する素因数を持たない」} \cdots \text{①} と言い換えられる。
    • したがって、共通する素因数を持たないようにカードを選んでいけばよい。
    • ここで AB72A - B \leq 72 より、共通し得る素因数は7272以下の素数のみである。7272より大きい素数は無視してよい。

    (なぜなら、例えば7373を共通の素因数に持つ二つの異なる数の差は必ず7373以上となるためである。)

    • 7272以下の素数は2020個しか存在しないため、状態数は高々2201062^{20} \simeq 10^6である。bitDPにより解くことができる。

    以下、具体的なbitDPでの解き方。

    • Pk=k番目の素数P_k=k\text{番目の素数}とする。(00-index、つまりP0=2P_0=2とする。)
    • numi=A+ik番目の素数を因数にもつかどうかを表すbit集合」num_i = \text{「}A+i \text{が}k\text{番目の素数を因数にもつかどうかを表すbit集合」}とする。

    例) 2,52, 5を素因数に持つ numi=101(2)\rightarrow num_i = 101_{(2)}

    • dp(i,bit)=i番目までのカードを見たとき, 既に選んだカードに含まれる素因数の状態がbitとなっている場合の数dp(i, bit) = i\text{番目までのカードを見たとき, 既に選んだカードに含まれる素因数の状態が} bit となっている場合の数 とする。
    • dpdpの遷移は、以下のとおり。

    dp(i,bit)=dp(i1,bit)(i番目のカードを選ばない)+dp(i1,bitnumi)(i番目のカードを選ぶ. numibitのときのみ.)\begin{aligned} dp(i, bit) &= dp(i - 1, bit) &\cdots \text{(i番目のカードを選ばない)}\\ &+ dp(i - 1, bit - num_i) &\cdots \text{(i番目のカードを選ぶ. } num_i \subseteq bit \text{のときのみ.)} \end{aligned}

    A, B = map(int, input().split())
    # primes[k]: k番目の素数
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
    L = len(primes)
    N = B - A + 1  # N: カードの数
    
    # num[i]: i番目のカードがk番目の素数をもつとき num[i] |= (1 << k)
    num = [0] * N
    for i in range(N):
        num[i] = sum((1 << j) for j in range(L) if (A + i) % primes[j] == 0)
    
    # dp配列を使いまわす実装
    dp = [0] * (1 << L)
    dp[0] = 1
    for i, n in enumerate(num):
        for bit in range((1 << L) - 1, -1, -1):  # dp配列を使いまわすためbitの大きい方から計算する
            if (bit & n) == n:  # n が bit に含まれるとき
                dp[bit] += dp[bit ^ n]
    print(sum(dp))
    

    まとめ

    爆死しなくてよかったー