結果

問題 No.5021 Addition Pyramid
ユーザー ra5anchor
提出日時 2025-03-02 19:47:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,625 ms / 2,000 ms
コード長 5,268 bytes
コンパイル時間 577 ms
コンパイル使用メモリ 82,840 KB
実行使用メモリ 85,188 KB
スコア 201,919,030
最終ジャッジ日時 2025-03-02 19:49:24
合計ジャッジ時間 85,124 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

        iter = 0
        max_iter = 1000
        while not tk.is_time_over(LIMIT) and iter < max_iter:
            iter += 1
            B = [[0]*N for _ in range(N)]
            a = random.randrange(10**8)
            # a = 0
            # d = random.randint(-10**4, 10**4)
            d = 0
            dif = 10**5 + d

            B[0][0] = (A[0][0] + a) % MAX
            for i in range(1, N):
                mn = 10**18
                for st in range(0, 10**8, dif):
                    max_err = 0
                    now = st
                    for j in range(i+1):
                        err = error(A[i][j], now)
                        max_err = max(max_err, err)
                        now = (B[i-1][j] - now) % MAX
                    if max_err < mn:
                        mn = max_err
                        bestst = st
                B[i][0] = bestst
                for j in range(1, i+1):
                    B[i][j] = (B[i-1][j-1] - B[i][j-1]) % MAX
            
            # print(len(B), len(B[i]), file=sys.stderr)
            # for i in range(N):
            #     print(*B[i], file=sys.stderr)
            #     print(*A[i], file=sys.stderr)
            sol = B[N-1]
            sc, pos = cal_score(sol)
            if sc > best_sc:
                print(f"best: {iter=} {sc=} {a=} {d=}", file=sys.stderr)
                best_sc = sc
                best_sol = sol[:]

        return best_sol, best_sc


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

    
    # 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, LIMIT)
    
    # 改良
    # sol2, sc2 = SA(sol1, sc1, LIMIT)

    # 出力
    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