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