結果

問題 No.266 最終進化を目指せ
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:55:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 45 ms / 2,000 ms
コード長 3,286 bytes
コンパイル時間 295 ms
コンパイル使用メモリ 82,652 KB
実行使用メモリ 63,076 KB
最終ジャッジ日時 2025-03-31 17:56:38
合計ジャッジ時間 2,323 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    data = sys.stdin.read().split()
    N = int(data[0])
    S = list(map(int, data[1:N+2]))
    
    if N == 0:
        s_max = S[0]
        dp = [float('inf')] * (s_max + 1)
        dp[0] = 1
        if s_max > 0:
            updated = True
            while updated:
                updated = False
                for x in range(s_max + 1):
                    if dp[x] == float('inf'):
                        continue
                    for s in range(s_max + 1):
                        if dp[s] == float('inf'):
                            continue
                        new_awake = x + s + 1
                        if new_awake > S[0]:
                            new_awake = S[0]
                        new_cost = dp[x] + dp[s]
                        if new_cost < dp[new_awake]:
                            dp[new_awake] = new_cost
                            updated = True
        if s_max < 0:
            print(1)
        else:
            print(' '.join(map(str, dp)) if len(dp) > 1 else '1')
        return
    
    # Initialize DP for each stage
    dp = []
    # Stage 0
    stage0_max = S[0]
    dp0 = [float('inf')] * (stage0_max + 1)
    dp0[0] = 1
    if stage0_max > 0:
        updated = True
        while updated:
            updated = False
            for x in range(len(dp0)):
                if dp0[x] == float('inf'):
                    continue
                for s in range(len(dp0)):
                    if dp0[s] == float('inf'):
                        continue
                    new_awake = x + s + 1
                    if new_awake > S[0]:
                        new_awake = S[0]
                    new_cost = dp0[x] + dp0[s]
                    if new_cost < dp0[new_awake]:
                        dp0[new_awake] = new_cost
                        updated = True
    dp.append(dp0)
    
    # Process each subsequent stage
    for k in range(1, N + 1):
        current_s = S[k]
        prev_dp = dp[k-1]
        current_dp = [float('inf')] * (current_s + 1)
        # Evolve from previous stage
        for a_prev in range(len(prev_dp)):
            if prev_dp[a_prev] == float('inf'):
                continue
            if a_prev <= current_s:
                cost = prev_dp[a_prev] + 1
                if cost < current_dp[a_prev]:
                    current_dp[a_prev] = cost
        # Reinforcement synthesis for current stage
        updated = True
        while updated:
            updated = False
            for x in range(len(current_dp)):
                if current_dp[x] == float('inf'):
                    continue
                for s in range(len(current_dp)):
                    if current_dp[s] == float('inf'):
                        continue
                    new_awake = x + s + 1
                    if new_awake > current_s:
                        new_awake = current_s
                    new_cost = current_dp[x] + current_dp[s]
                    if new_cost < current_dp[new_awake]:
                        current_dp[new_awake] = new_cost
                        updated = True
        dp.append(current_dp)
    
    final = dp[N]
    result = []
    for count in final:
        result.append(str(count))
    print(' '.join(result))

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