結果

問題 No.266 最終進化を目指せ
ユーザー lam6er
提出日時 2025-03-26 15:50:08
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,014 bytes
コンパイル時間 483 ms
コンパイル使用メモリ 82,532 KB
実行使用メモリ 60,180 KB
最終ジャッジ日時 2025-03-26 15:50:31
合計ジャッジ時間 2,355 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 2 WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
s_list = list(map(int, input().split()))
max_stage = n
stages = s_list

# DPテーブルの初期化: dp[k][a] = 最小カード数
dp = [{} for _ in range(max_stage + 1)]

# 段階0の処理
stage_0 = stages[0]
dp[0] = {a: float('inf') for a in range(stage_0 + 1)}
dp[0][0] = 1  # 初期状態

# 反復処理で段階0の強化合成を計算
updated = True
while updated:
    updated = False
    for a in range(stage_0 + 1):
        if a == 0:
            continue
        current_min = dp[0][a]
        for b in range(stage_0 + 1):
            if a < stage_0:
                required_sum = a - b - 1
                if required_sum < 0:
                    continue
                m = required_sum // stage_0
                if (b + m * stage_0 + 1) == a:
                    cost = dp[0][b] + m * dp[0][stage_0]
                    if cost < current_min:
                        current_min = cost
                        updated = True
            else:
                if b >= stage_0 - 1:
                    cost = dp[0][b] + 0 * dp[0][stage_0]
                    if cost < current_min:
                        current_min = cost
                        updated = True
                else:
                    required_m = (stage_0 - b - 1 + stage_0 - 1) // stage_0
                    if required_m < 0:
                        continue
                    if b + required_m * stage_0 + 1 >= stage_0:
                        cost = dp[0][b] + required_m * dp[0][stage_0]
                        if cost < current_min:
                            current_min = cost
                            updated = True
        if current_min < dp[0][a]:
            dp[0][a] = current_min
            updated = True

# 段階1からnまで処理
for k in range(1, max_stage + 1):
    prev_stage = k - 1
    current_stage = k
    current_s = stages[current_stage]
    prev_s = stages[prev_stage]
    prev_dp = dp[prev_stage]
    # 現在の段階のDPを初期化
    dp[current_stage] = {a: float('inf') for a in range(current_s + 1)}
    # 進化による初期値設定
    for a in range(prev_s + 1):
        if a <= current_s:
            dp[current_stage][a] = prev_dp[a] + 1
    # 反復処理で強化合成を考慮
    updated = True
    while updated:
        updated = False
        for a in range(current_s + 1):
            current_min = dp[current_stage][a]
            for b in range(current_s + 1):
                if a < current_s:
                    required_sum = a - b - 1
                    if required_sum < 0:
                        continue
                    m = required_sum // current_s
                    if (b + m * current_s + 1) == a:
                        cost = dp[current_stage][b] + m * dp[current_stage][current_s]
                        if cost < current_min:
                            current_min = cost
                            updated = True
                else:
                    if b >= current_s - 1:
                        cost = dp[current_stage][b] + 0 * dp[current_stage][current_s]
                        if cost < current_min:
                            current_min = cost
                            updated = True
                    else:
                        required_m = (current_s - b - 1 + current_s - 1) // current_s
                        if required_m < 0:
                            continue
                        if b + required_m * current_s + 1 >= current_s:
                            cost = dp[current_stage][b] + required_m * dp[current_stage][current_s]
                            if cost < current_min:
                                current_min = cost
                                updated = True
            if current_min < dp[current_stage][a]:
                dp[current_stage][a] = current_min
                updated = True

# 最終段階の結果を集める
final_s = stages[-1]
result = []
for a in range(final_s + 1):
    result.append(str(dp[max_stage][a]))

print(' '.join(result))
0