結果
問題 | No.2057 Ising Model |
ユーザー |
![]() |
提出日時 | 2022-08-08 03:46:52 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,387 bytes |
コンパイル時間 | 262 ms |
コンパイル使用メモリ | 82,404 KB |
実行使用メモリ | 56,656 KB |
最終ジャッジ日時 | 2024-09-21 02:00:02 |
合計ジャッジ時間 | 3,553 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 44 |
ソースコード
def naive(n,a,b):ans=2**63def f(s):ans=0for i in range(1,n+1):ans-=b*s[i]if i<n:ans+=a*s[i]*s[i+1]return ansfor bit in range(2**n):s=[0]*(n+1)for i in range(n):if (bit>>i)&1:s[i+1]=1else:s[i+1]=-1ans=min(ans,f(s))return ansdef sol1(n,a,b):dp=[[2**63,2**63] for i in range(n+1)]dp[1][1]=-bdp[1][0]=bfor i in range(2,n+1):dp[i][1]=min(dp[i-1][1]+a-b,dp[i-1][0]-a-b)dp[i][0]=min(dp[i-1][1]-a+b,dp[i-1][0]+a+b)return min(dp[n][1],dp[n][0])def mul(a,b):n=len(a)res=[[2**63]*n for i in range(n)]for i in range(n):for j in range(n):for k in range(n):res[i][j]=min(res[i][j],a[i][k]+b[k][j])return resdef mpow(a,k):if k==1:return ares=mpow(a,k//2)res=mul(res,res)if k%2==1:res=mul(res,a)return resdef sol2(n,a,b):M=[[a+b,-a+b],[-a-b,a-b]]M=mpow(M,n-1)dp0=min(M[0][0]+b,M[0][1]-b)dp1=min(M[1][0]+b,M[1][1]-b)return min(dp0,dp1)from random import randrange as rdcnt=0while 0:cnt+=1print(cnt)n,a,b=rd(2,100),rd(1,100),rd(1,100)#ansn=naive(n,a,b)ans1=sol1(n,a,b)ans2=sol2(n,a,b)if ans2!=ans1:print(n,a,b)break