結果

問題 No.9 モンスターのレベル上げ
ユーザー gew1fw
提出日時 2025-06-12 12:55:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 4,515 ms / 5,000 ms
コード長 1,678 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 82,280 KB
実行使用メモリ 149,568 KB
最終ジャッジ日時 2025-06-12 13:01:34
合計ジャッジ時間 22,745 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    A = list(map(int, data[idx:idx+N]))
    idx += N
    B = list(map(int, data[idx:idx+N]))
    idx += N
    
    # Precompute orders for each starting point k
    orders = []
    for k in range(N):
        order = []
        for i in range(N):
            pos = (k + i) % N
            order.append(B[pos])
        orders.append(order)
    
    min_max = N  # Initialize with the worst possible value
    
    for k in range(N):
        current_level = A.copy()
        current_count = [0] * N
        heap = [(current_level[i], current_count[i], i) for i in range(N)]
        heapq.heapify(heap)
        current_max = 0
        early_terminate = False
        
        for b in orders[k]:
            while True:
                level, cnt, idx = heapq.heappop(heap)
                if current_level[idx] == level and current_count[idx] == cnt:
                    current_count[idx] += 1
                    new_level = level + (b // 2)
                    current_level[idx] = new_level
                    heapq.heappush(heap, (new_level, current_count[idx], idx))
                    if current_count[idx] > current_max:
                        current_max = current_count[idx]
                        if current_max >= min_max:
                            early_terminate = True
                    break
            if early_terminate:
                break
        
        if not early_terminate and current_max < min_max:
            min_max = current_max
    
    print(min_max)

if __name__ == "__main__":
    main()
0