CodeChef August Cook-off 2011

CodeChef August Cook-off 2011（8/22 1:00~3:30）

■Open the Dragon Scroll

問題

A，B，Nが与えられる．
（2進数で）A，BのビットをNビットに収まる範囲で自由に並び替える．
A xor B = Cの最大値を求めよ．

解法

A，Bにおける1のビットの数を|A|，|B|とする．

1.|A|+|B|≦N

この時は，以下のようにビットを並び替えれば最大値になる．
A→11…1100…0000…00
B→00…0011…1100…00
C→11…1111…1100…00
（1が|A|+|B|個，0がN-(|A|+|B|)個）

2.|A|+|B|>N

xorをとると，どうしてもどこかでAの1とBの1が相殺して0になってしまう．
そのため，ビットを下のように並びかえる．
A→11…1100…0011…11
B→00…0011…1111‥11
この時，1 xor 1 = 0で相殺されてしまう1（右端の1のこと）の個数をXとすれば，
|A|+|B|-X=N
∴X=|A|+|B|-N
C→11…1111…1100…00
（1が2|N|-(|A|+|B|)個，0が|A|+|B|-N個）

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{
	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-9;

	int t, n, a, b;

	void run(){
		t=sc.nextInt();
		for(int i=0; i<t; i++){
			n=sc.nextInt();
			a=sc.nextInt();
			b=sc.nextInt();
			solve();
		}
	}

	void solve(){
		int ans=0;
		int bitA=Integer.bitCount(a);
		int bitB=Integer.bitCount(b);
		if(bitA+bitB<=n){
			for(int i=0; i<n; i++){
				ans<<=1;
				if(i<bitA+bitB){
					ans++;
				}
			}
		}else{
			for(int i=0; i<n; i++){
				ans<<=1;
				if(i<2*n-(bitA+bitB)){
					ans++;
				}
			}
		}
		println(ans+"");
	}

	void println(String s){
		System.out.println(s);
	}

	void print(String s){
		System.out.print(s);
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	public static void main(String[] args){
		new Main().run();
	}
}

■Vote for the Noodle Soup

問題

ある投票システムがある．
投票する際のスコアは+1/-1で，一度投票したら無効には出来ない．
スコアを見るためには，上記のスコアで投票する必要がある．
Poは，（+1/-1に）複数回投票し，スコアを記録した．
得られたスコアから，（Poを除いた）総投票者の最小数を求めよ．

解法

得られたスコアをscore[i]と表す．
Poが入れたポイント（vote[i]とする）は計算の邪魔なので，score[i]から予め引いておく．
score[0]～score[n-1]まで逐一見ていく．
i番目まで見たときの投票者数の最小値をnUsers[i]とする．
明らかなのは，
nUsers[0]=0
nUsers[i+1]=max(nUsers[i], |score[i+1]|)
ということ．投票者数は，最低でもスコアの絶対値だけ必要．
次に，nUsers[i]+score[i+1]が奇数だった場合は，
nUsers[i+1]=nUsers[i]+1
とする必要がある．何故なら，
nUsers[i]が偶数/奇数⇔score[i]が偶数/奇数
だから．そして，投票者数は減らないから，+1する．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{
	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-9;

	int n;
	int[] vote, ps;

	void run(){
		for(;;){
			n=sc.nextInt();
			if(n==0){
				break;
			}
			vote=new int[n];
			ps=new int[n];
			for(int i=0; i<n; i++){
				vote[i]=sc.next().equals("P")?+1:-1;
				ps[i]=sc.nextInt()-vote[i];
			}
			solve();
		}
	}

	void solve(){
		int min=0;
		for(int i=0; i<n; i++){
			if(abs(ps[i]+min)%2==1){
				min++;
			}
			min=max(min, abs(ps[i]));
		}
		println(min+"");
	}

	void println(String s){
		System.out.println(s);
	}

	void print(String s){
		System.out.print(s);
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	public static void main(String[] args){
		new Main().run();
	}
}

■Result

o-o--
実に不本意な結果…．