AISing Programming Contest 2019 参戦記 (D問題)

AISingコン反省会後編です。A-C問題はこちら。

AISing Programming Contest 2019 参戦記 (A-C問題) - アールグレー特売所

D問題 (Nearest Card Game)

from math import ceil
N, Q = map(int, input().split())
A = [int(a) for a in input().split()]
AltTake = [0 for a in range(N)] #i番目から交互に取っていくときの高橋君の点数
GetAll = [0 for a in range(N)] #i番目以上を総取りしたときの点数
AltTake[0], AltTake[1] = A[0], A[1]
GetAll[-1] = A[-1]
BlockList = [0 for i in range(ceil(N/2))] #i番目以上を総取りするために必要なxの最小値
maxBlock = ceil(N/2) #最大でceil(N/2)枚しか総取りすることはできません
 
for i in range(2, N):
    AltTake[i] = A[i] + AltTake[i-2]
for i in reversed(range(N-1)):
    GetAll[i] = GetAll[i+1] + A[i]
for i in range(ceil(N/2) - 1):
        BlockList[-i-1] = (A[-i-2] + A[-2*i - 3]) // 2 + 1
 
def BSearch(x, L): #二分探索
    left, right = 0, len(L)
    while right - left > 1:
        mid = (right + left)//2
        if L[mid] > x:
            right = mid
        else:
            left = mid
    return left
 
for _ in range(Q):
    block = maxBlock - BSearch(int(input()), BlockList) #上からblock枚総取りできる
    if block == maxBlock: print(GetAll[-block])
    else: print(GetAll[-block] + AltTake[N - block * 2 -1])

ある条件に従ってカードを交互に取っていくゲームでした。少し自分で実験してみると、高橋君は大きいものi枚総取りして、青木君と取りたいカードが競合した後は残りのN - 2i枚を大きい方から交互に取っていくことがわかります。そこで、事前計算として、上i枚をとった時の点数(GetAll)、N-2i枚目から交互に取った時の高橋君の点数(AltTake)、上i枚とるために必要なxの最小値(BlockList)を求めておきます。こうすることで、xが与えられたときにBlockListを二分探索して上から何枚総取りできるかを出せば、O(1)で高橋君の点数を求めることができます。二分探索の計算量がO(logN)、事前計算の計算量がO(N + N + (N / 2))なので、全体ではO(2.5N + NlogN)でPython3でも制限時間内に解ききることができます。提出時には総取りの計算にO(N)掛けていますが、ceil(N/2)しか取れないことを考えると実はうえからceil(N/2)枚まで考えればよくて、全体の計算量を(2N + NlogN)にできます。