#932298 (PyPy3) No.2596 Christmas Eve (Heuristic ver.)

提出ソース

結果

問題	No.2596 Christmas Eve (Heuristic ver.)
ユーザー	hirayuu_yc
提出日時	2023-11-28 14:43:54
言語	PyPy3 (7.3.15)
結果	AC
実行時間	1,153 ms / 1,224 ms
コード長	5,966 bytes
コンパイル時間	224 ms
コンパイル使用メモリ	81,700 KB
実行使用メモリ	87,596 KB
スコア	4,995,436
最終ジャッジ日時	2023-12-23 20:35:32
合計ジャッジ時間	155,564 ms
ジャッジサーバーID （参考情報）	judge12 / judge13
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,151 ms 85,396 KB
testcase_01	AC	1,152 ms 85,996 KB
testcase_02	AC	1,152 ms 85,876 KB
testcase_03	AC	1,151 ms 85,056 KB
testcase_04	AC	1,152 ms 85,316 KB
testcase_05	AC	1,151 ms 85,168 KB
testcase_06	AC	1,151 ms 86,168 KB
testcase_07	AC	1,151 ms 85,384 KB
testcase_08	AC	1,151 ms 86,368 KB
testcase_09	AC	1,150 ms 86,172 KB
testcase_10	AC	1,151 ms 86,932 KB
testcase_11	AC	1,151 ms 85,904 KB
testcase_12	AC	1,151 ms 85,232 KB
testcase_13	AC	1,151 ms 85,308 KB
testcase_14	AC	1,150 ms 85,000 KB
testcase_15	AC	1,151 ms 86,428 KB
testcase_16	AC	1,151 ms 85,692 KB
testcase_17	AC	1,152 ms 85,436 KB
testcase_18	AC	1,151 ms 86,360 KB
testcase_19	AC	1,151 ms 86,188 KB
testcase_20	AC	1,151 ms 85,768 KB
testcase_21	AC	1,151 ms 86,356 KB
testcase_22	AC	1,151 ms 85,512 KB
testcase_23	AC	1,152 ms 85,232 KB
testcase_24	AC	1,150 ms 85,680 KB
testcase_25	AC	1,152 ms 85,244 KB
testcase_26	AC	1,151 ms 86,152 KB
testcase_27	AC	1,151 ms 85,988 KB
testcase_28	AC	1,151 ms 85,760 KB
testcase_29	AC	1,151 ms 86,180 KB
testcase_30	AC	1,152 ms 86,140 KB
testcase_31	AC	1,151 ms 85,504 KB
testcase_32	AC	1,152 ms 86,664 KB
testcase_33	AC	1,151 ms 87,060 KB
testcase_34	AC	1,151 ms 84,936 KB
testcase_35	AC	1,150 ms 86,556 KB
testcase_36	AC	1,151 ms 86,044 KB
testcase_37	AC	1,151 ms 85,792 KB
testcase_38	AC	1,149 ms 85,796 KB
testcase_39	AC	1,151 ms 85,012 KB
testcase_40	AC	1,152 ms 86,252 KB
testcase_41	AC	1,152 ms 85,880 KB
testcase_42	AC	1,151 ms 85,452 KB
testcase_43	AC	1,151 ms 85,192 KB
testcase_44	AC	1,152 ms 85,200 KB
testcase_45	AC	1,150 ms 86,608 KB
testcase_46	AC	1,152 ms 84,260 KB
testcase_47	AC	1,150 ms 86,660 KB
testcase_48	AC	1,150 ms 85,644 KB
testcase_49	AC	1,153 ms 86,196 KB
testcase_50	AC	1,151 ms 85,976 KB
testcase_51	AC	1,151 ms 85,908 KB
testcase_52	AC	1,152 ms 86,000 KB
testcase_53	AC	1,150 ms 85,864 KB
testcase_54	AC	1,151 ms 85,236 KB
testcase_55	AC	1,150 ms 86,564 KB
testcase_56	AC	1,152 ms 85,620 KB
testcase_57	AC	1,152 ms 85,976 KB
testcase_58	AC	1,151 ms 86,184 KB
testcase_59	AC	1,152 ms 85,464 KB
testcase_60	AC	1,151 ms 85,776 KB
testcase_61	AC	1,152 ms 85,400 KB
testcase_62	AC	1,151 ms 86,364 KB
testcase_63	AC	1,152 ms 85,640 KB
testcase_64	AC	1,152 ms 86,344 KB
testcase_65	AC	1,152 ms 85,952 KB
testcase_66	AC	1,153 ms 85,100 KB
testcase_67	AC	1,151 ms 86,500 KB
testcase_68	AC	1,152 ms 85,788 KB
testcase_69	AC	1,152 ms 85,368 KB
testcase_70	AC	1,149 ms 86,452 KB
testcase_71	AC	1,150 ms 86,220 KB
testcase_72	AC	1,150 ms 85,884 KB
testcase_73	AC	1,152 ms 85,372 KB
testcase_74	AC	1,150 ms 87,596 KB
testcase_75	AC	1,150 ms 86,168 KB
testcase_76	AC	1,152 ms 85,496 KB
testcase_77	AC	1,151 ms 85,212 KB
testcase_78	AC	1,150 ms 86,148 KB
testcase_79	AC	1,151 ms 86,152 KB
testcase_80	AC	1,150 ms 85,136 KB
testcase_81	AC	1,150 ms 86,600 KB
testcase_82	AC	1,151 ms 84,208 KB
testcase_83	AC	1,151 ms 84,740 KB
testcase_84	AC	1,150 ms 84,944 KB
testcase_85	AC	1,151 ms 87,004 KB
testcase_86	AC	1,150 ms 84,772 KB
testcase_87	AC	1,151 ms 85,880 KB
testcase_88	AC	1,151 ms 86,160 KB
testcase_89	AC	1,151 ms 86,268 KB
testcase_90	AC	1,150 ms 86,420 KB
testcase_91	AC	1,151 ms 86,268 KB
testcase_92	AC	1,151 ms 86,168 KB
testcase_93	AC	1,151 ms 85,324 KB
testcase_94	AC	1,151 ms 86,256 KB
testcase_95	AC	1,151 ms 86,544 KB
testcase_96	AC	1,151 ms 86,664 KB
testcase_97	AC	1,150 ms 86,756 KB
testcase_98	AC	1,151 ms 86,776 KB
testcase_99	AC	1,152 ms 84,776 KB
testcase_100	AC	1,151 ms 86,028 KB
testcase_101	AC	1,151 ms 86,260 KB
testcase_102	AC	1,151 ms 85,820 KB
testcase_103	AC	1,151 ms 86,088 KB
testcase_104	AC	1,151 ms 85,900 KB
testcase_105	AC	1,151 ms 86,396 KB
testcase_106	AC	1,151 ms 85,980 KB
testcase_107	AC	1,153 ms 85,364 KB
testcase_108	AC	1,153 ms 85,376 KB
testcase_109	AC	1,151 ms 87,436 KB
testcase_110	AC	1,150 ms 85,792 KB
testcase_111	AC	1,151 ms 86,368 KB
testcase_112	AC	1,152 ms 85,128 KB
testcase_113	AC	1,150 ms 85,664 KB
testcase_114	AC	1,150 ms 85,480 KB
testcase_115	AC	1,151 ms 86,628 KB
testcase_116	AC	1,151 ms 85,076 KB
testcase_117	AC	1,152 ms 86,284 KB
testcase_118	AC	1,150 ms 86,004 KB
testcase_119	AC	1,150 ms 85,912 KB
testcase_120	AC	1,151 ms 86,512 KB
testcase_121	AC	1,151 ms 85,844 KB
testcase_122	AC	1,151 ms 86,240 KB
testcase_123	AC	1,150 ms 85,628 KB
testcase_124	AC	1,152 ms 86,036 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import random
import time
from math import exp
def isvalid(tree):
    return e[tree[3]]<a[tree[0]] and a[tree[0]]<c[tree[1]] and a[tree[0]]<c[tree[2]]

def high(tree):
    return b[tree[0]]+d[tree[1]]+d[tree[2]]+f[tree[3]]

def row_score(trees):
    global mini_pos,maxi_pos
    mini=40000
    maxi=0
    cnt=0
    for i in trees:
        now=high(i)
        if now<mini:
            mini=now
            mini_pos=cnt
        if now>maxi:
            maxi=now
            maxi_pos=cnt
        cnt+=1
    return maxi-mini

def score(trees):
    wa=0
    use=[]
    for i in trees:
        use.append(high(i))
        wa+=use[-1]
    ret=0
    for i in use:
        ret+=((i*N)-wa)**2
    return ret

st=time.time()
N,M=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
d=list(map(int,input().split()))
e=list(map(int,input().split()))
f=list(map(int,input().split()))
tip=list(zip(a,b,range(N)))
center=list(zip(c,d,range(N*2)))
stem=list(zip(e,f,range(N)))
tip.sort(reverse=True)
center.sort(reverse=True)
stem.sort(reverse=True)
tip_stock=set(range(N))
center_stock=set(range(N*2))
stem_stock=set(range(N))
tree=[]
for i in range(M):
    while stem[-1][0]>=tip[-1][0]:
        tip.pop()
    while tip[-1][0]>=center[-1][0]:
        center.pop()
    tree.append([tip[-1][2],center[-1][2],center[-2][2],stem[-1][2]])
    tip_stock.discard(tip[-1][2])
    center_stock.discard(center[-1][2])
    center_stock.discard(center[-2][2])
    stem_stock.discard(stem[-1][2])
    center.pop()
    center.pop()
    tip.pop()
    stem.pop()
tip_stock=list(tip_stock)
center_stock=list(center_stock)
stem_stock=list(stem_stock)
mini_pos=-1
maxi_pos=-1
now=row_score(tree)
t_st=20000
t_gl=5
count=0
best=now
fin=[i[:] for i in tree]
while time.time()-st<1.1:
    count+=1
    now_temp=t_st*(t_gl/t_st)**(time.time()-st)
    befmi=mini_pos
    befma=maxi_pos
    if random.random()<0.1:
        if random.random()<0.5:
            lf=mini_pos
        else:
            lf=maxi_pos
        ri=random.randint(0,M-1)
        if lf==ri:
            ri=(ri+1)%M
        if random.random()<0.25:
            tree[lf][0],tree[ri][0]=tree[ri][0],tree[lf][0]
            if not(isvalid(tree[lf]) and isvalid(tree[ri])):
                tree[lf][0],tree[ri][0]=tree[ri][0],tree[lf][0]
            else:
                sc=row_score(tree)
                if not(sc<now or random.random()<exp((now-sc)/now_temp)):
                    maxi_pos=befma
                    mini_pos=befmi
                    tree[lf][0],tree[ri][0]=tree[ri][0],tree[lf][0]
                else:
                    now=sc
        elif random.random()<0.3333:
            tree[lf][2],tree[ri][2]=tree[ri][2],tree[lf][2]
            if not(isvalid(tree[lf]) and isvalid(tree[ri])):
                tree[lf][2],tree[ri][2]=tree[ri][2],tree[lf][2]
            else:
                sc=row_score(tree)
                if not(sc<now or random.random()<exp((now-sc)/now_temp)):
                    maxi_pos=befma
                    mini_pos=befmi
                    tree[lf][2],tree[ri][2]=tree[ri][2],tree[lf][2]
                else:
                    now=sc
        else:
            if random.random()<0.5:
                tree[lf][1],tree[lf][2]=tree[lf][2],tree[lf][1]
            if random.random()<0.5:
                tree[ri][1],tree[ri][2]=tree[ri][2],tree[ri][1]
            tree[lf][1],tree[ri][1]=tree[ri][1],tree[lf][1]
            if not(isvalid(tree[lf]) and isvalid(tree[ri])):
                tree[lf][1],tree[ri][1]=tree[ri][1],tree[lf][1]
            else:
                sc=row_score(tree)
                if not(sc<now or random.random()<exp((now-sc)/now_temp)):
                    maxi_pos=befma
                    mini_pos=befmi
                    tree[lf][1],tree[ri][1]=tree[ri][1],tree[lf][1]
                else:
                    now=sc
    else:
        if random.random()<0.5:
            lf=mini_pos
        else:
            lf=maxi_pos
        if random.random()<0.25:
            pos=random.randint(0,len(tip_stock)-1)
            tree[lf][0],tip_stock[pos]=tip_stock[pos],tree[lf][0]
            if not(isvalid(tree[lf])):
                tree[lf][0],tip_stock[pos]=tip_stock[pos],tree[lf][0]
            else:
                sc=row_score(tree)
                if not(sc<now or random.random()<exp((now-sc)/now_temp)):
                    maxi_pos=befma
                    mini_pos=befmi
                    tree[lf][0],tip_stock[pos]=tip_stock[pos],tree[lf][0]
                else:
                    now=sc
        elif random.random()<0.33333:
            pos=random.randint(0,len(stem_stock)-1)
            tree[lf][3],stem_stock[pos]=stem_stock[pos],tree[lf][3]
            if not(isvalid(tree[lf])):
                tree[lf][3],stem_stock[pos]=stem_stock[pos],tree[lf][3]
            else:
                sc=row_score(tree)
                if not(sc<now or random.random()<exp((now-sc)/now_temp)):
                    maxi_pos=befma
                    mini_pos=befmi
                    tree[lf][3],stem_stock[pos]=stem_stock[pos],tree[lf][3]
                else:
                    now=sc
        else:
            if random.random()<0.5:
                tree[lf][1],tree[lf][2]=tree[lf][2],tree[lf][1]
            pos=random.randint(0,len(center_stock)-1)
            tree[lf][2],center_stock[pos]=center_stock[pos],tree[lf][2]
            if not(isvalid(tree[lf])):
                tree[lf][2],center_stock[pos]=center_stock[pos],tree[lf][2]
            else:
                sc=row_score(tree)
                if not(sc<now or random.random()<exp((now-sc)/now_temp)):
                    maxi_pos=befma
                    mini_pos=befmi
                    tree[lf][2],center_stock[pos]=center_stock[pos],tree[lf][2]
                else:
                    now=sc
    if best>now:
        fin=[i[:] for i in tree]
        best=now
for i in fin:
    print(*(map(lambda x:x+1,i)))

yukicoder

結果

テストケース

ソースコード