kmjp's blog

競技プログラミング参加記です

Codeforces #1121 : Div2. F. Deranged Calculator

また変わった問題。
https://codeforces.com/contest/2264/problem/F

問題

変数nの値が与えられたとき、以下の要素を組み合わせ、n=1~50に対する完全順列の個数を求める単一の数式を構成せよ

  • 変数n
  • 四則演算
  • 括弧
  • 小数点以下四捨五入

解法

順列が完全順列となる確率は1/eらしい。
ということで、求めるのはround(n!/e)である。
n!とeの構成法を考える。

  • 正整数は、(n+n+n+n)/n=4のようにnを繰り返してnで割れば構成できる。
  • n!は、(1*(n≧2)+1)*(2*(n≧3)+1)* ... ((k-1)*(n≧k)+1) ... * (49*(n≧50)+1)が計算できればよい。
    • n≧xは、round(n/(n+x))で表現できる。nがx以上なら1になり、x未満なら0になるため。
  • eは2+1/2*(1+1/3*(1+1/4*(....)))と連分数で表現できる。
string getN(int n) {
	if(n==1) return "n/n";
	string ret="(n";
	while(--n>=1) ret+="+n";
	return ret+")/n";
}

string revN(int n) {
	if(n==1) return "n/n";
	string ret="(n";
	while(--n>=1) ret+="+n";
	return "n/"+ret+")";
}

string ge(int v) {
	return "round(n/(n+"+getN(v)+"))";
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	string F=getN(1);
	for(i=2;i<=50;i++) F+="*(n/n+"+ge(i)+"*"+getN(i-1)+")";
	
	string E=getN(1);
	for(i=50;i>=1;i--) E="n/n+"+revN(i)+"*("+E+")";
	
	string ret="round("+F+"/("+E+"))";
	cout<<ret<<endl;
	
}

まとめ

この完全順列の確率をそもそも知らなかった。