SRM 294 DIV1 Hard DigitByDigit

問題 Editorial

問題

digits

つの数字が入る所がある。今入っている数字はdigitsで与えられる。'_'の所は空であることを表す。

'_'の数だけ独立にランダムに順番に数字が選ばれる。
1つの数字が選ばれた時、次の数字が選ばれる前に、どこに数字を入れるかを決めなければいけない。
全ての数字が入れ終わった時、そのそれぞれを各桁として読んだものがスコアになる。
最良にプレイするときの期待値を求めよ

• 1 <= |digits| <= 50

解答

rng_58さんの解答を参考にした。
まず、期待値は線形性とかより各桁ごとに独立に計算して最後に足せばいい。
さて、最良な戦略は何か？もし全ての数字が既にわかっているとしたら大きい順に並べるのが最良。
そのように考えて、期待値の大きい順に並べるのが最良である。
また、各ターンでは残りいくつ開いているかだけわかればいい。どこが開いていようとその順番のみが大事なので。
つまり、この後の期待値を考えて、それといま見た数字を一緒にソートしたときのそれらの期待値が今の期待値になる。
これはDPになる。
vectorを持ってやってもよいし、dp[i][k]というふうにしても良い

コメント

DPの中でsortするというのが面白いと思った。
既にわかっている時の戦略から考えて、そのわかっているものを期待値に置き換えてみるというのは、限定的ではあるだろうけれどなんとなく少し良い感じ

コード

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
using namespace std;

struct DigitByDigit {
	double expectedScore(string digits) {
		static double dp[55][55];
		rer(i, 1, 50) {
			rep(k, i) dp[i][k] = 0;
			rer(d, 0, 9) {
				vector<double> v;
				rep(k, i-1) v.pb(dp[i-1][k]);
				v.pb(d);
				sort(all(v), greater<double>());
				rep(k, i) dp[i][k] += v[k] / 10;
			}
		}
		int cnt = count(all(digits), '_'), j = 0;
		double r = 0;
		rep(i, digits.size()) {
			double x = digits[i] == '_' ? dp[cnt][j ++] : digits[i] - '0';
			r += x * pow(10., (double)(digits.size() - i - 1));
		}
		return r;
	}
};