結果
| 問題 |
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 |
ソースコード
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')