提出 #70290449

---

ソースコード 拡げる

import sys
from typing import List, Tuple

# ---------------------------------------
# Heuristic:
# 1) Choose "primer" chest p maximizing avg_topCi = sum_top_Ci(A[p,*]) / C[p]
# 2) Open p by hand (Wi = -1)
# 3) While unopened remains:
#    - Among available weapons (remaining durability>0), pick (w,b) with max A[w][b]
#    - If max_damage <= 1 -> hand on the softest remaining chest
#    - Apply; when a chest opens, its weapon becomes available
# ---------------------------------------

def choose_primer(N: int, H: List[int], C: List[int], A: List[List[int]]) -> int:
    best = (-1.0, -10**9, -1)  # (score, -H[i], -i)  -> prefer high score, then small H
    for i in range(N):
        ci = C[i]
        if ci <= 0:
            score = 0.0
        else:
            row = A[i][:]
            row.sort(reverse=True)
            score = sum(row[:ci]) / ci
        cand = (score, -H[i], -i)
        if cand > best:
            best = cand
    return -best[2]

def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    try:
        N = int(next(it))
    except StopIteration:
        return
    H = [int(next(it)) for _ in range(N)]
    C = [int(next(it)) for _ in range(N)]
    A = [[int(next(it)) for _ in range(N)] for _ in range(N)]

    # Remaining hardness; track opened
    remH = H[:]
    opened = [False]*N

    # Weapons: remaining durability; only usable after chest opened
    remC = [0]*N

    actions: List[Tuple[int, int]] = []

    # 1) choose primer and open by hand
    primer = choose_primer(N, remH, C, A)
    # open by hand
    while remH[primer] > 0:
        remH[primer] -= 1
        actions.append((-1, primer))
    opened[primer] = True
    remC[primer] = C[primer]

    # 2) loop until all opened
    unopened_count = opened.count(False)
    while unopened_count > 0:
        # find best weapon attack
        best_w, best_b, best_damage = -1, -1, 0
        for w in range(N):
            if remC[w] <= 0:
                continue
            # try all unopened boxes
            # prefer harder box when tie on damage
            for b in range(N):
                if remH[b] <= 0:
                    continue
                dmg = A[w][b]
                if dmg > best_damage or (dmg == best_damage and remH[b] > (remH[best_b] if best_b != -1 else -1)):
                    best_damage = dmg
                    best_w, best_b = w, b

        if best_damage <= 1:
            # hand attack: hit the softest remaining box
            target = -1
            best_h = 10**9
            for b in range(N):
                if 0 < remH[b] < best_h:
                    best_h = remH[b]
                    target = b
            # safety
            if target == -1:
                break
            remH[target] -= 1
            actions.append((-1, target))
            if remH[target] <= 0 and not opened[target]:
                opened[target] = True
                remC[target] = C[target]
                unopened_count -= 1
        else:
            # use weapon
            remH[best_b] -= best_damage
            remC[best_w] -= 1
            actions.append((best_w, best_b))
            if remH[best_b] <= 0 and not opened[best_b]:
                opened[best_b] = True
                remC[best_b] = C[best_b]
                unopened_count -= 1

    # 出力
    print(len(actions))
    for w, b in actions:
        print(w, b)

if __name__ == "__main__":
    main()

提出情報

ジャッジ結果