結果
問題 | No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance |
ユーザー |
👑 ![]() |
提出日時 | 2022-10-14 22:38:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,924 ms / 2,000 ms |
コード長 | 3,808 bytes |
コンパイル時間 | 240 ms |
実行使用メモリ | 87,280 KB |
スコア | 1,116,899,169,693,692 |
最終ジャッジ日時 | 2022-10-14 22:40:09 |
合計ジャッジ時間 | 105,120 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
""" Note"""#==================================================# 関数部def General_Binary_Increase_Search_Integer(L, R, cond, default=None):""" 条件式が単調増加であるとき, 整数上で二部探索を行う.L: 解の下限R: 解の上限cond: 条件(1変数関数, 広義単調増加を満たす)default: Lで条件を満たさないときの返り値"""if not(cond(R)):return defaultif cond(L):return LR+=1while R-L>1:C=L+(R-L)//2if cond(C):R=Celse:L=Creturn Rdef move(start,direction,time):return start+direction*timedef position(B,M,E,T):if E==0:M=BE=1H=(B-M)//EF=2*B*H-E*H*Hif T<B:return TT-=Bif T<F:check=lambda p:T<2*p*B-p*p*Ep=General_Binary_Increase_Search_Integer(1,H,check,None)direction=pow(-1,p)start=pow(-1,p-1)*(B-(p-1)*E)return move(start,direction,T-(2*(p-1)*B-pow(p-1,2)*E))T-=Fif T<(B-H*E)+M:direction=pow(-1,H+1)start=pow(-1,H)*(B-H*E)return move(start,direction,T)if M>0:T-=(B-H*E)+Mq,r=divmod(T,2*M)direction=pow(-1,H+2+q)start=pow(-1,H+1+q)*Mreturn move(start,direction,r)else:return 0def score_confrontation(B,M,E,mode=False):X=[[0]*N for _ in range(K)]C1=0coef=(2*pow(10,7))/(N*(N-1))for j in range(K):for i in range(N):X[j][i]=position(B[i], M[i], E[i], T[j])R=0for i in range(N):for k in range(i+1, N):R+=abs(X[j][i]-X[j][k])/(B[i]+B[k])C1+=round(coef*R)C=round(C1/N)if mode:return C, Xelse:return Cdef score_cooperation(B,M,E,mode=False):Y=[[0]*N for _ in range(K)]C2=0for j in range(K):for i in range(N):Y[j][i]=position(B[i],M[i],E[i],U[j])R=max(Y[j])-min(Y[j])C2+=round(pow(10,7)/sqrt(R/20+1))C=round(C2/N)if mode:return C,Yelse:return Cdef calculate(B,M,E):C1=score_confrontation(B,M,E)C2=score_cooperation(B,M,E)return C1*C2def scoring(X,Y):C1=0for j in range(K):R=0for i in range(N):for k in range(i+1,N):R+=abs(X[j][i]-X[j][k])/(B[i]+B[k])C1+=round((2*pow(10,7))/(N*(N-1))*R)C1=round(C1/N)C2=0for j in range(N):R=max(Y[j])-min(Y[j])C2+=round(pow(10,7)/sqrt(R/20+1))C2=round(C2/N)return C1*C2def debug(*message):print(*message,file=sys.stderr)#==================================================# インポートfrom time import *from math import sqrtfrom random import *import sys#==================================================# 入力N,K=map(int,input().split())T=list(map(int,input().split()))U=list(map(int,input().split()))#==================================================BEGIN_TIME=time()TIME_LIMIT_A=1.800#==================================================# 初期解best_score=-1E=[1]*NB=[1]*Nwhile time()-BEGIN_TIME<TIME_LIMIT_A:for i in range(N):rand=random()if rand<=0.45:B[i]=1elif rand<=0.90:B[i]=2else:B[i]=3M=[randint(1,B[i]) for i in range(N)]score=calculate(B,M,E)if best_score<score:best_score=scoreBest_B=B.copy()Best_M=M.copy()#==================================================for b,m,e in zip(Best_B,Best_M,E):print(b,m,e)debug("Confrontation")debug(score_confrontation(B,M,E))debug("Cooperation")debug(score_cooperation(B,M,E))debug(best_score)