結果
問題 | No.5021 Addition Pyramid |
ユーザー |
|
提出日時 | 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 |
ソースコード
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')