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

    【Python】エイシング プログラミング コンテスト 2020 解説

    リアルタイムでは参加できなかったので, バチャコンで参加. 結果はぎりぎり4完. コンテストであれば1400位くらいの成績でしょうか.
    Pythonでの解答・解説を載せます.

    疑問点・不明点など, ページ最下部のお問合せもしくはTwitterからメッセージいただければ回答いたします.

    A - Number of Multiples

    全探索してもいいし, 一発で求めることも可能.

    L, R, d = map(int, input().split())
    print(R // d - L // d + (L % d == 0))  # Lがdの倍数のケースを考慮

    B - An Odd Problem

    下記の性質を利用する.

    • マスの番号とマスに書かれた整数がともに奇数 \Leftrightarrow マスの番号 * マス書かれた整数 が奇数
    N = int(input())
    A = map(int, input().split())
    cnt = 0
    for i, a in enumerate(A):
        if ((i + 1) * a) % 2:
            cnt += 1
    print(cnt)

    Pythonicに書くなら、リスト内包表記を使ってこんな感じか.

    N = int(input())
    A = map(int, input().split())
    print(sum(((i + 1) * a) % 2 for i, a in enumerate(A)))

    C - XYZ Triplets

    1x,y,zN1\leq x, y, z\leq \sqrt{N} の範囲で全探索する.

    僕の回答では若干遠回りして計算量を減らしている.
    (こんなことをしなくてもACできるのでやらないほうがよい.)

    x,y,zx, y, zの対称性に注目して, xyzx\leq y\leq zの条件で探索する.

    from math import sqrt
    
    
    # x, y, zの組合せ数を算出する
    # 例えば (x, y, z) = (1, 1, 3)だったら, 3通りのバリエーションが存在する.
    # (1, 1, 3), (1, 3, 1), (3, 1, 1)
    def check(i, j, k):
        cnt = set([i, j, k])
        if len(cnt) == 1:
            return 1
        if len(cnt) == 2:
            return 3
        if len(cnt) == 3:
            return 6
    
    
    N = int(input())
    ans = [0] * N
    
    R = int(sqrt(N))
    for x in range(1, R + 1):
        for y in range(x, R + 1):
            for z in range(y, R + 1):
                f = (x ** 2) + (y ** 2) + (z ** 2) + (x * y) + (y * z) + (z * x)
                if f <= N:
                    ans[f - 1] += check(x, y, z)
    print(*ans, sep='\n')

    D - Anything Goes to Zero

    ここ最近のDの中では一番難しかった.

    この問題の解法は、大雑把に言えば以下の2つのパートに別れる.

    1. X=2200000X = 2^{200000} (10進表記)のとき, popcount(X)popcount(X)を求めよ.
    2. X=100000X = 100000 (10進表記)のとき, f(X)f(X)を求めよ.

    1,21, 2で本質的には同じ関数の値を算出するにも関わらず、両者で異なるアルゴリズムが求められる. これが難しさの主な要因だろう.

    まず1について.

    • XXがとてつもなく大きいため, 単純な割り算すらできない.
    • そこで, X=x020+x121+x222++x22000002200000X = x_0*2^0 + x_1*2^1 + x_2 * 2^2+\cdots+x_{2^{200000}}*2^{200000} に注目して, popcount(X)popcount(X)を算出する. (xix_iは2進表示での下位ii番目の数 0or10 or 1 )
    • 11の個数をeeとすると, popcount(X)=Xmode=(x020)mode+(x121)mode+(x222)mode+popcount(X) = X \bmod e = (x_0*2^0) \bmod e + (x_1*2^1) \bmod e+ (x_2 * 2^2) \bmod e + \cdots となる. これはO(N)\mathcal{O}(N)で求められる.
    • この考え方を拡張して, popcount(X1),popcount(X2),popcount(X_1), popcount(X_2), \dotsを求めるために, Xmod(e1)X \bmod {(e-1)}, Xmod(e+1)X \bmod {(e+1)} を事前に算出しておく. (累積和と似た考え方)

    2について.

    • 定義通りに算出すればOK.
    • メモ化再帰を使うとさらに高速に.
    from collections import Counter
    import sys
    sys.setrecursionlimit(10 ** 6)
    
    
    # 解法パート2
    def dfs(n):
        if memo[n] >= 0:
            rst = memo[n]
        else:
            tmp = n
            one = 0
            while tmp > 0:
                one += tmp & 1
                tmp >>= 1
            m = n % one
            rst = 1 if m == 0 else 1 + dfs(m)
            memo[n] = rst
        return rst
    
    
    N = int(input())
    X = list(map(int, list(input())))
    one = Counter(X)[1]
    
    # 解法パート1の前処理.
    # Xがオール0のとき, 1が一つしか含まれないとき、を場合分けする
    if one > 1:
        Sm = 0
        mm = one - 1
        tm = 1
        for i in range(N - 1, -1, -1):
            tm %= mm
            if X[i] == 1:
                Sm += tm
                Sm %= mm
            tm *= 2
    
    Sp = 0
    mp = one + 1
    tp = 1
    for i in range(N - 1, -1, -1):
        tp %= mp
        if X[i] == 1:
            Sp += tp
            Sp %= mp
        tp *= 2
    
    
    memo = [-1] * (2 * (10 ** 5) + 10)
    memo[0] = 0
    
    
    # f(Xi)を求めていく処理
    # 解法パート1とパート2を順に適用する
    for i in range(N):
        # 解法パート1
        if X[i] == 0:
            m = (Sp + pow(2, N - 1 - i, mp)) % mp
        elif one > 1:
            m = (Sm - pow(2, N - 1 - i, mm)) % mm
        else:  # X[i] == 1 かつ 全体で1が一つしかない 場合 は必ず0になる
            print(0)
            continue
        cnt = 1
    
        # 解法パート2
        cnt += dfs(m)
        print(cnt)

    E - Camel Train

    考察の難易度は低いが, 時間内に解くとなるとかなり難しそう.

    考え方は以下の通り. 想定解答とは逆の考え方(点数を極力減らさない並べ方)をした.

    まず、ラクダを3つのグループに分ける. 1: L>RL > R, 2: L<RL < R, 3: L==RL == R.
    グループ3はどこに配置しても答えは変わらないため考察不要.
    以下、グループ1について考察する.

    • グループ1のラクダは極力左側に配置してあげると点数が高くなる. 最大で iLi\sum_{i} L_iとなる可能性があるが, 実際はKiK_iより右側に配置されたラクダの分、点数が LiRiL_i - R_i だけ小さくなる.
    • では、どのような場合にKiK_iより右側に配置されるラクダが存在するのか?
    • 例えば、{Ki=1K_i = 1のラクダが22頭}の場合、どちらか1頭はKiK_iより右側に配置される. {Ki=1K_i=122頭, Ki=2K_i=211頭}の場合は3頭中の1頭, {Ki=1K_i=122頭, Ki=2K_i=222頭}の場合は4頭中の2頭, etc…
    • つまり, KiK_i以下のラクダがnn頭存在する場合, nin - i頭は右側に配置されるのである.
    • では次に、どのラクダを右側に配置するべきか?
    • これは点数の減少幅がもっとも小さいラクダ、すなわち LiRiL_i - R_i が小さいラクダを右側に配置すべきである.
    • グループ2についても同様に, 極力右側に配置して, どのラクダが左側に溢れてしまうかを考える.
    import sys
    from heapq import heappop, heappush
    
    
    T = int(input())
    for t in range(T):
        N = int(input())
        left, right = [], []  # left: グループ1, right: グループ2
        ans = 0
        for i in range(N):
            K, L, R = map(int, sys.stdin.readline().split())
            if L > R:  # グループ1
                ans += L
                left.append((K, L - R))
            elif L < R:  # グループ2
                ans += R
                right.append((K, R - L))
            else:  # グループ3
                ans += L
        # グループ1について計算
        pool = []  # Kiより左側に配置されるラクダの集合. L-Rの小さい順に格納される.
        left.sort()  #Kiの順にソート
        cur = 0
        pos = 1  # 左からpos番目以下のラクダについて計算
        while cur < len(left):
            # Ki <= pos のラクダをすべてpoolに格納する 
            while cur < len(left) and left[cur][0] == pos:
                k, d = left[cur]
                heappush(pool, d)
                cur += 1
    
            # pool内のラクダがpos頭を超えている場合, 一部のラクダは右側に配置される. その分だけ答えが減る.
            while len(pool) > pos:
                d = heappop(pool)
                ans -= d  # 答えがLi-Riだけ小さくなる
            pos += 1
                
        # グループ2について計算
        pool = []
        pos = N
        right.sort(reverse=True)
        cur = 0
        while cur < len(right):
            while cur < len(right) and right[cur][0] == pos:
                k, d = right[cur]
                heappush(pool, d)
                cur += 1
            while len(pool) > N - pos:
                d = heappop(pool)
                ans -= d
            pos -= 1
    
        print(ans)

    F - Two Snuke

    TBA