SRM 637 DIV1 Easy - DivisorsPower (○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13504&rd=16080
・1から2Nまで書かれた、2N枚のカードがあり、2人でゲームを行う。
・このカードが自分と相手それぞれ均等に配られる。
・2人が一枚ずつカードを出し、大きい数字の方が１ポイント得られる。
・自分のカードについては、何が配られたかわかっている。
・相手のカードについては自分のカードから推測できるが、カードを出す順番もわかっている。
ただし、-1で示されているときは何が出されるかわかっていない。
・このとき、自分が得ることのできるスコアの最大の期待値を求める。
解き方
・まず、自分のカードから相手のカードを推測し配列に保存する。
・相手のカードについて、出すものがわかっているものに対しては最適な戦略を取る。
・つまり、ある相手のわかっているカードについてそれより大きい数のカードがある場合は
そのうち最小のものを出す。
・大きい数のカードがない場合は一番小さいカードを出す。
・残りのカードについては総当たりで計算して期待値を足していけばよい。
→System Passed
・もっとシンプルな解き方があるのか他のコードをみてみたが、この方法が一番シンプルそう。
紙に書いて手順を整理すれば着実に解ける。
コード
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 GreaterGame {
public: double calc(vector<int> hand, vector<int> sothe) {
int n=hand.size();
vector<int> me(2*n+1,0),you(2*n+1,0);
FORE(i,0,n)me[hand[i]]=1;
FORE(i,0,2*n+1)you[i]=1-me[i];
int cnt=0;
FORE(i,0,n)if(sothe[i]==-1)cnt++;
double ret=0.0;
sort(all(sothe));
FORE(i,0,n)if(sothe[i]!=-1){
int win=0;
FORE(j,sothe[i]+1,2*n+1)if(me[j]){
me[j]=0;
ret++;
win=1;
break;
}
you[sothe[i]]=0;
if(!win){
FORE(j,1,2*n+1)if(me[j]==1){
me[j]=0;
break;
}
}
}
FORE(i,1,2*n+1)if(me[i]){
int tmp=0;
FORE(j,1,i)if(you[j])tmp++;
ret+=(double)tmp/cnt;
}
return ret;
}
};
#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 GreaterGame {
public: double calc(vector<int> hand, vector<int> sothe) {
int n=hand.size();
vector<int> me(2*n+1,0),you(2*n+1,0);
FORE(i,0,n)me[hand[i]]=1;
FORE(i,0,2*n+1)you[i]=1-me[i];
int cnt=0;
FORE(i,0,n)if(sothe[i]==-1)cnt++;
double ret=0.0;
sort(all(sothe));
FORE(i,0,n)if(sothe[i]!=-1){
int win=0;
FORE(j,sothe[i]+1,2*n+1)if(me[j]){
me[j]=0;
ret++;
win=1;
break;
}
you[sothe[i]]=0;
if(!win){
FORE(j,1,2*n+1)if(me[j]==1){
me[j]=0;
break;
}
}
}
FORE(i,1,2*n+1)if(me[i]){
int tmp=0;
FORE(j,1,i)if(you[j])tmp++;
ret+=(double)tmp/cnt;
}
return ret;
}
};
