https://codeiq.jp/q/1704

readme.txt

【解答】
・第１問：2.01966
・第２問：3.10849098132
【方針】
(回答時コメント）
　良い方法が思いつかなかったので、苦し紛れのDPでの数え上げです。

　0から9の10文字の個数をそれぞれA[0],A[1],A[2],…,A[9]とすると、
　今回、n<=12なので、各A[i]は精々4bitで表されることから、64bit整数Sを用いて S=ΣA[i]<<4*i for i=0 to 9 で
　出目の状態をエンコードできます。
　
　各状態の組み合わせを辞書で管理しておき、n-1までの出目に
　n番目の出目を加えた際にできる組み合わせの数を順次DPで計算していきます。
　（n文字の時の状態数は10Hn = (n+9)C(9) で n=12で293930程度に収まります)
　
　最後に各状態からもっとも多い出現回数を復元して、組み合わせの数を掛けたものを
　足し合わせて、10^n で割ることで期待値を計算しました。
　
　計算量は O(10*n*10Hn)くらいでは抑えられているとは思いますが、ローカルで0.5secくらいなので
　もうちょっと良い解があると思っています。。

（補足）
Calc1：ナイーブ解　000000から999999まで文字列で作ってスコアを計算
Calc2：半分全列挙解　ナイーブに半分全列挙したのち、それらから2つ選んで足し合わせてスコアを計算する。
　　　　　　　　　　 DP解の回りくどくて遅いバージョン
Calc3：DP解

slotMachine4.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
class TEST{
	static void Main(){
		new Sol().Solve();
	}
}

class Sol{
	public void Solve(){
		
		var sw=new Stopwatch();
		sw.Start();
		//Console.WriteLine("N={0},Expectation={1}",1,Calc1(1));
		//Console.WriteLine("N={0},Expectation={1}",2,Calc1(2));
		//Console.WriteLine("N={0},Expectation={1}",3,Calc1(3));
		
		//Console.WriteLine("N={0},Expectation={1}",6,Calc1(6));
		//Console.WriteLine("N={0},Expectation={1}",6,Calc2(6));
		//Console.WriteLine("N={0},Expectation={1}",6,Calc3(6));
		
		//Console.WriteLine("N={0},Expectation={1}",12,Calc2(12));
		Console.WriteLine("N={0},Expectation={1}",1,Calc3(1));
		Console.WriteLine("N={0},Expectation={1}",2,Calc3(2));
		Console.WriteLine("N={0},Expectation={1}",3,Calc3(3));
		Console.WriteLine("N={0},Expectation={1}",6,Calc3(6));
		Console.WriteLine("N={0},Expectation={1}",12,Calc3(12));
		Console.WriteLine(sw.ElapsedMilliseconds+"[ms]");
	}
	
	double Calc1(int n){
		//Naive
		int M=(int)Math.Pow(10,n);
		double ret=0.0;
		for(int i=0;i<M;i++){
			String s=String.Format("{0:D0"+n+"}",i);
			int[] a=new int[10];
			for(int j=0;j<s.Length;j++){
				a[s[j]-'0']++;
			}
			ret+=a.Max();
		}
		return ret/(double)M;
	}
	double Calc2(int n){
		//半分全列挙・・・
		int n1=n/2;
		int n2=n-n1;
		
		int M1=(int)Math.Pow(10,n1);
		Dictionary<long,long> D1=new Dictionary<long,long>();
		for(int i=0;i<M1;i++){
			String s=String.Format("{0:D0"+n1+"}",i);
			long k1=0;
			for(int j=0;j<s.Length;j++){
				k1+=1L<<(4*(s[j]-'0'));
			}
			if(D1.ContainsKey(k1)==false)D1.Add(k1,0);
			D1[k1]++;
		}
		
		int M2=(int)Math.Pow(10,n2);
		Dictionary<long,long> D2=new Dictionary<long,long>();
		for(int i=0;i<M2;i++){
			String s=String.Format("{0:D0"+n2+"}",i);
			long k2=0;
			for(int j=0;j<s.Length;j++){
				k2+=1L<<(4*(s[j]-'0'));
			}
			if(D2.ContainsKey(k2)==false)D2.Add(k2,0);
			D2[k2]++;
		}
		
		double ret=0.0;
		foreach(var k1 in D1.Keys){
			foreach(var k2 in D2.Keys){
				long k=k1+k2;
				long max=0;
				for(int i=0;i<10;i++){
					long x=((k>>(4*i))&0xF);
					max=Math.Max(x,max);
				}
				
				ret+=(double)max*(double)D1[k1]*(double)D2[k2];
			}
		}
		
		return ret/(double)M1/(double)M2;
	}
	
	double Calc3(int n){
		
		//DP・・・
		Dictionary<long,long> Dnow=new Dictionary<long,long>();
		for(int i=0;i<10;i++){
			Dnow.Add(1L<<(4*i),1);
		}
		for(int t=1;t<n;t++){
			var Dnxt=new Dictionary<long,long>();
			foreach(var k in Dnow.Keys){
				for(int i=0;i<10;i++){
					long k2=k+(1L<<(4*i));
					if(!Dnxt.ContainsKey(k2))Dnxt.Add(k2,0);
					Dnxt[k2]+=Dnow[k];
				}
			}
			Dnow=Dnxt;
		}
		
		double ret=0.0;
		foreach(var k in Dnow.Keys){
			long max=0;
			for(int i=0;i<10;i++){
				long x=((k>>(4*i))&0xF);
				max=Math.Max(x,max);
			}
			ret+=(double)max*(double)Dnow[k];
		}
		for(int t=0;t<n;t++)ret/=10.0;
		return ret;
	}
}