SRM 548 DIV1 Middle - KingdomAndDice （復習○）
問題
サイコロが２つあり、２人のプレイヤーがそれぞれ１つのサイコロを振って出た目が大きい方が勝つゲームを行う。
ゲームはできるだけ公平にしたいので、勝つ確率は５０％になるのが望ましい。
ここで、サイコロ２つに対して各面の目がいくつか与えられる。
ただしそのうち一つのサイコロはいくつかの面がとれてしまい、代わりに０としている。
この目をすでに使っていない数字かつ最大の数字Ｘ以下の数字を埋めることで、
各確率を５０％に可能な限り近づけた際の確率を求める。
ただし数字は必ずしも埋めずに０を使ってもよい。
解き方
出る目の数字は１０＾９であるので単純に考えると計算量は間に合わない。
ここで問題文に着目してみると、求めるのは勝つ確率だけであるので、相手の目に対して埋める目の勝つ数は５０個以下であることがわかる。
つまり勝つ回数０～５０まで考えればよいことがわかる。
次に、それぞれの勝つ回数について、何個まで使うことができるかを求める。
今回はvector型のint変数を用意し、勝つ回数を配列に用意する。それぞれの勝つ回数は最大で埋めることのできる数、つまり最初のサイコロの０の数なのですべて用意してもオーバーフローしない。
求めたvector配列を用いて、勝つことのできる回数を全て求める。
単純に考えると組み合わせ５０Ｃ２５で間に合わないが、ｄｐを用いて
状態を勝つ回数、値を利用する目の数とすることで求めることができる。
ｄｐを回す際には、配列がオーバーフローしないように判定することに注意。
最後に求めたｄｐの中からできるだけ答えが０．５に近くなるものを求める。
この時にｎ＊ｎで割ると誤差が出てしまうので式を変形して、
勝つ回数をxとすると
x/(n*n)=0.5
x=0.5*n*n
2x=n*n
2x-n*n=0
つまり2x-n*nの絶対値が一番０に近いものが最終的な答えになる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class KingdomAndDice {
public: double newFairness(vector<int> firstDie, vector<int> secondDie, int X) {
int n=firstDie.size();
int cnt=0;
map<int,int> m;
FORE(i,0,n){
m[firstDie[i]]++;
if(firstDie[i]==0)cnt++;
}
vector<int> num;
secondDie.push_back(X+1);
sort(all(secondDie));
FORE(i,0,n){
int tmp=0;
for(int j=secondDie[i]+1;tmp<=cnt&&j<secondDie[i+1];j++){
if(m.find(j)==m.end()){
num.push_back(i+1);
tmp++;
}
}
}
int dp[n*n+1];
FORE(i,0,n*n+1)dp[i]=1e+9;
dp[0]=0;
for(int i=0;i<num.size();i++){
for(int j=n*n+1;j>=0;j--){
if(j-num[i]>=0)dp[j]=min(dp[j],dp[j-num[i]]+1);
}
}
double init=0;
FORE(i,0,n){
if(firstDie[i]!=0)FORE(j,0,secondDie.size())if(firstDie[i]>secondDie[j])init++;
}
double ret=0;
FORE(i,0,n*n+1){
if(dp[i]>cnt)continue;
if( fabs(2*(init+ret)-n*n) > fabs(2*(init+i)-n*n) )ret=i;
}
return (init+ret)/(n*n);
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class KingdomAndDice {
public: double newFairness(vector<int> firstDie, vector<int> secondDie, int X) {
int n=firstDie.size();
int cnt=0;
map<int,int> m;
FORE(i,0,n){
m[firstDie[i]]++;
if(firstDie[i]==0)cnt++;
}
vector<int> num;
secondDie.push_back(X+1);
sort(all(secondDie));
FORE(i,0,n){
int tmp=0;
for(int j=secondDie[i]+1;tmp<=cnt&&j<secondDie[i+1];j++){
if(m.find(j)==m.end()){
num.push_back(i+1);
tmp++;
}
}
}
int dp[n*n+1];
FORE(i,0,n*n+1)dp[i]=1e+9;
dp[0]=0;
for(int i=0;i<num.size();i++){
for(int j=n*n+1;j>=0;j--){
if(j-num[i]>=0)dp[j]=min(dp[j],dp[j-num[i]]+1);
}
}
double init=0;
FORE(i,0,n){
if(firstDie[i]!=0)FORE(j,0,secondDie.size())if(firstDie[i]>secondDie[j])init++;
}
double ret=0;
FORE(i,0,n*n+1){
if(dp[i]>cnt)continue;
if( fabs(2*(init+ret)-n*n) > fabs(2*(init+i)-n*n) )ret=i;
}
return (init+ret)/(n*n);
}
};
