提出 #71725602

---

ソースコード 拡げる

import sys
import math
from heapq import heappush, heappop, nlargest
from copy import deepcopy

# 定数
TIME_LIMIT = 1.8  # 実行時間制限（少し余裕を持たせる）
BEAM_WIDTH = 50   # ビーム幅（PyPy3ならもっと増やせる可能性があります）

def solve():
    # --- 入力受取 ---
    # N: ID種類数(10), L: Level種類数(4), T: ターン数(500), K: 初期りんご
    N, L, T, K = map(int, sys.stdin.readline().split())
    
    # A: Level 0 の生産能力
    A = list(map(int, sys.stdin.readline().split()))
    
    # C: 初期コスト [Level][ID]
    C = []
    for _ in range(L):
        row = list(map(int, sys.stdin.readline().split()))
        C.append(row)

    # --- 前計算: 二項係数 ---
    # パスカルの三角形を用いて二項係数を事前計算
    # comb[n][k] = nCk
    # 最大500ターンなので 505 x 6 程度あれば十分（kは最大でもLevel数+1程度）
    comb = [[0] * 10 for _ in range(T + 10)]
    for i in range(T + 10):
        comb[i][0] = 1
        if i > 0:
            for j in range(1, 10):
                comb[i][j] = comb[i-1][j-1] + comb[i-1][j]

    # --- 状態クラスの定義 ---
    class State:
        def __init__(self, apples, B, P, history, turn):
            self.apples = apples
            self.B = B  # 機械の台数 [L][N]
            self.P = P  # 機械のパワー [L][N]
            self.history = history # 行動履歴
            self.turn = turn
            self.score = -1 # 評価値（未計算）

        def evaluate(self):
            """
            評価関数:
            「この時点からゲーム終了(Tターン)まで、一度も強化を行わなかった場合」の
            最終的なりんご総数を計算する。
            これを数学的公式（二項係数）で一発計算する。
            """
            remaining_turns = T - self.turn
            if remaining_turns <= 0:
                return self.apples

            predicted_apples = self.apples
            
            # 各機械について、残りの期間でどれだけりんごを生み出すか加算
            for j in range(N):
                # ID j の機械群が連携して生み出すりんご
                
                # 生産性ベース (A[j] * 全レベルのPの積)
                # 注: 実際は連鎖的に作用するが、簡易化のため系列ごとの係数を計算
                # 正確には、Level k の機械が Level 0 のりんごになるまで k ターン遅延し、
                # その寄与は パスカルの三角形(二項係数) に従う。
                
                # Level 0 の機械からの寄与
                # 毎ターン A[j] * P[0][j] * B[0][j]
                if self.P[0][j] > 0:
                    term = A[j] * self.B[0][j] * self.P[0][j]
                    predicted_apples += term * remaining_turns
                
                # Level 1以上の機械からの寄与
                # Level i の機械 1台は、tターン後に binom(t, i+1) 個のりんご生産に寄与する(概算)
                # 厳密には、間のLevelのPowerも掛け算される
                
                # 高速化のため、影響力が大きい系列のみ計算、あるいはDP的に解くべきだが
                # ここでは「現在の構成で放置した場合の厳密解」を計算する
                
                # Pの累積積を計算 (prod_P[i] = P[0][j] * ... * P[i][j])
                # ただしP=0が含まれるとそれより上流は機能しない
                
                current_prod = A[j]
                for i in range(L):
                    if self.P[i][j] == 0:
                        break # これより上のレベルは下のレベルを動かせない
                    
                    current_prod *= self.P[i][j]
                    
                    # Level i の機械 B[i][j] 台が残り R ターンで生む総量
                    # 公式: Total += B[i][j] * (A * ΠP) * binom(R, i+1)
                    # binom(R, i+1) は、「残りRターンで、i回の積分（累積和）を経て得られる総和」
                    
                    term = self.B[i][j] * current_prod * comb[remaining_turns][i+1]
                    predicted_apples += term
            
            return predicted_apples

        def __lt__(self, other):
            # heapqは最小値を取り出すため、逆にして最大ヒープのように振る舞わせる
            # ただし、今回は nlargest を使うので、単純に score で比較できれば良い
            return self.score < other.score

    # --- 初期状態 ---
    # B: 全て1, P: 全て0
    init_B = [[1] * N for _ in range(L)]
    init_P = [[0] * N for _ in range(L)]
    
    initial_state = State(K, init_B, init_P, [], 0)
    initial_state.score = initial_state.evaluate()
    
    beam = [initial_state]

    # --- ターン進行 ---
    for t in range(T):
        next_beam = []
        
        # 候補の手を列挙して次状態を作成
        # ビーム内の各状態について
        for state in beam:
            # 1. 何もしない (常に選択可能)
            # コスト0。ただし、自動生産フェーズは必ず走る
            
            # まず、このターンでの自動生産(Bの増加とりんごの増加)を計算しておく
            # 次の状態のベースとなる B と apples
            next_B = [row[:] for row in state.B]
            produced_apples = 0
            
            # Level 0, 1, 2, 3 の順に処理 (問題文準拠)
            # Level 0: りんご増加
            for j in range(N):
                produced_apples += A[j] * state.B[0][j] * state.P[0][j]
            
            # Level 1以上: 1つ下のレベルの機械数増加
            for i in range(1, L):
                for j in range(N):
                    next_B[i-1][j] += state.B[i][j] * state.P[i][j]
            
            base_next_apples = state.apples + produced_apples
            
            # 行動A: 何もしない (-1)
            # 常に候補に入れる
            no_op_state = State(
                base_next_apples, 
                next_B, 
                state.P, # Pは変わらない
                state.history + [-1], 
                t + 1
            )
            no_op_state.score = no_op_state.evaluate()
            next_beam.append(no_op_state)

            # 行動B: 強化する (i, j)
            # 全ての (i, j) を試すと 40 通り。ビーム幅50だと 2000 状態生成。
            # 重すぎれば、コストが払えるものだけに絞るなどの枝刈りが可能。
            
            for i in range(L):
                for j in range(N):
                    cost = C[i][j] * (state.P[i][j] + 1)
                    
                    # コストが払えるかチェック (state.apples を使う。自動生産分はこのターン使えない)
                    if state.apples >= cost:
                        # 強化実行
                        new_P = [row[:] for row in state.P]
                        new_P[i][j] += 1
                        
                        # りんご消費
                        rem_apples = base_next_apples - cost
                        
                        # 新しい状態
                        upg_state = State(
                            rem_apples,
                            next_B,
                            new_P,
                            state.history + [i * N + j], # 履歴には便宜上整数を入れる、出力時に変換
                            t + 1
                        )
                        upg_state.score = upg_state.evaluate()
                        next_beam.append(upg_state)

        # 上位 K 個を残す (Beam Search)
        # スコア（将来予測される最終りんご数）が高い順
        beam = nlargest(BEAM_WIDTH, next_beam, key=lambda s: s.score)

    # --- 結果出力 ---
    best_state = beam[0]
    
    # 履歴をデコードして出力
    for action in best_state.history:
        if action == -1:
            print("-1")
        else:
            i = action // N
            j = action % N
            print(f"{i} {j}")

# --- 実行 ---
if __name__ == "__main__":
    solve()

提出情報

ジャッジ結果