CodeChef October Challenge 2012 "Need More Diamonds"

最初にやったこと（愚直DP解　TLE）

与えられた配列 $V$ の、 $[\ell,r)$ の範囲が残った状態で先手の番が来たとき、
それ以降の先手が獲得するスコアの期待値を $f(\ell, r)$ とおく。

（１）先手が左端（ $V_\ell$ ）を取る場合
　　後手は $V_{\ell+1}$ か $V_{r-1}$ のどちらかを取るので、
　　次に先手の番が来るときの $V$ の状態は以下の2通りになる。
　　　・ $V_{\ell+2}\:, \;\; \dots, \;\; V_{r-2}\:, \;V_{r-1}$ 　（後手が $V_{\ell+1}$ をとった場合　 $[\ell+2,\:r)$ が残った状態で先手の番になる）
　　　・ $V_{\ell+1}\:, \;V_{\ell+2}\;,\;\; \dots, \;\; V_{r-2}$ 　（後手が $V_{r-1}$ をとった場合　 $[\ell,\:r-1)$ が残った状態で先手の番になる）
　　このどちらかが1/2の確率で起こるので、これ以降の期待値は
　　　　 $V_{\ell}\;+\;\frac{1}{2}\:(f(\ell+2,\:r)\;+\;f(\ell+1,\;r-1)\:) \mbox{ (eq. 1)}$
　　と書ける。

（２）先手が右端（ $V_{r-1}$ ）を取る場合
　　（１）と同様に
　　　　 $V_{r-1}\;+\;\frac{1}{2}\:(f(\ell,\:r-2)\;+\;f(\ell+1,\;r-1)\:) \mbox{ (eq. 2)}$
　　となる。

（１）、（２）はそれぞれ1/2の確率で起こるので、
　　　　 $f(\ell,\:r)\;=\;\frac{1}{2}\:(\mbox{ (eq. 1)}\;+\mbox{ (eq. 2)}\:)$
　　　　 $\quad\quad\quad=\;\frac{1}{2}\:(V_\ell\:+\:V_{r-1}\:+\:f(\ell+1,\:r-1)\:+\:\frac{1}{2}\:(\:f(\ell+2,\:r)\:+\:f(\ell,\:r-2)\:)\:)$
となる。

#include <cstdio>
double memo[2010][2010];
int v[2010];
double func(int l, int r)
{
    if (r-l<=0) return 0;    // 1つも残っていない
    if (r-l==1) return v[l]; // v[l] (==v[r-1]) だけが残っている
    double& res=memo[l][r];
    if (res>-0.5) return res;
    return res=0.5*(v[l]+v[r-1]+func(l+1,r-1)+0.5*(func(l+2,r)+func(l,r-2)));
}
int main()
{
    int T; scanf("%d",&T);
    while (T--) {
        int n; scanf("%d",&n);
        for(int i=1;i<=n;++i) scanf("%d",v+i);
        for(int i=0;i<=n+1;++i) for(int j=0;j<=n+1;++j) memo[i][j]=-1;
        printf("%.3f\n",func(1,n+1));
    }
    return 0;
}

計算量はたぶんO(T*N*N)。
1<=T<=500 , 1<=N<=2000 なので最大で 500 * 2000 * 2000 = 2 * 10^9 。
これじゃさすがにCodeChefじゃなくても余裕でTLEっぽいのでボツ。

次にやったこと（数列観察ゲー　Accepted）
少々ややこしいので具体例で説明。
例えばN=4のとき、ゲームの進み方は以下の8通りがある。

この中で先手が取るもの（図で色がついている部分）の、1〜4それぞれの出現回数を並べると
　　5, 3, 3, 5　（1が5個、2が3個、3が3個、4が5個）
という数列が得られる。

で、これを使って
　　 $(V_1\,\times\,5\:+\:V_2\,\times\,3\:+\:V_3\,\times\,3\:+\:V_4\,\times\,5)\:/\:(5+3+3+5)$
とでもすれば答えになるんじゃね？と思ってN=1〜3についても同様に数列を作ってサンプルを計算してみた。
100.000　(正解 100.000）
21.000　（正解 21.000）
4.250　（正解 9.500）
5.000　（正解 10.000）
…合わない。N=3とN=4のときは2倍しないと合わない。

この2ってなんだ？
1ゲームあたりの先手の手数（上の図でいうと色のついている列数）っぽいな。
よし、そういうことにしよう。

ということで
・与えられた数列 $V$ の要素数を $n$
・上述の手順で得られる数列を $\{A_n\}$
・ $\{A_n\}$ の $i$ 番目の要素を $A_{n,\,i}$
・数列 $\{A_n\}$ の総和を $S_n$
・1ゲームあたりの先手の手数を $H_n$
とおくと、

　　　 $\sum_{i=1}^{n}\,V_i\,\times\,A_{n,\,i}\,/\,S_n\,\times\,H_n \mbox{ (eq. 3)}$

が求めるべき答えになりそう（なんかしらんけど）。
（実際これが正解だった。なんかしらんけど。）

$H_n$ は (n+1)/2 で計算できるので、あとは $\{A_n\}$ が求められればOK。
とりあえず 1<=n<=10 のときを列挙してみる。

// {An}を求める
#include <vector>
#include <set>
#include <cstdio>
#include <cstdlib>
using namespace std;
void func(set<vector<int> >& s, vector<int> v, int l, int r)
{
    if (r-l<1) return;
    if (r-l==1) { v.push_back(l+1); s.insert(v); return ;}
    v.push_back(l+1);
    func(s, v, l+1, r);
    v[v.size()-1]=r;
    func(s, v, l, r-1);
}
int main(int argc, char** argv)
{
    int N=atoi(argv[1]);
    for(int n=1;n<=N;++n) {
        set<vector<int> > s;
        vector<int> v;
        func(s,v,0,n);
        vector<int> c(n+1);
        for(typeof(s.begin())i=s.begin();i!=s.end();++i){
            vector<int> t=*i;
            for(int j=0;j<t.size();++j) if(j%2==0) c[t[j]]++;
        }
        printf("%2d:\t",n);
        for(int i=1;i<=n;++i)printf("%4d ",c[i]);
        puts("");
    }
    return 0;
}

これからパスカルの三角形っぽく計算出来ないものかと規則性をさがす。

みつからない。一日中眺めててもなにも見つからない。

ということで先手だけじゃなくて後手についても $\{A_n\}$ と同様の数列（ $\{B_n\}$ とする）を作って並べてみる。

サクッと発見。こんなかんじ。

　　　 $\large\left\{\begin{array}{ccll}A_{1,1}&=&1&\\ B_{1,1}&=&0&\\ A_{n,1}&=&A_{n,n}=A_{n-1,1}\:+\:2B_{n-1,1}&\quad(n\,>\,1)\\B_{n,1}&=&B_{n,n}=A_{n-1,1}&\quad(n\,>\,1)\mbox{ (eq. 4)}\\A_{n,j}&=&B_{n,j-1}\:+\:B_{n,j}&\quad(n\,>\,1\:,\:j\,>\,1)\\B_{n,j}&=&A_{n,j-1}\:+\:A_{n,j}&\quad(n\,>\,1\:,\:j\,>\,1)\end{array}$

    int A[2010][2010],B[2010][2010];
    A[1][1]=1;
    B[1][1]=0;
    for(int i=2;i<=2000;++i) {
        A[i][1]=A[i][i]=A[i-1][1]+2*B[i-1][1];
        B[i][1]=B[i][i]=A[i-1][1];
        for(int j=2;j<i;++j) {
            A[i][j]=B[i-1][j-1]+B[i-1][j];
            B[i][j]=A[i-1][j-1]+A[i-1][j];
        }
    }

これで解ける・・・わけない。こんなもんあっさりオーバーフローするわ。
ここでちょっと $S_n$ をよく見てみたら
　　　　 $S_n\;=\;2^{n-1}\:\times\;H_n\mbox{ (eq. 5)}$
になってるのを発見（なんかしらんけど）。これを使うと (eq. 3) は

　　　　 $\sum_{i=1}^{n}\,V_i\,\times\,A_{n,\,i}\,/\,2^{n-1} \mbox{ (eq. 6)}$

とすっきりした形になる。
$P_{n,\,i}\:=\:A_{n,\,i}\:/\:2^{n-1}\quad,\quad Q_{n,\,i}\:=\:B_{n,\,i}\:/\:2^{n-1}$ とおくと、(eq. 4) をまるごと $2^{n-1}$ で割って

　　　　 $\large\left\{\begin{array}{ccll}P_{1,1}&=&1&\\ Q_{1,1}&=&0&\\ P_{n,1}&=&P_{n,n}=\frac{1}{2}P_{n-1,1}\:+\:Q_{n-1,1}&\quad(n\,>\,1)\\Q_{n,1}&=&Q_{n,n}=\frac{1}{2}P_{n-1,1}&\quad(n\,>\,1)\mbox{ (eq. 7)}\\P_{n,j}&=&\frac{1}{2}$Q_{n,j-1}\:+\:Q_{n,j}$&\quad(n\,>\,1\:,\:j\,>\,1)\\Q_{n,j}&=&\frac{1}{2}$P_{n,j-1}\:+\:P_{n,j}$&\quad(n\,>\,1\:,\:j\,>\,1)\end{array}$

が得られる。また、 (eq. 6) は

　　　　 $\sum_{i=1}^{n}\,V_i\,\times\,P_{n,\,i}$

となる。これでオーバーフローせずに答えが求められる。めでたしめでたし。

// 計算量は O(N*N + T*N) かな
#include <cstdio>
#include <cstdlib>
#include <cstring>
double P[2010][2010],Q[2010][2010];
int main()
{
	P[1][0]=1;
	Q[1][0]=0;
	for(int i=2;i<=2000;++i) {
		P[i][0]=P[i][i-1]=0.5*P[i-1][0]+Q[i-1][0];
		Q[i][0]=Q[i][i-1]=0.5*P[i-1][0];
		for(int j=1;j<i-1;++j) {
			P[i][j]=0.5*(Q[i-1][j-1]+Q[i-1][j]);
			Q[i][j]=0.5*(P[i-1][j-1]+P[i-1][j]);
		}
	}
	int T; scanf("%d",&T);
	while (T--) {
		int n; scanf("%d",&n);
		double res=0;
		for(int i=0;i<n;++i){
			int v; scanf("%d",&v);
			res+=v*P[n][i];
		}
		printf("%.6f\n",res);
	}
	return 0;
}