結果

問題 No.5021 Addition Pyramid
ユーザー Keroru
提出日時 2025-02-25 21:05:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,856 ms / 2,000 ms
コード長 14,763 bytes
コンパイル時間 570 ms
コンパイル使用メモリ 82,512 KB
実行使用メモリ 87,216 KB
スコア 21,604,219
最終ジャッジ日時 2025-02-25 21:07:28
合計ジャッジ時間 96,843 ms
ジャッジサーバーID
(参考情報)
judge3 / judge6
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #

T0=100000
T1=100

import time
START=ALL_START=st=time.time()
TL=5

from typing import List, Tuple

import os
import sys

file_path='keroru'
if os.path.isdir(file_path):
    prod_env=False
    from PIL import Image,ImageDraw,ImageFont
    TL=1.8
else:
    prod_env=True
    TL=1.8

from bisect import*
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline#;input=lambda:sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**7)
import copy
from itertools import permutations
from collections import deque,defaultdict,Counter


movie_frame_size=50
images=[]

hash_id=hash(st)
show_flg=False
if not prod_env:
    import os
    show_flg=True

def log(*inp, end='\n'): # output time elapsed since the last time this function was called or the program started
    if prod_env:
        return
    global st
    now=time.time()
    if show_flg:
        tmp_print(f'{now-st:.3f} sec:',*inp,end=end,flush=True)
    rt,st=now-st,now
    return rt

##############  I/O  ###############################################################
file_no=0
input_file=''
output_file=''
if prod_env:
    if str(print)!="<built-in function print>":
        del print
        tmp_print=print
        def print(*x,flush=True):
            tmp_print(*x,flush=True)
    
def IO_refresh(f_num=None):
    # in の f_num.txtから入力を全て読んでqueueに入れる。ローカルではinput()を上書きしてqueueからFIFOで返す関数にする。
    if prod_env:
        return
    global file_no,output_file,input_file,input_que,print
    if f_num==None:
        file_no+=1
    else:
        file_no=f_num
    input_file=f"in/test_{file_no:03}.txt"
    output_file=f"out/abcd_{file_no:04}.txt"
    errfile=f"out/err_{file_no:04}.txt"
    
    input_que=deque()
    with open(input_file) as fin:
        for ln in fin.readlines():
            input_que+=ln.rstrip(),
    
    with open(output_file, mode='w') as f:
        f.write('')
    with open(errfile, mode='w') as f:
        f.write('')
print_buffer=[]
if not prod_env:
    def input():
        return input_que.popleft()

    # Outputの度にファイルセーブしてると遅いので、1テストケース完了まではプリントバッファに貯めておいて最後にtxtファイルにOutputする
    if str(print)!="<built-in function print>":
        del print
    tmp_print=print
    def print(*x,flush=True,file=None):
        global print_buffer
        if file==sys.stderr:
            return
        print_buffer+=str(' '.join(map(str,x)))+'\n',
        # show(x) #デバッグ用
    
    def _print(*x,flush=True,file=None): # 直書き
        with open(output_file, mode='a') as f:
            f.write(str(' '.join(map(str,x)))+'\n')
    
    def print_all():
        global print_buffer
        with open(output_file, mode='a') as f:
            for x in print_buffer:
                f.write(x)
        print_buffer=[]

    def debug_print(*x,outputfile=None,mode='a'):
        global file_no
        if outputfile==None:
            outputfile="out/err"+str(10000+file_no)[1:]+".txt"
        with open(outputfile, mode=mode) as f:
            f.write(str(' '.join(map(str,x)))+'\n',)
        print_buffer=[]
    
    def analysis_print(*x,outputfile=None,mode='a'):
        global file_no
        if outputfile==None:
            outputfile="data/analysis_data_"+str(hash_id)+".csv"
        with open(outputfile, mode=mode) as f:
            f.write(str(' '.join(map(str,x)))+'\n',)
else:
    def print_all():
        return
    def debug_print(*x,file=sys.stderr):
        print(*x,file=file)
        return

##############  I/O  ###############################################################

##############  Template  ###############################################################
import math,time,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict

def I():return int(input())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def StoLI():return [ord(i)-97 for i in input()]
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        if prod_env:
            0
            #print('#',*inp,end=end)
        else:
            tmp_print('#',*inp,end=end)
def RLE(it):
    rt=[]
    for i in it:
        if rt and rt[-1][0]==i:rt[-1][1]+=1
        else:rt+=[i,1],
    return rt
mo=10**9+7
mo=998244353
inf=float('inf')
INF=float('inf')
inf=1<<31
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)]
compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
##############  Template  ###############################################################

n,a,*_=[0]*20
##############  read_input  ###############################################################
def read_input(test_case):
    global n,a
    IO_refresh(test_case)
    
    n=I()
    a=[]
    for _ in range(n):
        a+=LI(),
    return n,a
##############  read_input  ###############################################################
class customers_info:
    def __init__(self,n,m,homes,works):
        self.revenue=0

def station_placement_by_beam_search(n, m, homes, works, k, T, beam_width=300, max_stations=500):
    import math, random

    # (3) 状態評価のためのシミュレーション関数
    def simulate_state(state):
        # state: 駅建設順リスト (各要素は (r,c))
        t = 0
        fund = k
        revenue = 0
        cinfo = customers_info(n, m, homes, works)
        built = []
        for s in state:
            if not built:
                # 初回は設置のみ(費用としてCOST_STATIONを支払う)
                built.append(s)
                cinfo.add_station(s[0], s[1])
                fund = k - COST_STATION
            else:
                # 新駅 s を既に建設済みの駅群から最短距離で接続と仮定
                dist = min(manhattan(s, bs) for bs in built)
        final_score = fund + revenue * (T - t) if t <= T else -1
        return final_score, t, fund, revenue


    # (5) 候補手生成関数
    def get_candidate_moves(state):
        if not state:
            return candidate_positions[:]  # 1ターン目:全候補
        cand = set()
        for i in range(m):
            if home_cov and work_cov:
                continue
            # 「今カバー範囲にいる」とは,少なくとも片側はすでにカバーされている
        
        return list(cand)
    
    # (6) ビームサーチ本体
    # 各状態は (score, state, t, fund, revenue)
    beam = []
    # 初期状態(1ターン目):2駅ペアの候補状態を生成
    station_pairs=find_good_station_pair(n,m,s_for_h,s_for_w,no_of_pairs=beam_width)
    for revenue,(st1,st2,rail_len,construction_cost) in station_pairs:
        state=[st1,st2]
        score, t_val, fund_val, rev = simulate_state(state)
        beam.append((score, state, t_val, fund_val, rev))
    
    # 上位 beam_width 件に絞る
    beam.sort(key=lambda x: x[0], reverse=True)
    beam = beam[:beam_width]
    
    best_state = None
    best_score = -1
    current_level = 2  # 現在の駅数
    while current_level < max_stations:
        new_beam = []
        # 各状態から,次手候補を展開
        for score, state, t_val, fund_val, rev in beam:
            candidate_moves = get_candidate_moves(state)
            for move in candidate_moves:
                if move in state:
                    continue  # 重複は避ける
                new_state = state + [move]
                new_score, new_t, new_fund, new_rev = simulate_state(new_state)
                if new_score < 0:
                    continue
                new_beam.append((new_score, new_state, new_t, new_fund, new_rev))
        if not new_beam:
            break
        new_beam.sort(key=lambda x: x[0], reverse=True)
        beam = new_beam[:beam_width]
        # 状態のレベル(駅数)を更新
        current_level += 1
        if beam[0][0] > best_score:
            best_score = beam[0][0]
            best_state = beam[0][1]
    # 最良状態を再評価して返す
    final_score, final_t, final_fund, final_rev = simulate_state(best_state) if best_state is not None else (-1, T, -1, 0)
    return best_state, final_t, final_rev, final_score

def anealing(a):
    import random, math, time
    
    # シミュレーション用:状態評価関数
    
    # 初期状態:候補中上位2地点(なければ候補1地点)
    state = a[-1]
    current_score, x = process_a(state)
    best_state = state[:]
    best_score = current_score

    # 焼きなましパラメータ(時間・温度スケジュールなどは例)
    SA_start_time = time.time()
    # TLはグローバルTL等を利用してもよいが,ここでは例として5秒
    initial_temp = T0
    final_temp = T1

    try_count=defaultdict(int)
    passed_count=defaultdict(int)
    good_accept_count=defaultdict(int)
    bad_accept_count=defaultdict(int)    
    iteration = 0
    while 1:
        if iteration&127==127:
            #if time.time() - SA_start_time > TL_SA_st:
            if time.time() - START > TL:
                break
            show(current_score)
            #show(current_score)
        iteration += 1
        # 現状態 state のコピーを new_state とする
        new_state = state[:]
        # 移動種類
        rn=RI(0,n-1)
        mx=10**6
        new_state[rn]=(new_state[rn]+RI(-mx,mx))%mo
        
        # 状態評価
        new_score, new_x = process_a(new_state)
        
        move_type=0
        passed_count[move_type]-=1
        delta = (new_score - current_score)/mo
        # 温度スケジュール(時間経過により線形に冷却)
        elapsed = time.time() - SA_start_time
        frac = elapsed / TL
        temp = initial_temp * ((final_temp / initial_temp) ** frac)
        # 遷移採用判定        
        if delta > 0 or random.random() < math.exp(delta / temp):
            if delta>0:
                good_accept_count[move_type]+=1
            else:
                bad_accept_count[move_type]+=1
            state = new_state
            current_score = new_score
            if new_score > best_score:
                best_score=new_score
                best_state=new_state[:]
        # ※ 途中で一定回数ごとに探索長さの上限(no_of_stations)に達していたら打ち切るなどの調整も可能

    # 最終的な最良状態を再評価
    final_score, final_x = process_a(best_state)

    show(f'{iteration=}')
    #for move_type in ["swap","add", "delete", "change"]:
    #    sa_res=(good_accept_count[move_type],bad_accept_count[move_type],passed_count[move_type],try_count[move_type])
    #    debug_print(f'{move_type,"good,bad,pass,try",sa_res=}')
    return final_score, final_x

#############################################
# メイン
#############################################
mo=10**8
def gosa(a,b):
    rt=min(abs(a-b),mo-abs(a-b))
    return rt

def process_a(b):
    global n,a
    x=[b[:]]
    for t in range(n-1):
        nx=[(i+j)%mo for i,j in zip(b,b[1:])]
        x+=nx[:],
        b=nx
    x=x[::-1]
    err=0
    
    for i in range(n):
        for j in range(i+1):
            err=max(err,gosa(a[i][j],x[i][j]))
    score=5*10**7-err
    return score,x

def solve():
    global n,a
        
    score,b=anealing(a)
    ans=b[-1]
    print(*ans)
    return score,[]
    
##############  solve  ############################################################### 
start_case=0
if prod_env:
    iteration=1
else:
    start_case=1
    iteration=10

total=0
total_rel=0
quick_score=0
scores=[]
log_scores=[]
cases=[]

stats=[]
for tc in range(iteration):
    images=[]
    if not prod_env:
        START=start_time =time.time()
    #random.seed(tc+start_case)
    
    ans=[]
    show_im_flag=False
    visualize_flag=True
    visualize_flag=False
    make_movie_flag=False
    show_im_flag&=visualize_flag
    
    ######## read input ####################
    n,a=read_input(tc+start_case)
    score,*_=solve()
    debug_print(score*50)
    cases+="",
    
    ######## solver choice ####################
    
    #ew,pew,eh,peh,i_sq_err,e_sq_err,aneal_done,time_of_best_score,cnt_of_best,bw,bh,*_=specific_info
    sol_num=0
    stats+=(n),
    score=max(1,score)
    log_score=math.log(score,10)
    scores+=score,
    log_scores+=log_score,
    
    ######## calc test case info ####################
    
    #visualize(ans,tour,n,m,t,la,lb,roads,target,xy,specific_info,score=score,pseudo_ans=[],show_im=True,comment="t ="+str(t),case_num=tc+start_case)
    
    ######## output info to local ####################
    t=0
    if not prod_env:
        elapsed_t=time.time()-START
        print_all()
        
        if visualize_flag or make_movie_flag:
            new_dir_path = 'img/'+str(hash_id)
            if not os.path.isdir(new_dir_path):
                os.mkdir(new_dir_path)
        
        info=f'ID={tc+start_case:04}, lns={math.log(score,10):.3f}, {score=:>8}'
        analysis_print(','.join(map(str,[tc+start_case,math.log(score,10),score])))
        if visualize_flag:
            comment=info
            im=visualize(ans,tour,n,specific_info,score=score,pseudo_ans=[],show_im=False,comment=info,case_num=tc+start_case)
            im.save(f'img/{hash_id}/image_{tc+start_case:04}.png')
            
            mp4_flag=False
            if mp4_flag:
                clip = mp.VideoFileClip(f'img/'+str(hash_id)+'/mov_{tc+start_case:04}.gif')
                clip.write_videofile(f'img/'+str(hash_id)+'/mp4_{tc+start_case:04}.mp4' ,logger=None)
                clip.close()

        elapsed_time=time.time()-START
        
        #### info ####################
        
        log_file='_logs.txt'
        with open(log_file, mode='a') as f:
            f.write(str(''.join(map(str,info)))+'\n')
    
    quick_score+=log_score
    
    #debug_print(f'{score,sol_num=}')
    if not prod_env:
        log(info)
        print_all()
    
    if tc==9:show(f'quick score = {quick_score} average {quick_score/10}')
    ######## output info to local ####################

if not prod_env:
    now=time.time()
    hours=0
    mins=0
    secs=int(now-ALL_START)
    if secs>60:
        mins=secs//60
        secs%=60
        if mins>60:
            hours=mins//60
            mins%=60
    show(f'quick score = {quick_score} average {quick_score/iteration}')
    show(f'All processes finished in {hours} hour {mins} min {secs} sec')
0