SRM 252 DIV1 Hard WordBoggle

問題文は見つけられなかった(Editorial, Match OverviewsからのStaticsが無い)

問題

4*4のボードがある。
まずここに、"位置も向きもランダムに"16つのキューブcubesを全てはめる。
各キューブのそれぞれの面は違う文字である。
その後辞書dictに登録されている単語を見つける。
どこでも最初の文字を始められて、上下左右のみに移動して次の文字を見つけることができる。
一度通った所を再び通ることはできない。
ボードにある全ての単語のパスに対して得点が加算される。
同じ単語でもパスの一部を共有していても、パスの一部が違っていたら別個に得点が加算される。
それぞれの単語の得点は単語の文字数の2乗(|words[i]|^2)である。
得点の期待値を求めよ

解答

Practice Roomのrng_58さんの解答を参考にした。
まず、各単語に対して別個に期待値を計算して、最後に総和を取れば良い。(期待値の線形性)
各単語の得点は、(|words[i]|^2 * あり得るキューブの組み合わせの期待値 * |words[i]|つのキューブが連結なところに並ぶ確率)のような形で求められる。
"あり得るキューブの組み合わせの期待値"のところは、2^16のビットマスクを持つDPで1つずつ試していけばいい。各キューブのそれぞれの面は違う文字であることに注意。
"xつのキューブが連結なところに並ぶ確率"は、(全ての連結な配置の数 / (全ての配置 = 16 * (16-1) * ... (16-x+1)))となる。
"全ての連結な配置の数"はdfsで数えればいい。
そんな感じか

コード

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#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 reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define all(o) (o).begin(), (o).end()
using namespace std;
typedef vector<string> vs;
bool b[4][4];
struct WordBoggle {
	vs c; string w;
	int dfs(int i, int y, int x) {
		static const int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};
		int r = 0;
		b[y][x] = 1;
		if(i == 1) {
			r = 1;
		} else rep(d, 4) {
			int yy = y + dy[d], xx = x + dx[d];
			if(yy<0||yy>=4||xx<0||xx>=4||b[yy][xx]) continue;
			r += dfs(i-1, yy, xx);
		}
		b[y][x] = 0;
		return r;
	}
	double expectedScore(vector <string> cubes, vector <string> dict) {
		c = cubes; int n = dict.size();
		static double connect[9];
		rer(i, 1, 8) {
			connect[i] = 0;
			rep(y, 4) rep(x, 4) connect[i] += dfs(i, y, x);
			rer(j, 16-i+1, 16) connect[i] /= j * 1.;
		}
		double r = 0;
		rep(ii, n) {
			w = dict[ii];
			int a = 0;
			static int dp[1<<16];
			dp[0] = 1;
			reu(i, 1, 1<<16) {
				int x = __builtin_popcount(i);
				dp[i] = 0;
				if(x > w.size()) continue;
				rep(j, 16) if(((i >> j) & 1) && count(all(c[j]), w[x - 1])) dp[i] += dp[i &~ (1 << j)];
				if(x == w.size()) a += dp[i];
			}
			r += a * connect[w.size()] / pow(6., w.size()*1.) * w.size() * w.size();
		}
		return r;
	}
};