結果
問題 | No.2057 Ising Model |
ユーザー |
![]() |
提出日時 | 2022-08-09 07:42:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 46 ms / 2,000 ms |
コード長 | 1,922 bytes |
コンパイル時間 | 349 ms |
コンパイル使用メモリ | 82,500 KB |
実行使用メモリ | 55,168 KB |
最終ジャッジ日時 | 2024-09-21 01:59:46 |
合計ジャッジ時間 | 3,881 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 44 |
ソースコード
def naive(n,a,b): ans=2**63 def f(s): ans=0 for i in range(1,n+1): ans-=b*s[i] if i<n:ans+=a*s[i]*s[i+1] return ans for bit in range(2**n): s=[0]*(n+1) for i in range(n): if (bit>>i)&1: s[i+1]=1 else: s[i+1]=-1 ans=min(ans,f(s)) return ans def sol1(n,a,b): dp=[[2**63,2**63] for i in range(n+1)] dp[1][1]=-b dp[1][0]=b for 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 res def mpow(a,k): if k==1:return a res=mpow(a,k//2) res=mul(res,res) if k%2==1: res=mul(res,a) return res def 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) def sol3(n,a,b): def f(x): if 2*x==n:return (2*b-4*a)*x+a*(n+1)-b*n return (2*b-4*a)*x+a*(n-1)-b*n return min(f(0),f((n-1)//2),f(n//2)) def fake1(n,a,b): def f(x): return (2*b-4*a)*x+a*(n-1)-b*n return min(f(0),f(n//2)) def fake2(n,a,b): def f(x): return (2*b-4*a)*x+a*(n-1)-b*n return min(f(0),f((n-1)//2)) from random import randrange as rd cnt=0 n,a,b=map(int,input().split()) print(sol2(n,a,b)) exit() while 0: cnt+=1 print(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) ans3=sol3(n,a,b) ansf1=fake1(n,a,b) ansf2=fake2(n,a,b) if not (ans2==ansf1==ansf2): print(n,a,b) print(ans2,ansf1,ansf2) break