結果

問題 No.5021 Addition Pyramid
コンテスト
ユーザー ra5anchor
提出日時 2025-03-02 19:22:31
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 218 ms / 2,000 ms
コード長 4,693 bytes
コンパイル時間 504 ms
コンパイル使用メモリ 82,696 KB
実行使用メモリ 84,064 KB
スコア 167,471,620
最終ジャッジ日時 2025-03-02 19:22:45
合計ジャッジ時間 12,012 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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()

    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):
                err = error(A[i][j], B[i][j])
                if err > max_error:
                    max_error = err
                    max_error_pos = (i,j)
                # max_error = max(max_error, error(A[i][j], B[i][j]))
        score = MAX // 2 - max_error
        return score, max_error_pos

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

        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, pos = 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

    def GR(current_sol, current_sc, LIMIT):
        best_sol = current_sol
        best_sc = current_sc
        sol = [[0]*N for _ in range(N)]
        sol[0][0] = A[0][0]
        for i in range(1, N):
            mn = 10**18
            for st in range(0, 10**8, 10**5):
                max_err = 0
                now = st
                for j in range(i+1):
                    err = error(A[i][j], now)
                    max_err = max(max_err, err)
                    now = (sol[i-1][j] - now) % MAX
                if max_err < mn:
                    mn = max_err
                    bestst = st
            sol[i][0] = bestst
            for j in range(1, i+1):
                sol[i][j] = (sol[i-1][j-1] - sol[i][j-1]) % MAX
        # print(len(sol), len(sol[i]), file=sys.stderr)
        # for i in range(N):
        #     print(*sol[i], file=sys.stderr)
        #     print(*A[i], file=sys.stderr)
        sc, pos = cal_score(sol[N-1])

        return sol[N-1], sc


    if DEBUG == True:
        LIMIT = 1
    else:
        LIMIT = 1.5

    LIMIT1 = 0.5
    LIMIT2 = 1.0
    
    random.seed(0)            
    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, pos = cal_score(init_sol)
    
    # 改良
    sol1, sc1 = GR(init_sol, init_sc, LIMIT1)
    
    # 改良
    # sol2, sc2 = SA(sol1, sc1, LIMIT2)

    # 出力
    print(*sol1)
    print(f"SC: {sc1}", 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