SRM 222 DIV1 Hard KingOfTheCourt
問題
ゲームをする。プレイヤーがN人いて、常に一列に並んでいる。
kingと呼ばれるプレイヤーが各ターンに一人いる。
kingは次のプレイヤーとテニスの対戦をしていき、kingが勝ったなら、対戦相手は列の一番後ろに移動し、次のプレイヤーとまた対戦をする。全てのプレイヤーに一度のkingの間に勝ったならそこでゲームが終了し、kingの最終的な勝ち。
kingが負けたなら、kingのプレイヤーは列の一番に移動し、対戦相手のプレイヤーが新しいkingとなりその位置(列の一番前)に留まり、次のターンへ進む。
テニスの1回のセットで勝つ確率は、プレイヤーごとに決められた強さabilityに対し、iがjに勝つ確率は(ability[i] / (ability[i] + ability[j]))とする。
テニスの1回の対戦では、kingは1回, kingではないプレイヤーは2回 のセットの先取で勝ちが決まる。
ゲームの最初、プレイヤー0がkingである。
プレイヤー0がゲームに最終的に勝つ確率を求めよ
解答
EditorialとPractice Roomのrng_58さんの解答を参考にした。
状態として「列の順列」を持つ。このとき、列の先頭がkingで、まだ誰にも勝っていない状態を考える。
そして更新では「(i-1)回勝ってそのあと負ける」という確率を求めて足す。
あとはDPを収束するまで回すやつをやる
コメント
最初問題よくよめてなかった。しかしこれはなんとく分かりそうな気はする。
コード
#include <vector> #include <algorithm> #include <map> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) using namespace std; typedef vector<int> vi; struct KingOfTheCourt { double chancesOfWinning(vector <int> a) { int n = a.size(); vi v; rep(i, n) v.pb(i); map<vi,int> permto; int m = 0; do { permto[v] = m ++; } while(next_permutation(all(v))); static double win[5040], prob[5040][7]; static int to[5040][7]; sort(all(v)); do { int s = permto[v]; double p = 1; reu(i, 1, n) { vi w; reu(j, i, n) w.pb(v[j]); reu(j, 1, i) w.pb(v[j]); w.pb(v[0]); //負けた後の状態だから、最後にkingが来る double q = a[v[0]] * 1. / (a[v[0]] + a[v[i]]); to[s][i] = permto[w]; prob[s][i] = p * ((1 - q) * (1 - q)); p *= 1 - (1 - q) * (1 - q); } if(v[0] == 0) win[s] = p; else win[s] = 0; }while(next_permutation(all(v))); static double dp[2][5040]; fill(dp[1], dp[1]+m, 0.); rep(ii, 5000) rep(i, m) { dp[ii&1][i] = win[i]; reu(j, 1, n) dp[ii&1][i] += prob[i][j] * dp[~ii&1][to[i][j]]; } return dp[0][0]; } };
Twitterで書いた、作った問題の解答
https://twitter.com/anta_prg/status/281025745768288256
問題
今位置0に居て、ある位置[K,K+M-1](K,M≦10^10)の範囲に止まる必要がある。
カードがN(≦40)枚、それぞれに数値とコスト(≦10^9)が書かれていて{捨てる・数値だけ進む}ことができる。
コストを最小化せよ。止まれない場合は-1を返せ
解答(想定解, 合っているかは不明)
半分全列挙する。
半分全列挙した片方(移動距離, コスト)をRangeMinimumQueryに入れる。
もう半分の列挙に対して、[K - 移動距離, K - 移動距離 + M)の範囲(をlower_bound,upper_boundでインデックスにする)でRMQをクエリし、その区間最小+コストをminする
コメント
初めて問題を作ってみた。
半分の指数の問題をhttp://d.hatena.ne.jp/anta1/20121218/1355826246でやって、それでそういう問題を作ってみたいなと思って作ってみた。RMQ使えるじゃん、と思ってやってみた。
もっと簡単な解法もあるかもしれないね。
実際解答が合っているかは不明だが良い感じだと思う。
なんとなく組み合わせが簡単なので、恐らく過去に同じような問題が出されているかもしれない。
これからも理解のために、やった問題からアイデアを得て問題をどんどん作って行きたい。このブログの直前を見れば答えわかっちゃう、ということになるかもしれないけれど。
問題作るのは楽しいしね。でもテストケースとか作ってないし大変なことはしてないわけだからなーとか
コード
#include <vector> #include <algorithm> #include <cstring> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL using namespace std; typedef vector<int> vi; typedef long long ll; typedef pair<long long,long long> pll; struct RMQ { int n; ll d[2097152]; void init(int nmin) { for(n = 1; n < nmin; n *= 2); memset(d, INF, 2 * n); } void update(int i, ll x) { d[n+i] = x; for(int k = (n+i)/2; k > 0; k >>= 1) d[k] = min(d[k * 2], d[k * 2 + 1]); } ll get(int l, int r) const { ll m = INFL; for(; l && l + (l&-l) <= r; l += l&-l) m = min(m, d[(n+l) / (l&-l)]); for(; l < r; r -= r&-r) m = min(m, d[(n+r) / (r&-r) - 1]); return m; } }; RMQ rmq; ll minCost(vi xs, vi costs, ll K, ll M) { int n = xs.size(); int m = n/2; vector<pll> v; rep(i, 1<<m) { ll cost = 0, advance = 0; rep(j, m) if((i >> j) & 1) advance += xs[j], cost += costs[j]; v.pb(mp(advance, cost)); } sort(all(v)); rmq.init(v.size()); rep(i, v.size()) rmq.update(i, v[i].second); int m2 = n - m; ll r = INFL; rep(i, 1<<m2) { ll cost = 0, advance = 0; rep(j, m2) if((i >> j) & 1) advance += xs[m+j], cost += costs[m+j]; int l = lower_bound(all(v), mp(K - advance, -INFL)) - v.begin(); int u = upper_bound(all(v), mp(K + M - advance, -INFL)) - v.begin(); cost += rmq.get(l, u); r = min(r, cost); } return r == INFL ? -1 : r; }
SRM 223 DIV1 Hard RevolvingDoors
問題
マップでスタート地点からゴール地点まで行きたい。
マップには空白・壁、回転ドアがあり、回転ドアは
1 2 | -O- → 5O6 3 4 |
の図のように、1,3の位置から5の位置まで、2,4の位置から6の位置まで行く事によって回転できる。
縦になったドアも同じように回転でき、同じドアを複数回回転させることもできる。
回転ドアは斜めの部分に壁があっても回転できる。
スタート地点からゴール地点まで行くとき、最小の、「回転ドアを回転させる回数」を求めよ
解答
(回転ドアの状態ビットマスク * 位置)を状態に持ったBFS。
どのマスがどの回転ドアに含まれるかはあらかじめメモしておいたほうがいい。
BFSの実装では、"距離"の増分が0か1なので、dequeを使うやつでやった
コメント
BFSも簡単なものなら十分慣れたなー
コード
#include <string> #include <vector> #include <algorithm> #include <queue> #include <cstring> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f using namespace std; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; struct RevolvingDoors { int turns(vector <string> a) { int h = a.size(), w = a[0].size(); pii st, ed; rep(i, h) rep(j, w) if(a[i][j] == 'S') st = mp(i, j), a[i][j] = ' '; rep(i, h) rep(j, w) if(a[i][j] == 'E') ed = mp(i, j), a[i][j] = ' '; vpii d; rep(i, h) rep(j, w) if(a[i][j] == 'O') d.pb(mp(i, j)); int n = d.size(); static int b[50][50][1<<10]; rep(i, h) rep(j, w) { bool f = true; rep(k, n) { if(abs(i-d[k].first) == 1 && j == d[k].second) { rep(mask, 1<<n) b[i][j][mask] = ((mask >> k) & 1) == 1 ? 2+k : 0; f = false; break; }else if(i == d[k].first && abs(j-d[k].second) == 1) { rep(mask, 1<<n) b[i][j][mask] = ((mask >> k) & 1) == 0 ? 2+k : 0; f = false; break; } } if(f) rep(mask, 1<<n) b[i][j][mask] = a[i][j] == ' ' ? 0 : 1; } int firstmask = 0; rep(k, n) if(a[d[k].first-1][d[k].second] == '|') firstmask |= 1 << k; static int memo[1<<10][50][50]; mset(memo, INF); deque<pair<int,pair<int,pii> > > q; q.push_back(mp(0, mp(firstmask, st))); while(!q.empty()) { int t = q.back().first; pair<int,pii> s = q.back().second; q.pop_back(); int mask = s.first, y = s.second.first, x = s.second.second; if(memo[mask][y][x] <= t) continue; memo[mask][y][x] = t; if(s.second == ed) return t; static const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0}; rep(dir, 4) { int yy = y + dy[dir], xx = x + dx[dir]; if(yy < 0 || yy >= h || xx < 0 || xx >= w) continue; if(b[yy][xx][mask] >= 2 && ((mask>>(b[yy][xx][mask]-2))&1) == (dy[dir]==0)) { q.push_front(mp(t+1, mp(mask ^ (1 << (b[yy][xx][mask]-2)), mp(yy, xx)))); }else if(b[yy][xx][mask] == 0) { q.push_back(mp(t, mp(mask, mp(yy, xx)))); } } } return -1; } };
SRM 224 DIV1 Hard ArithSeq
問題
A004201は、任意の(等差, 長さ)の等差数列を含む(飛び飛びでも含んでいるとする)。
与えられた(等差delta, 長さn)に対して、最初に現れるその等差数列の初項を求めよ
- 2 <= n <= 30
- 1 <= delta <= 100000000
解答
EditorialとPractice Roomのrng_58さんの解答を参考にした。あまりよくわかっていない。
まず、ある数xがこの数列に現れるかどうかは(let k = ceil(sqrt(x)) in x > k*(k-1))で決定できる。
初項のkを全探索してそのつど、あり得る範囲を(n-1)回考えて、deltaを足しながら狭めていく
コメント
なんとなくわかった気がしないでもない。
範囲を狭めていくやつはなかなか慣れない。この、範囲自体に定数を足しながら狭めてくのはなるほどなー
そしてまずceil(sqrt(x))の式を出さないといけないわけだが、まずきちんとこれをやるようにしよう
コード
#include <algorithm> #include <cmath> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) using namespace std; typedef long long ll; struct ArithSeq { ll sqrtceil(ll x) { //long longの範囲ではdoubleでも誤差が怖いので、まずざくっと求めてから周囲を探索する ll y = (ll)sqrt((double)x) - 2; while(y*y < x) y ++; return y; } long long minStart(ll n, ll delta) { for(ll i = 0; ; i ++) { ll l = i * (i+1) + 1, u = (i+1) * (i+1); if(l + (n-1)*delta <= u) return l; rep(j, n-1) { l += delta, u += delta; ll x = sqrtceil(l) - 1; l = max(l, x * (x+1) + 1); u = min(u, (x+1) * (x+1)); if(l > u) break; } if(l <= u) return l - (n-1)*delta; } } };
