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個）

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.     Scanner sc=new Scanner(System.in);  
11.   
12.     int INF=1<<28;  
13.     double EPS=1e-9;  
14.   
15.     int t, n, a, b;  
16.   
17.     void run(){  
18.         t=sc.nextInt();  
19.         for(int i=0; i<t; i++){  
20.             n=sc.nextInt();  
21.             a=sc.nextInt();  
22.             b=sc.nextInt();  
23.             solve();  
24.         }  
25.     }  
26.   
27.     void solve(){  
28.         int ans=0;  
29.         int bitA=Integer.bitCount(a);  
30.         int bitB=Integer.bitCount(b);  
31.         if(bitA+bitB<=n){  
32.             for(int i=0; i<n; i++){  
33.                 ans<<=1;  
34.                 if(i<bitA+bitB){  
35.                     ans++;  
36.                 }  
37.             }  
38.         }else{  
39.             for(int i=0; i<n; i++){  
40.                 ans<<=1;  
41.                 if(i<2*n-(bitA+bitB)){  
42.                     ans++;  
43.                 }  
44.             }  
45.         }  
46.         println(ans+"");  
47.     }  
48.   
49.     void println(String s){  
50.         System.out.println(s);  
51.     }  
52.   
53.     void print(String s){  
54.         System.out.print(s);  
55.     }  
56.   
57.     void debug(Object... os){  
58.         System.err.println(Arrays.deepToString(os));  
59.     }  
60.   
61.     public static void main(String[] args){  
62.         new Main().run();  
63.     }  
64. }  

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する．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.     Scanner sc=new Scanner(System.in);  
11.   
12.     int INF=1<<28;  
13.     double EPS=1e-9;  
14.   
15.     int n;  
16.     int[] vote, ps;  
17.   
18.     void run(){  
19.         for(;;){  
20.             n=sc.nextInt();  
21.             if(n==0){  
22.                 break;  
23.             }  
24.             vote=new int[n];  
25.             ps=new int[n];  
26.             for(int i=0; i<n; i++){  
27.                 vote[i]=sc.next().equals("P")?+1:-1;  
28.                 ps[i]=sc.nextInt()-vote[i];  
29.             }  
30.             solve();  
31.         }  
32.     }  
33.   
34.     void solve(){  
35.         int min=0;  
36.         for(int i=0; i<n; i++){  
37.             if(abs(ps[i]+min)%2==1){  
38.                 min++;  
39.             }  
40.             min=max(min, abs(ps[i]));  
41.         }  
42.         println(min+"");  
43.     }  
44.   
45.     void println(String s){  
46.         System.out.println(s);  
47.     }  
48.   
49.     void print(String s){  
50.         System.out.print(s);  
51.     }  
52.   
53.     void debug(Object... os){  
54.         System.err.println(Arrays.deepToString(os));  
55.     }  
56.   
57.     public static void main(String[] args){  
58.         new Main().run();  
59.     }  
60. }  

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--
実に不本意な結果…．