Pythonでエイシングプログラミングコンテスト2020

エイシングプログラミングコンテスト2020に参加しました

普段のABCよりD、Eが重かったですね。本番はD完、Eは解説AC。

A - Number of Multiples

N以下のdの倍数はN//dなので、R//dから(L-1)//dを引く。
開始1分でAC。

L, R, d = map(int, input().split())
print(R//d - (L-1)//d)

B - An Odd Problem

enumerate(A)でリストのindex(i)と中身(a = A[i])を同時に引っ張ってこれる。
iが0始まりであることに注意して、偶奇をチェックすればOK。
開始3分でAC。

    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    for i, a in enumerate(A):
        if i % 2 == 0 and a % 2 == 1:
            ans += 1
    print(ans)

C - XYZ Triplets

二次方程式を解きにかかるのは無理筋なので全探索でカウントしたくなるが、愚直に $x, y, z$ を $10^4$ まで全探索すると $10^{12}$ 回の計算量でTLEとなる。
$x$, $y$ に0を代入すると $z^2=n$ となるので、この制約上では $z$ は高々 $10^2$ である。$x$, $y$ についても同様。
$x$, $y$, $z$ を1から100まで全探索して答えの数字ごとにカウントしてやると $10^6$ 回の計算量で充分間に合う。
102にしているのは念のため。(解説でも105までやっていた)
開始7分半でAC。

    N = int(input())
    A = [0] * (N+1)
    for x in range(1, 102):
        for y in range(1, 102):
            for z in range(1, 102):
                t = x*x + y*y + z*z + x*y + y*z + z*x
                if t <= N:
                    A[t] += 1
    for i in range(1, N+1):
        print(A[i])

D - Anything Goes to Zero

考えたこと

• まずpythonでの整数Nに対してのpopcountはどうするか → bin(N).count("1") でよさそう。

• 最初の $X$ は最大 $2^{2×10^5}$ とかいう巨大な数なのでいくらpythonの整数に限界がないとはいえ時間を食う。しかし1回でも操作すればN以下まで落ちて急激に小さくなるので、1回目の操作をいかに凌ぐかがキモ。

• 桁ごとに剰余計算すればよさそう。各 $popcount(X_i)$ は $popcount(X) ± 1$のどちらかになるので、2通りの各桁ごとの剰余計算を前処理しておく。$2^N$ の剰余を高速に計算したいときは $pow(base, exp, mod)$ が使える。

• ※$popcount(X) - 1$ が0のときがコーナーケース！bit反転後に0になるものは0回の操作で終了する！

• i番目のbitを反転したものに対して毎回足し合わせると同じ計算を何度もしてしまうので、Xの剰余計算のみ行い、反転した分だけ差し引きしてやることにする。

• 1回計算できたら残りはwhileで回してもすぐ終わる大きさに落ちる。

作業が捉えにくかったり0除算のコーナーケースがあったり1回だけ工夫したりと中々厄介な問題。
開始45分でAC。

    N = int(input())
    X = input()
    X_pop = X.count("1")
    X_plus = X_pop + 1
    X_minus = X_pop - 1
    # 前処理
    RP = [pow(2, i, X_plus) for i in range(N+1)]
    if X_minus > 0:
        RM = [pow(2, i, X_minus) for i in range(N+1)]
    else:
        RM = [0] * (N+1)
 
    # Xそのものの剰余計算
    X = X[::-1]
    rem_p = 0
    rem_m = 0
    for i in range(N):
        if X[i] == "1":
            rem_p += RP[i]
            rem_m += RM[i]

    # 反転時の差分を計算する
    for i in range(N-1, -1, -1):
        if X[i] == "0":
            tmp = (rem_p + RP[i]) % X_plus
        elif X_minus >= 1:
            tmp = (rem_m - RM[i]) % X_minus
        else: # popcount(X_i)が0のときは0回の操作で終了
            print(0)
            continue
        ans = 1
        # 1回目を乗り越えたらあとはwhileでぶん回せばOK
        while tmp > 0:
            tmp = tmp % bin(tmp).count("1")
            ans += 1
        print(ans)

E - Camel Train

本番いいところまで行った気がするけど解けず、解説AC。

本番中に考えたこと

• TとNの条件から $O(NlogN)$ くらいか？sortなりheapqなり駆使して解けそう。
• 各ラクダは左にいる方が嬉しいもの(Lラクダ)と右のほうが嬉しいもの(Rラクダ)がいる。一緒に扱うと面倒なので分けて考えられないか？
• あるLラクダよりもさらに左にRラクダがいる場合、2つを入れ替えると必ず得するので、Lラクダは全部左、Rラクダは全部右に寄せてそれぞれで詰めていけばいけそう！
• 各ラクダのLとRのうち小さいほうは必ず得点するので先に計算しておき(base)、嬉しい範囲に入れたときにボーナスで$|L-R|$(=diff)が貰え、そうでないときは0とすれば変数が1つ落ちる。
• Lラクダの詰め方について考える。端から貪欲で一番条件の厳しい(Kの小さくてdiffの大きい)ものを取って確定させていけばいいかと思いきや、[K, diff] が [1, 1], [2, 100], [2, 100] みたいなケースで101点しか取れないので良くない。
• じゃあどうやって詰めていくんだ…？heapqをこねくり回すも断念。

解説の解説

• 左から1列の最適化→左から2列の最適化→…→全部の最適化、というように見る範囲を広げていく。新しく広がった列(i列目)が嬉しい範囲の右端であるようなLラクダ(K=i)をまとめてheapqに追加し、溢れた分をdiffの少ない順にpopしていけば常に最適状態を保てる。
• 例)[1, 1], [2, 100], [2, 100]のケースだと、i=1で[1, 1]を追加、i=2で[2, 100], [2, 100]を追加して2列から溢れた[1, 1]を弾き出すと[2, 100], [2, 100]が残り最適状態になる。

    import heapq as hq

    T = int(input())
    for _ in range(T):
        N = int(input())
        camels = [list(map(int, input().split())) for _ in range(N)]
        base = 0
        camels_L = [[] for _ in range(N+1)]
        camels_R = [[] for _ in range(N+1)]
        # 左から詰めるラクダと右から詰めるラクダを仕分ける
        for camel in camels:
            if camel[1] >= camel[2]:
                camels_L[camel[0]].append(camel[1] - camel[2])
                base += camel[2] # LとRの低いほうを加算
            else:
                # Rラクダは右から何列目かを考えるのでN - camel[0]と反転する
                camels_R[N - camel[0]].append(camel[2] - camel[1])
                base += camel[1] # LとRの低いほうを加算

        diff = 0

        # Lラクダについて考える
        heap_camels = []
        hq.heapify(heap_camels)
        for i in range(1, N+1):
            # 左からi番目までが限度のラクダをまとめて追加
            for camel in camels_L[i]:
                hq.heappush(heap_camels, camel)
            # 左からi番目までに入りきらない場合に低いものから除外
            while len(heap_camels) > i:
                hq.heappop(heap_camels)
        # heapqに残ったものがすべての条件を満たしうれしさが最大
        diff += sum(heap_camels)

        # Rラクダについても同様
        heap_camels = []
        hq.heapify(heap_camels)
        for i in range(1, N+1):
            for camel in camels_R[i]:
                hq.heappush(heap_camels, camel)
            while len(heap_camels) > i:
                hq.heappop(heap_camels)
        diff += sum(heap_camels)
        print(diff + base)

色んな解説を見たりしてなんとか自分の言葉になった感じがある。
Fは分かりません。お疲れさまでした。