結果

問題 No.5021 Addition Pyramid
ユーザー ra5anchor
提出日時 2025-03-02 17:47:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,624 ms / 2,000 ms
コード長 3,408 bytes
コンパイル時間 462 ms
コンパイル使用メモリ 82,388 KB
実行使用メモリ 89,544 KB
スコア 33,272,010
最終ジャッジ日時 2025-03-02 17:49:02
合計ジャッジ時間 84,268 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

import copy
import random
from time import perf_counter
import argparse
import sys
import math

MAX = 10**8

class TimeKeeper:
    def __init__(self):
        self.start_time = perf_counter()
    def is_time_over(self, LIMIT):
        return (perf_counter() - self.start_time) >= LIMIT
    def time_now(self):
        return (perf_counter() - self.start_time)

def error(a, b):
    return min(abs(a - b), MAX - abs(a - b))

###########################################
def main(DEBUG):
    tk = TimeKeeper()
    if DEBUG == True:
        LIMIT = 1
    else:
        LIMIT = 1.5

    def cal_score(C):
        N = 50
        B = [[0 for i in range(N)] for i in range(N)]
        for i in range(N):
            B[N - 1][i] = C[i]
        for h in range(N-1):
            i = N - 2 - h
            for j in range(i+1):
                B[i][j] = (B[i+1][j] + B[i+1][j+1]) % MAX
        max_error = 0
        for i in range(N):
            for j in range(i+1):
                max_error = max(max_error, error(A[i][j], B[i][j]))
        score = MAX // 2 - max_error
        return score

    def SA(current_sol, current_sc, LIMIT):
        best_sol = current_sol
        best_sc = current_sc
        iter = 0
        
        T0 = 0.0001
        T1 = 0.0001
        # T0 = 10000
        # T1 = 1

        while not tk.is_time_over(LIMIT):
            iter += 1
            progress = tk.time_now() / LIMIT
            T = T0 + (T1 - T0) * progress
            cand = current_sol[:]

            num = random.randrange(100)
            if num < 20:
                type = 1
                id = random.randrange(N)
                num = random.randrange(MAX)
                cand[id] = (cand[id] + num) % MAX
            if num < 40:
                type = 2
                id = random.randrange(N)
                num = random.randint(-1000, 1000)
                cand[id] = (cand[id] + num) % MAX
            if num < 60:
                type = 3
                id = random.randrange(N)
                num = random.randint(-10, 10)
                cand[id] = (cand[id] + num) % MAX
            elif num < 100:
                type = 4
                id1 = random.randrange(N)
                id2 = random.randrange(N)
                cand[id1], cand[id2] = cand[id2], cand[id1]
    
            cand_sc = cal_score(cand)
            delta = cand_sc - current_sc
            
            if delta >= 0 or random.random() < math.exp(delta / T):
                current_sol = cand[:]
                current_sc = cand_sc
                if cand_sc > best_sc:
                    print(f"best: {iter=} {cand_sc=} {type=}", file=sys.stderr)
                    best_sol = cand[:]
                    best_sc = cand_sc

        return best_sol, best_sc
            
    
    N = int(input()) # N=50
    A = [[0]*N for _ in range(N)]
    for i in range(N):        
        L = list(map(int, input().split()))
        for j in range(i+1):
            A[i][j] = L[j]
    
    # 初期解
    init_sol = [0]*N
    init_sc = cal_score(init_sol)
    
    # 改良
    sol, sc = SA(init_sol, init_sc, LIMIT)

    # 出力
    print(*sol)
    print(f"SC: {sc}", file=sys.stderr)
            
    


if __name__ == '__main__':
    parser = argparse.ArgumentParser(description='Debug mode')
    parser.add_argument('--debug', action='store_true', help='Enable debug mode')
    args = parser.parse_args()
    main(args.debug)
0