TopCoder SRM 637 Div1
今回はSRM637の解説です。問題内容は
- Easy: 確率(?)
- Medium: Grandy数
となっております。それでは行きます。
Easy (250点)
問題
1から2Nまでの整数がある。この整数を2人でN個ずつに分けて、1つずつ出して勝負していく。数が大きい方が1ポイントを獲得する。あなたは相手が数を出す順番が部分的にわかっていて、それが数列で与えられる。分からない箇所は-1になっている。あなたはそれを見て最適な数字を出す順番を決める。この時、得られるポイントの期待値はいくつか？
解法
まず、相手の出す数がすべてわかっている場合について考える。
もし、相手の出す数より大きい数を持っているなら、それよりギリギリ大きい数を出すのが良く、もし大きい数を持っていないなら、一番小さい数を出すのがよい。
もし-1が混じっていたら、上のやり方で、-1以外の数と対戦させる数を最初に決める。upper_boundを使うと結構簡単に書ける。
で、-1の部分はどうするかというと、これはコインを投げて神に祈ると書いてあるので、全部の場合を試せばいい。
とはいっても、全部を真面目に列挙していては時間が足りないので、少し考える。
どの数字の出し方も等確率で現れることから、-1の部分に入りうる数に対して、余っている数が勝てるのか勝てないのかを判断していく。
この対戦表みたいなもので勝てる数を余っている数で割ればほしい期待値が求まる。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <tuple>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;
typedef long long lint;
typedef pair<lint,lint> pll;
#define REP(i,n) for(lint i=0; i<n; i++)
#define REPP(i,s,e) for(lint i=s; i<=e; i++)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
class GreaterGame {
public:
double calc(vector <int> h, vector <int> s) {
int n = h.size();
set<int> st;
REP(i,2*n) st.insert(i+1);
REP(i,n) {
st.erase(h[i]);
if(s[i] != -1) st.erase(s[i]);
}
sort(ALL(h));
double ans = 0.0;
bool update = true;
while(update) {
update = false;
REP(i,h.size()) {
if(s[i] != -1) {
auto it = upper_bound(ALL(h), s[i]);
if(it != h.end()) {
h.erase(it);
ans += 1.0;
} else {
h.erase(h.begin());
}
s.erase(s.begin() + i);
update = true;
break;
}
}
}
int m = h.size();
vector<int> re(ALL(st));
if(m != 0) {
int cnt = 0;
REP(i,m) REP(j,m) {
if(h[i] > re[j]) cnt++;
}
ans += cnt / (double)m;
}
return ans;
}
};
Medium (500点)
問題
高さが2で横幅がNのグリッドが与えられる。各マスは白か黒に塗られていて、初期状態では一番左のマスの上下いずれかから、白いマスだけを通って一番右のマスの上下いずれかにたどり着くことができる。2人のプレイヤーは交互に白いマスを黒く塗っていくのだが、上記のように一番左から一番右に移動できなくしてしまった方が負けとなる。与えられた状態から先手と後手どちらが勝つのかを調べよ。
解法
Grandy数を求めて勝敗を決定する。
ある列に注目した時に上下いずれかに黒マスがあれば、その列はもうこれ以上塗れない。なので、黒マスがある列でグリッドを分割する。
分割されたグリッドは当然ながらすべて白のマスである。ただし、両端には制約がついていて、黒マスがあった列と同じ列にしか置くことができないことに注意する。
したがって、分割されたグリッドの状態は、その幅、左側についている制約、右側についている制約の3つから決まる。
ちなみに、元のグリッドの両端に限っては、もし黒マスがなければ制約なしになる。
あとは、細かな部分だが、
- 幅が0の時はもうこれ以上置けないので先手負け。
- 幅が1の時は、両側に同じ制約がついているか、少なくともどちらか一方が制約なしなら、後手勝ち、それ以外は先手勝ち。
という条件を用いる。
常識かもしれないのですが一応補足しておくと、Grandy数は、遷移できる状態のGrayndy数に現れないもののうち最小のものになる。
また、ある手を打った時にゲームの状態が分割される(今回の場合でいえば左右2つのゲーム)時には、その分割後のゲームのGrandy数のXORがその手を打つ遷移のGrandy数になる。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;
typedef long long lint;
typedef pair<lint,lint> pll;
#define REP(i,n) for(int i=0; i<n; i++)
#define REPP(i,s,e) for(int i=s; i<=e; i++)
#define ALL(a) (a).begin(), (a).end()
#define PPP(a) #a << " = " << (a) << ", "
#define PRT(a) cerr << PPP(a) << endl
#define PRT2(a, b) cerr << PPP(a) << PPP(b) << endl
#define PRT3(a, b, c) cerr << PPP(a) << PPP(b) << PPP(c) << endl
int memo[1000][4][4];
class PathGame {
public:
int nimber(int w, int l, int r) {
if(w == 0) return 0;
if(w == 1) {
if(l == r) return 1;
if(l == 0) return 1;
if(r == 0) return 1;
return 0;
}
if(memo[w][l][r] != -1) return memo[w][l][r];
set<int> ss;
if(l != 2) ss.insert(nimber(w-1, 1, r));
if(l != 1) ss.insert(nimber(w-1, 2, r));
if(r != 2) ss.insert(nimber(w-1, l, 1));
if(r != 1) ss.insert(nimber(w-1, l, 2));
for(int i=1; i<w-1; i++) {
ss.insert(nimber(i, l, 1) ^ nimber(w-i-1, 1, r));
ss.insert(nimber(i, l, 2) ^ nimber(w-i-1, 2, r));
}
int nim = 0;
while(ss.count(nim)) nim++;
memo[w][l][r] = nim;
return nim;
}
string judge(vector <string> board) {
int n = board[0].size();
vector<vector<int> > bd(2, vector<int>(n, 0));
REP(i,2) REP(j,n) bd[i][j] = board[i][j] == '#' ? 1 : 0;
memset(memo, -1, sizeof(memo));
int nim = 0;
int b = 0;
while(b < n) {
if(!bd[0][b] && !bd[1][b]) {
int a = b;
while(b<n && !bd[0][b] && !bd[1][b]) b++;
int lstate = 0;
if(a != 0) lstate = bd[0][a-1] + (bd[1][a-1] << 1);
int rstate = 0;
if(b != n) rstate = bd[0][b] + (bd[1][b] << 1);
nim ^= nimber(b-a, lstate, rstate);
} else {
b++;
}
}
return nim != 0 ? "Snuke" : "Sothe";
}
};
まとめ
完全状態ゲームの問題に苦手意識を持っていましたが、予想通りMediumは理解にかなりの時間を要しました。
まぁ、分かってしまえば意外と単純なんですけど…