https://community.topcoder.com/stat?c=round_overview&er=5&rd=16080
Easy
わかんないカードをS,それと対戦するカードをTとすると、勝つ回数の期待値Eは加法定理を使って、
E=Σ(T[i]がSに勝つ確率)=Σ(T[i]>S[j]となるjの数)/|S|となります。よって１つあたりの期待値は1以下です。
わかってるカードに勝てるやつがあれば期待値は1になるのでわかんないカードと対戦するよりも期待値が高くなります。よってなるべくわかってるカードに勝てるようにすればいいです。どうしても勝てないカードには弱いカードを当てます。こういう煩雑なやつはsetを使ってやると良いですね。
struct GreaterGame { vector<int> hand; vector<int> sothe; bool used[110]; double calc(vector<int> _hand, vector<int> _sothe) { hand = _hand, sothe = _sothe; int n = sz(hand); set<int> S; rep(i, 0, n) S.insert(hand[i]); vector<int> unknown; rep(i, 0, n) { hand[i]--; used[hand[i]] = true; } rep(i, 0, n) { if(sothe[i] == -1) continue; sothe[i]--; used[sothe[i]] = true; } rep(i, 0, 2 * n) { if(!used[i]) unknown.pb(i); } sort(all(sothe)); int cnt1 = 0; rer(i, n, 0) { if(sothe[i] == -1) break; int a = sothe[i]; auto b = S.upper_bound(a); //c++0x使えます。 if(b == S.end()) continue; S.erase(b); cnt1++; } if(!sz(unknown)) return cnt1; while(sz(S) > sz(unknown)) S.erase(S.begin()); int cnt2 = 0; for(int a : S) { rep(i, 0, sz(unknown)) { if(a > unknown[i]) cnt2++; } } return cnt1 + 1.0 * cnt2 / sz(unknown); } };
41 minutes 12 secs。めちゃくちゃ遅い。考察は10分くらいで終わったけど。フロー流すのは思いつかなかったけど頭すごいいいなぁ。
Medium
.#.
oooのように、#があると3つのoがあるところに#が置けなくなるので、oと#でちょうど盤面を覆い尽くした人が勝ちというゲームになります。それであり得る状態は、
#...#
#...#と
#...#
##..#と
#..##
##..#と
#...#
##.##しかないので、grundy数をdpで求めることができますが、遷移がとてもややこしいです。
盤面が負けの状態=盤面に対しどうプレイしても負ける場合
なので注意。負けの状態にできる盤面と勘違いしないように。
あとGameはGrundyを使うのを考えるのが重要で、同じ問題がn個あればGrundy数を求められることに留意しましょう。
struct PathGame { vector<string> board; int dp[1010][4]; int loop(int l, int state) { if(l == 0 && state == 0) return 0; if(l == 0 && state == 1) return 1; if(l == 0 && state == 2) return 0; if(l == 0 && state == 3) return 1; if(l == 1 && state == 0) return 1; if(l == 1 && state == 1) return 2; if(l == 1 && state == 2) return 1; if(l == 1 && state == 3) return 0; if(dp[l][state] != -1) return dp[l][state]; set<int> S; if(state == 0) { rep(i, 0, l - 2) { int a = loop(i, 1) ^ loop(l - 3 - i, 1); S.insert(a); } S.insert(loop(l - 2, 1)); } if(state == 1) { rep(i, 0, l - 2) { int a = loop(i, 3) ^ loop(l - 3 - i, 1); int b = loop(i, 2) ^ loop(l - 3 - i, 1); S.insert(a); S.insert(b); } S.insert(loop(l - 1, 1)); S.insert(loop(l - 2, 1)); S.insert(loop(l - 2, 1) ^ 1); S.insert(loop(l - 2, 3)); S.insert(loop(l - 2, 2)); } if(state == 2) { rep(i, 0, l - 2) { int a = loop(i, 3) ^ loop(l - 3 - i, 3); int b = loop(i, 2) ^ loop(l - 3 - i, 2); S.insert(a); S.insert(b); } S.insert(loop(l - 2, 3)); S.insert(loop(l - 2, 2) ^ 1); S.insert(loop(l - 1, 2)); } if(state == 3) { rep(i, 0, l - 2) { int a = loop(i, 3) ^ loop(l - 3 - i, 2); int b = loop(i, 2) ^ loop(l - 3 - i, 3); S.insert(a); S.insert(b); } S.insert(loop(l - 2, 2)); S.insert(loop(l - 2, 3) ^ 1); S.insert(loop(l - 1, 3)); } int at = 0; while(S.count(at)) at++; return dp[l][state] = at; } string judge(vector<string> _board) { board = _board; int n = 2, m = sz(board[0]); rep(i, 0, n) { rep(j, 0, m) { if(board[i][j] == '#') { rep(k, -1, 1 + 1) { if(j + k < 0 || m <= j + k) continue; if(board[1 - i][j + k] == '.') { board[1 - i][j + k] = 'o'; } } } } } memset(dp, -1, sizeof(dp)); int ans = 0; int cnt = 0, state = -1; //-1:none,0:up,1:down,2:both rep(j, 0, m) { if(state == -1) { if(board[0][j] == '.' && board[1][j] != '.') { state = 0; cnt = 0; } else if(board[0][j] != '.' && board[1][j] == '.') { state = 1; cnt = 0; } else if(board[0][j] == '.' && board[1][j] == '.') { state = 2; cnt = 1; } } else if(state == 2) { if(board[0][j] != '.' && board[1][j] != '.') { state = -1; ans ^= loop(cnt, 0); } else if(board[0][j] == '.' && board[1][j] != '.') { state = -1; ans ^= loop(cnt, 1); } else if(board[0][j] != '.' && board[1][j] == '.') { state = -1; ans ^= loop(cnt, 1); } else if(board[0][j] == '.' && board[1][j] == '.') { cnt++; } } else if(state == 0) { if(board[0][j] != '.' && board[1][j] != '.') { state = -1; ans ^= loop(cnt, 1); } else if(board[0][j] == '.' && board[1][j] != '.') { state = -1; ans ^= loop(cnt, 2); } else if(board[0][j] != '.' && board[1][j] == '.') { state = -1; ans ^= loop(cnt, 3); } else if(board[0][j] == '.' && board[1][j] == '.') { cnt++; } } else if(state == 1) { if(board[0][j] != '.' && board[1][j] != '.') { state = -1; ans ^= loop(cnt, 1); } else if(board[0][j] == '.' && board[1][j] != '.') { state = -1; ans ^= loop(cnt, 3); } else if(board[0][j] != '.' && board[1][j] == '.') { state = -1; ans ^= loop(cnt, 2); } else if(board[0][j] == '.' && board[1][j] == '.') { cnt++; } } } if(state == 0 || state == 1) { ans ^= loop(cnt, 1); } if(state == 2) { ans ^= loop(cnt, 0); } if(ans == 0) return "Sothe"; else return "Snuke"; } };
93 minutes 56 secs 2 resubmitはキツイ
