SRM 229 DIV1 Hard Hangman42
問題
まず最初にランダムな単語がwordsの中から選ばれる。
最初はその単語のそれぞれの文字は隠されている。
各ターン、プレイヤーは文字を一文字言うことができる。最初に選ばれた単語の中にその文字があるなら、その部分がわかり、もう一度そのプレイヤーのターンができる。
各ターン、プレイヤーは文字のかわりに単語を言うこともできる。単語が正解と同じなら勝ちである。
両者が最良にプレイするとき、先攻の勝つ確率を求めよ
- 1 <= |words| <= 10
解答
ゲームDP。しかし色々と自明でないところがあると思う(自分が証明力ないだけ？)。よくわかってない。
状態として「今ありえる単語の集合」のビットマスクのみを持つ。
これが状態として十分なのは考えればわかるが、例えばもし既に言った文字を言おうとしても、その状態は変わらないから問題ない。
言う文字を全探索して、最初に選ばれた単語を可能な中から全探索、平均を取る形になる。
更新時に状態が変わらないことがある。この場合はその文字を言うことをやめる。
これは、あまりよくわかってないが、なんかそういうことをしても意味ないっぽい。
次に、最初に選ばれた単語の中に文字があってもう一度ターンができる、という判断だが、これは最初に選ばれた単語の中にその文字が入っているか？だけで判断できる。
なぜかというと、既に言った文字の場合は状態が変わらないので上記のように除外されるからである。
あと問題なのが単語を言うタイミング。
これは可能な単語が1つになった時に言えばよく、そうなるまで言う必要はない。
あまりよくわかってないが、もし2つ以上可能な単語があるなかで単語を言っても確率が0.5以下であって、状態が変わらないので意味ないらしい？。
コメント
よくわかってない。
でも実際には適当にやってAC！でいいんだろうな。
そのために「状態はこれだけもてばあれがこうなるし大丈夫じゃね？」とか「状態が変わらないときは取りあえず無視するか」とかは考えて、うまくいきそうなら試してみよう。
コード
#include <string> #include <vector> #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 mset(m,v) memset(m,v,sizeof(m)) using namespace std; typedef long long ll; typedef vector<string> vs; double dp[1<<10]; struct Hangman42 { vs w; int n, m; double rec(int mask) { if(dp[mask]==dp[mask]) return dp[mask]; int count = __builtin_popcount(mask); double r = 0; if(count == 1) r = 1; else rer(c, 'a', 'z') { double x = 0; rep(i, n) if((mask >> i) & 1) { bool q = false; rep(k, m) q |= w[i][k] == c; int nmask = 0; ll ans = 0; rep(k, m) if(w[i][k] == c) ans |= 1LL << k; rep(j, n) if((mask >> j) & 1) { ll t = 0; bool b = true; rep(k, m) if(w[j][k] == c) t |= 1LL << k, b &= w[i][k] == w[j][k]; if(t == ans && b) nmask |= 1 << j; } if(mask == nmask) { x = 0; break; } else x += q ? rec(nmask) : 1 - rec(nmask); } r = max(r, x / count); } return dp[mask] = r; } double probability(vector <string> words) { w = words, n = w.size(), m = w[0].size(); mset(dp, -1); return rec((1 << n) - 1); } };
