H - まとめ売り

H - まとめ売り

O(Q^N) 問題文をシミュレーションした際のコードです。 TLEになります。

import math
import heapq
import itertools
from functools import reduce
 
# main
def main():
    N = int(input())
    C = list(map(int, input().split()))
    Q = int(input())
    res = 0

    for i in range(0, Q):
        S = list(map(int, input().split()))

        if S[0] == 1:
            x = S[1] - 1
            if C[x] - S[2] >= 0:
                C[x] = C[x] - S[2]
                res += S[2]
        if S[0] == 2:
            ok = True
            for i in range(0, N, 2):
                if C[i] - S[1] < 0:
                    ok = False
            if ok:
                for i in range(0, N, 2):
                    C[i] = C[i] - S[1]
                    res += S[1]
        if S[0] == 3:
            ok = True
            for i in range(0, N):
                if C[i] - S[1] < 0:
                    ok = False
            if ok:
                for i in range(0, N):
                    C[i] = C[i] - S[1]
                    res += S[1]
    print(res)
            
# エントリポイント
if __name__ == '__main__':
    main()

クエリの2, 3の時の処理は改善できそうです。 奇数の購入枚数、全種類の購入枚数を保持します。 最後に加算すると良さそうです。

import math
import heapq
import itertools
from functools import reduce
 
# main
def main():
    N = int(input())
    C = list(map(int, input().split()))
    Q = int(input())
    res = 0
    s = 0
    z = 0
    min_s_C = 1000000007
    min_z_C = 1000000007

    for i in range(0, N):
        if i % 2 == 0:
            min_s_C = min(min_s_C, C[i])
        else:
            min_z_C = min(min_z_C, C[i])

    for i in range(0, Q):
        S = list(map(int, input().split()))

        if S[0] == 1:
            if (S[1] - 1) % 2 == 0:
                if C[S[1]-1] - s - z - S[2] >= 0:
                    C[S[1]-1] = C[S[1]-1] - S[2]
                    min_s_C = min(min_s_C, C[S[1]-1])
                    res += S[2]
            else:
                if C[S[1]-1] - z - S[2] >= 0:
                    C[S[1]-1] = C[S[1]-1] - S[2]
                    min_z_C = min(min_z_C, C[S[1]-1])
                    res += S[2]

        if S[0] == 2:
            if min_s_C - s - z - S[1] >= 0:
                s += S[1]

        if S[0] == 3:
            if min(min_s_C - s - z, min_z_C - z) - S[1] >= 0:
                z += S[1]

    res += len(C) * z + (len(C)+1) // 2 * s
    print(res)
            
# エントリポイント
if __name__ == '__main__':
    main()