結果

問題 No.352 カード並べ
ユーザー startcppstartcpp
提出日時 2016-03-12 00:20:11
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 1,496 bytes
コンパイル時間 518 ms
コンパイル使用メモリ 55,980 KB
実行使用メモリ 82,936 KB
最終ジャッジ日時 2023-10-25 06:18:09
合計ジャッジ時間 7,179 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

//だめだ
//数字を1,2,3…とみていくのではなく、挿入箇所を左から順に見ていく。それで、どの数字を入れるかを全探索する。
//すると、(最も右のカード(N通り), 未使用のカード組(2^N通り))から「次の操作でかかるコスト」を計算できる。
//そして、操作後の(最も右のカード(N通り), 未使用のカード組(2^N通り))もそれ自身から計算できる。
//コスト和は、「操作でかかるコスト + これからのコスト」を計算すれば求まる。期待値は適当に平均とるだけ。
//…O(N * 2^N)のDPを組める気がしてきた！！

#include <iostream>
#include <cstdio>
using namespace std;

int n;
double dp[21][1<<21];

//簡単化のため、depも引数にするが、これが無くてもDPできる。
double dfs(int prev, int remain, int dep){
	if( dep == n ){ return 0; }
	//if( dp[prev][remain] >= 0 ){ return dp[prev][remain]; }
	double ret = 0;
	for( int i = 1; i <= n; i++ ){
		if((remain >> i) & 1){	//数字iが未使用
			remain &= ~(1 << i);
			int cst = (dep == 0 || dep == n-1) ? 1 : prev * i;
			ret += cst + dfs(i, remain, dep + 1);
			remain |= (1 << i);
		}
	}
	ret /= n - dep;	//未使用の個数で割る
	return (dp[prev][remain] = ret);
}

int main(){
	cin >> n;
	for( int i = 0; i <= n; i++ )
		for( int j = 0; j < 1<<(n+1); j++ )
			dp[i][j] = -1;
	
	int remain = (1<<(n+1)) - 2;
	printf("%.14f\n", dfs(-1, remain, 0));
	return 0;
}
0