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; } };