Problem p02618 (python)

Fixed submission:
n = int(input())
for i in range(n):
    print(1)

Buggy submission (verdict: Runtime Error):
from random import randrange, random
import time
START_TIME = time.time()


def is_valid(ans_types: list, ans_val: int) -> bool:
    """ans_types(1-indexed)を選んだときに、
    答えがans_valになるかどうかを確かめる。"""
    res = 0

    tmp_last_days = {}
    for c_type in range(1, C_TYPES + 1):
        tmp_last_days[c_type] = 0
   
    for day in range(1, DAYS + 1):
        c_type = ans_types[day - 1]
        res += s[day][c_type]

        tmp_last_days[c_type] = day
        for c_type in range(1, C_TYPES + 1):
            res -= c[c_type] * (day - tmp_last_days[c_type])

    return res == ans_val


def search_max_point(day: int, last_days: dict):
    """day-1日目までに選んだコンテストが確定している状態で
    day日目にどのコンテストを選べば満足度を最適化できるか貪欲に探索する。
    dayは1-indexedに注意。
    返値として、選ぶコンテスト(1-indexed)、そのときに得られる満足度を返す。
    """
    max_val = -INF
    max_type = -1
    for c_type in range(1, C_TYPES + 1):
        tmp = s[day][c_type]
        for c_type2 in range(1, C_TYPES + 1):
            if c_type2 == c_type:
                continue
            tmp -= c[c_type2] * (day - last_days[c_type2])
        if max_val < tmp:
            max_val = tmp
            max_type = c_type
    return max_type, max_val


def change(ans_types: list, day: int, from_type: int, to_type:int):
    """day日目のコンテストをfrom_typeからto_typeに変更する。
    dayは1-indexed、選ぶコンテストは1-indexedに注意。
    返値として、そのときに得られる満足度の変化量を返す。
    """
    res_diff = 0
    res_diff = -s[day][from_type] + s[day][to_type]

    from_t = ans_types
    to_t = ans_types[0:]
    to_t[day - 1] = to_type

    l_day = {from_type: 0, to_type: 0}
    for day, type_c in enumerate(from_t):
        day += 1
        if type_c in l_day:
            l_day[type_c] = day
        for type_c2 in l_day:
            res_diff += c[type_c2] * (day - l_day[type_c2])

    l_day = {from_type: 0, to_type: 0}
    for day, type_c in enumerate(to_t):
        day += 1
        if type_c in l_day:
            l_day[type_c] = day
        for type_c2 in l_day:
            res_diff -= c[type_c2] * (day - l_day[type_c2])
    return res_diff

# 1-indexedに統一(重要！！！！)
# アクセスを早くするためにtupleにしておく
d = int(input())  # 365
c = tuple([0] + list(map(int, input().split())))
s = tuple([tuple([0 for i in range(27)])] + [tuple([0] + list(map(int, input().split()))) for i in range(d)])

# 定数たち
DAYS = d
C_TYPES = 26
INF = 10 ** 18
NAPIER = 2.71828182846

# last_days: 最後にコンテストを行った日を記録する
last_days = {}
for c_type in range(1, C_TYPES + 1):
    last_days[c_type] = 0

# Step1.
# 貪欲で初期解を構築する
ans_val = 0
ans_types = []
for day in range(1, DAYS + 1):
    c_type, val = search_max_point(day, last_days)
    ans_types.append(c_type)
    ans_val += val
    last_days[c_type] = day

# 解が不当な場合(アルゴリズムが正しく構築できてない場合)、REにさせる。
if not is_valid(ans_types, ans_val):
    print(re)
    exit()

# Step2.
# 最も良いrouteを焼きなまし法で決める
T = 10000
cool = 0.9999
best_score = ans_val
best_types = ans_types[0:]
score = ans_val
types = ans_types[0:]

while time.time() - START_TIME < 1.8:

    # スワップ対象の選定
    day = randrange(1, DAYS + 1)
    from_type = ans_types[day - 1]
    while True:
        to_type = randrange(1, C_TYPES + 1)
        if to_type != from_type:
            break

    # 差を求める
    diff = change(ans_types, day, from_type, to_type)
    
    # 温度から確率を定義
    p = pow(NAPIER, -abs(diff) / T)
    
    # 遷移
    if (diff > 0 or random() < p):
        types[day - 1] = to_type
        score = score + diff
        
    # ベストスコアを保存しておく
    if score > best_score:
        best_score = score
        best_types = types[0:]
        
    # 温度を下げる
    T = T * cool

# 解が不当な場合(アルゴリズムが正しく構築できてない場合)、REにさせる。
if not is_valid(best_types, best_score):
    print(re)
    exit()

for i in best_types:
    print(i)