結果

問題 No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー 👑 Kazun
提出日時 2022-07-31 15:47:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,896 ms / 2,000 ms
コード長 4,427 bytes
コンパイル時間 251 ms
実行使用メモリ 91,964 KB
スコア 137,361,754,978,717
最終ジャッジ日時 2022-10-14 21:11:35
合計ジャッジ時間 104,283 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""
作戦 0: 全テストケース固定の解答
作戦 1: (N-1) 個同じ離散振り子
作戦 2: 時間いっぱいランダム
作戦 3: 山登り
"""

#==================================================
# 関数部

def General_Binary_Increase_Search_Integer(L, R, cond, default=None):
    """ 条件式が単調増加であるとき, 整数上で二部探索を行う.

    L: 解の下限
    R: 解の上限
    cond: 条件(1変数関数, 広義単調増加を満たす)
    default: Lで条件を満たさないときの返り値
    """

    if not(cond(R)):
        return default

    if cond(L):
        return L

    R+=1
    while R-L>1:
        C=L+(R-L)//2
        if cond(C):
            R=C
        else:
            L=C
    return R

def move(start,direction,time):
    return start+direction*time

def position(B,M,E,T):
    if E==0:
        M=B
        E=1

    H=(B-M)//E
    F=2*B*H-E*H*H

    if T<B:
        return T

    T-=B
    if T<F:
        check=lambda p:T<2*p*B-p*p*E
        p=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-=F
    if 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)+M
        q,r=divmod(T,2*M)

        direction=pow(-1,H+2+q)
        start=pow(-1,H+1+q)*M
        return move(start,direction,r)
    else:
        return 0

def score_confrontation(X):
    X=[position(i,T) for i in range(N)]
    R_sum=0
    for i in range(N):
        for k in range(i+1,N):
            R_sum+=abs(X[i]-X[k])/(B[i]+B[k])

    coef=pow(10,7)*(2/(N*(N-1)))
    return round(coef*R_sum)

def score_cooperation(T: int):
    X=[position(i,T) for i in range(N)]
    H=max(X)-min(X)
    alpha=sqrt(H/20+1)
    return round(pow(10,7)/alpha)

def debug(*message):
    print(*message,file=sys.stderr)

#==================================================
# インポート
from time import *
from math import sqrt
from random import *
import sys

#==================================================
# 入力
N,K=map(int,input().split())
T=list(map(int,input().split()))
U=list(map(int,input().split()))

#==================================================
FIRST_PHASE=1.400
SECOND_PHASE=0.400

B=[0]*N; M=[0]*N; E=[0]*N
X=[[0]*N for _ in range(K)]
Y=[[0]*N for _ in range(K)]
#==================================================
# 第 1 部

BEGIN_TIME=time()
best_score=-1
while time()-BEGIN_TIME<FIRST_PHASE:
    for i in range(N):
        B[i]=randint(100,1000); M[i]=randint(100,1000)
        if B[i]<M[i]:
            B[i],M[i]=M[i],B[i]
        E[i]=randint(0,B[i]-M[i])

    for j in range(K):
        for i in range(N):
            X[j][i]=position(B[i],M[i],E[i],T[j])
            Y[j][i]=position(B[i],M[i],E[i],U[j])

    C1=0
    for j in range(K):
        R=0
        for 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=0
    for j in range(N):
        R=max(Y[j])-min(Y[j])
        C2+=round(pow(10,7)/sqrt(R/20+1))
    C2=round(C2/N)

    if best_score<C1*C2:
        best_score=C1*C2
        BB=B.copy()
        MM=M.copy()
        EE=E.copy()

#==================================================
# 第 2 部
B=BB; M=MM; E=EE

BEGIN_TIME=time()
chance=0; change=0
while time()-BEGIN_TIME<SECOND_PHASE:
    i=randint(0,N-1)

    b=randint(100,1000); m=randint(100,1000)
    if b<m:
        b,m=m,b
    e=randint(0,b-m)

    B[i],b=b,B[i]; M[i],m=m,M[i]; E[i],e=e,E[i]
    for j in range(K):
        X[j][i]=position(B[i],M[i],E[i],T[j])
        Y[j][i]=position(B[i],M[i],E[i],U[j])

    C1=0
    for j in range(K):
        R=0
        for 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=0
    for j in range(N):
        R=max(Y[j])-min(Y[j])
        C2+=round(pow(10,7)/sqrt(R/20+1))
    C2=round(C2/N)

    chance+=1
    if best_score<C1*C2:
        change+=1
        best_score=C1*C2
    else:
        B[i],b=b,B[i]; M[i],m=m,M[i]; E[i],e=e,E[i]

#==================================================
for i in range(N):
    print(B[i],M[i],E[i])

debug(change,"/",chance)
debug(best_score)
0