Google Code Jam 2014 Qualification Round : D. Deceitful War

問題文が長くわかりにくい…。
https://code.google.com/codejam/contest/2974486/dashboard#s=p3

問題

NaomiとKenは異なる重さのN個の重りを持つ。
互いの持つ重りの重さは知っているものとする。

２人の重りを1個ずつ出していき、重い方を出した側が1点得るゲームを考える。
ここで１つ目のルールをWar、２つ目のルールをDeceitful Warとする。

Warでは、互いの全重りの重さを知っている。
また、Naomiが出す重りの重さを宣言して出したうえで、後手Kenが重りを出す。

Deceitful WarではNaomiはKenの重りの重さを知っており、一方KenはNaomiの重りの重さを知らない。
Naomiが出す重りの重さを宣言して出したうえで、後手Kenが重りを出す点は同じである。
ただしNaomiは重りの重さを偽ることができる。

NaomiはDeceitful Warをプレイするが、Kenはその事実を知らずWarだと思って(Naomiが正直だと思って)プレイする。
ただし重りの大小がNaomiの宣言と実際の値が異なる場合、KenにDeceitful Warであることがバレてしまうのでダメである。

NaomiとKenが互いに最適手を取る場合、NaomiがDeceitful Warをプレイする場合に得られるスコアとWarをプレイした場合に得られるスコアを答えよ。

解法

まずWarのスコアを考える。
KenはNaomiの手を見て自分の手を決められるので、相手の手よりちょっとだけ勝てるものを出すようにしてくる。
相手の重りの重い方の物には勝てないかもしれないが、そこは自分の弱い重りを当てれば１点失うだけで済む。

次にDeceitful Warを考える。
Kenの戦略は勝てる時は小勝ちし、負けるときは大負けである。
よって、相手をできるだけ下しに行けばよい。

Naomiの重りの上位P個がKenの重りの下位P個に互いに勝てる場合、以下のようにすればNaomiはP点取れる。

• 先に勝ち目のないNaomiの下位(N-P)個の重りを使い、Kenの重り上位(N-P)個を消費させたい。
  • そのためには、Kenの上位(N-P)個よりちょっと低い値を宣言しつつ、Naomiは下位(N-P)個を出せばよい。この際全部負けるが、Naomiの重りが実は軽いことはバレない。
• 後はNaomiが大きな重さを宣言して上位P個を出せば、Kenはあきらめて低い順に出してくるのでP点取れる。

Pを総当たりし、Naomiの上位P個とKenの下位P個を比較するので、全体でO(N^2)で処理できる。

int N;
double DF[1010],DS[1010];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	cin>>N;
	FOR(i,N) cin>>DF[i];
	FOR(i,N) cin>>DS[i];
	
	sort(DF,DF+N);
	sort(DS,DS+N);
	
	int ma=0;
	for(i=1;i<=N;i++) {
		int ok=1;
		FOR(j,i) if(DF[N-i+j]<DS[j]) ok=0;
		if(ok) ma=i;
	}
	
	int W=0;
	x=N-1;y=N-1;
	while(x>=0 && y>=0) {
		if(DF[x]>DS[y]) x--;
		else x--,y--,W++;
	}
	_P("Case #%d: %d %d\n",_loop, ma, N-W);
}

まとめ

CよりDの方がすんなり思いついて楽だった。