【TIOJ 1545】三國殺

原題連結：https://tioj.ck.tp.edu.tw/problems/1545

這題看完第一直覺是令$\color{white}{\space dp[N][M]\space}$為輸入$\color{white}{\space N,M\space}$時的答案，可以很輕易的發現轉移是$\color{white}{\space O(N)\space}$。
複雜度$\color{white}{\space O(N^3)\space}$，可以拿下前兩筆subtask。

不過適當的利用精度捨棄不必要的運算之後可以利用這個方法拿到第三筆subtask。
但最終還是過不了第四筆QQ。

稍微被劇透一下解之後，得知若令$\color{white}{\space dp[N]\space}$為輸入$\color{white}{\space N,N\space}$時的答案，則有等式：

$\color{white}{\space dp[i]=\frac{1}{2}\displaystyle\sum_{j=0}^{i-2}(\frac{\dbinom{n-1}{j}}{2^{n-1}}dp[i-j])+\frac{\dbinom{n-1}{n-1}}{2^{n-1}}\space}$

轉移想法來源為，枚舉閃電傳完一輪後(第$\color{white}{\space N\space}$個人傳完)，已經有$\color{white}{\space j\space}$個人被殺掉且第$\color{white}{\space N\space}$個人還活著的機率(多乘一個$\color{white}{\space \frac{1}{2}\space}$)總和起來，但必需特判剛好傳完一輪其他人全死光的情況(此時第$\color{white}{\space N\space}$個人不需要再進行閃電判斷)。

所以稍微做個移項之後可得：

$\color{white}{\space (2-\frac{\dbinom{n-1}{0}}{2^{n-1}})dp[i]=\displaystyle\sum_{j=1}^{i-2}(\frac{\dbinom{n-1}{j}}{2^{n-1}}dp[i-j])+2\frac{\dbinom{n-1}{n-1}}{2^{n-1}}\space}$

只要計算出右邊的東西就可以做個除法得到$\color{white}{\space dp[i]\space}$了。
而令$\color{white}{\space f(i,j)=\frac{\dbinom{i}{j}}{2^{i}}\space}$後可得：

$\color{white}{\space (2-f(n-1,0))dp[i]=\displaystyle\sum_{j=1}^{i-2}(f(n-1,j)dp[i-j])+2f(n-1,n-1)\space}$

令$\color{white}{\space f(i,j)\space}$的原因是因為這個函數也能DP的關係，這樣子比較能防止精度流失。

那我們就獲得了一個$\color{white}{\space O(N^2)\space}$，$\color{white}{\space N=M\space}$的做法了。

那有了$\color{white}{\space N=M\space}$的答案又能怎樣？
觀察到我們也同時能枚舉第$\color{white}{\space M\space}$個人前面被幹掉幾個人，進而轉換成$\color{white}{\space N=M\space}$的情況，所以有：

$\color{white}{\space ans(N,M)=\frac{1}{2}\displaystyle\sum_{j=0}^{M-1}(f(M-1,j)dp[N-j])\space}$

其中$\color{white}{\space N=M\space}$的case要特判，於是我們就有理論$\color{white}{\space O(N^2)\space}$的做法了OwO~~

而回想一開始通過第三個subtask的方法，我們似乎還是能透過利用精度捨棄運算的做法來優化，觀察到$\color{white}{\space f(i,j)\space}$的$\color{white}{\space j\space}$在極端值時會有極小值，所以不管在計算$\color{white}{\space f(i,j)\space}$還是$\color{white}{\space dp[i]\space}$，多開一個左右界慢慢把還在精度範圍內的區間縮小，只計算這部分就好了，這邊我精度取到$\color{white}{\space 10^{-10}\space}$剛好AC XD。

題外話，這題存在著一種不斷逼近的做法，只要一直用數學式計算第$\color{white}{\space 1\space}$輪、第$\color{white}{\space 2\space}$輪、...、第$\color{white}{\space k\space}$輪遊戲就結束，第$\color{white}{\space M\space}$個人存活的機率加起來，就會發現$\color{white}{\space k\space}$有一定大小的時候很欠剪枝，就可以在極快的時間AC了OAO

附上第一種做法的code：

	#pragma GCC optimize("Ofast","unroll-loops")
	#include <bits/stdc++.h>
	#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	#define pb push_back
	#define F first
	#define S second
	#define MEM(i,j) memset(i,j,sizeof i)
	#define ALL(v) v.begin(),v.end()
	#define MP make_pair
	#define ET cout << "\n"
	#define DB(a,s,e) {for(int i=s;i<e;i++) cout << a[i] << " ";ET;}
	using namespace std;
	typedef long long ll;
	typedef pair<int,int> pii;
	typedef pair<ll,ll> pll;
	double dp[100005],C[2][100005],CC[100005];
	const double eps=1e-10;
	int main()
	{jizz
	int n,m,l,r;
	double t,ans=0;
	cin >> n >> m,dp[0]=1,dp[1]=1,C[0][0]=1,C[1][0]=0.5,C[1][1]=0.5;
	if(m==1) CC[0]=1;
	if(m==2) CC[0]=CC[1]=0.5;
	l=0,r=1;
	for(int i=2;i<=n;++i)
	{
	for(int j=max(1,l);j<=min(r,i-2);++j)
	dp[i]+=C[i&1^1][j]*dp[i-j];
	dp[i]+=2*C[i&1^1][i-1];
	dp[i]/=(2-C[i&1^1][0]),C[i&1][0]=C[i&1^1][0]/2.;
	++r;
	for(int j=max(1,l);j<=min(r,i);++j)
	C[i&1][j]=(C[i&1^1][j]+C[i&1^1][j-1])/2.;
	while(l<r&&C[i&1][l]<eps) C[i&1][l]=0,++l;
	while(l<r&&C[i&1][r]<eps) --r;
	if(i==m-1)
	for(int j=0;j<=i;++j)
	CC[j]=C[i&1][j];
	}
	if(n==m) ans=dp[n];
	else
	{
	for(int j=0;j<m;++j)
	ans+=CC[j]*dp[n-j];
	ans/=2;
	}
	cout << fixed << setprecision(9) << ans << "\n";
	}

view raw gistfile1.txt hosted with ❤ by GitHub