2011年8月25日木曜日

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--
実に不本意な結果…．
投稿者 時刻: 0 件のコメント:
ラベル:

2011年8月10日水曜日

京都大学プログラミングコンテスト KUPC 2011

京都大学プログラミングコンテスト KUPC 2011(8/6 13:00~18:00)

久しぶりに，非定期コンテストに参加．

■A KUPC

文字ごとの出現回数をカウントして，
min(count['K'], count['U'], count['P'], count['C'])
が答え．
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-12;

	void run(){
		String s=sc.next();
		int[] count=new int[256];
		for(char c : s.toCharArray()){
			count[c]++;
		}
		int ans=min(count['K'], min(count['U'], min(count['P'], count['C'])));
		println(ans+"");
	}

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

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

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

	public static void main(String[] args){
		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
	}
}

■B 蝉

典型的なDP．
dp[y][x] := (x,y)に到達までに出会う蝉の数の最小値
右か下にしかいけないので，(x,y)の左と上を見ればdp[y][x]を決定できる．
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-12;

	int n, m;
	int[][] a;

	void run(){
		n=sc.nextInt();
		m=sc.nextInt();
		a=new int[n][m];
		for(int j=0; j<n; j++){
			String s=sc.next();
			for(int i=0; i<m; i++){
				a[j][i]=s.charAt(i)-'0';
			}
		}

		int[][] dp=new int[n][m];
		for(int j=0; j<n; j++){
			fill(dp[j], INF);
		}
		dp[0][0]=0;
		for(int j=0; j<n; j++){
			for(int i=0; i<m; i++){
				if(j>0){
					dp[j][i]=min(dp[j][i], dp[j-1][i]+a[j][i]);
				}
				if(i>0){
					dp[j][i]=min(dp[j][i], dp[j][i-1]+a[j][i]);
				}
			}
		}
		println(dp[n-1][m-1]+"");
	}

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

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

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

	public static void main(String[] args){
		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
	}
}

■C しりとり

'xa'と尋ね続ければ，その内，'a'で始まる文字列が無くなることを利用する．
途中で，不正な返答が来た時の処理等を忘れてWAを食らいまくる．
package c;

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-12;

	void run(){
		TreeSet set=new TreeSet();
		println("?a");
		System.out.flush();
		set.add("a");
		String next="";
		char ch='a';
		for(; sc.hasNext();){
			String s=sc.next();
			boolean out=false;
			out|=s.charAt(0)!='a';
			out|=set.contains(s);
			if(out){
				println("!OUT");
				break;
			}
			set.add(s);
			println("?"+s.charAt(s.length()-1)+next+ch+"a");
			if(ch++=='z'){
				next+='z';
				ch='a';
			}
			System.out.flush();
		}
	}

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

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

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

	public static void main(String[] args){
		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
	}
}

■D 列の構成

ずっとやり方を考えていたが，DFS+適当な枝刈りで通ってしまった． 想定解法は乱択アルゴリズムという珍しい問題． 
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-12;

	int n, k;
	int[][] a, sum;
	int[] count, seq;
	boolean[] brank;
	boolean end=false;

	void run(){
		n=sc.nextInt();
		k=sc.nextInt();
		a=new int[k][n];
		brank=new boolean[n];
		sum=new int[k][n+1];
		fill(brank, true);
		for(int j=0; j<k; j++){
			for(int i=0; i<n/2; i++){
				int k=sc.nextInt();
				a[j][k-1]=1;
				brank[k-1]=false;
			}
			for(int i=0; i<n; i++){
				sum[j][i+1]=sum[j][i]+a[j][i];
			}
		}
		count=new int[k];
		seq=new int[n];
		rec(0);
	}

	void rec(int x){
		if(end){
			return;
		}

		// 枝刈り
		for(int j=0; j<k; j++){
			int rem=sum[j][n]-sum[j][x];
			if(count[j]+rem<n/8){
				return;
			}
			if(count[j]>3*n/8){
				return;
			}
		}

		if(x==n){
			end=true;
			for(int i=0; i<n; i++){
				print(seq[i]+"");
			}
			println("");
			return;
		}

		if(brank[x]){
			rec(x+1);
			return;
		}

		seq[x]=0;
		rec(x+1);

		seq[x]=1;
		for(int j=0; j<k; j++){
			count[j]+=a[j][x];
		}
		rec(x+1);
		for(int j=0; j<k; j++){
			count[j]-=a[j][x];
		}

	}

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

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

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

	public static void main(String[] args){
		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
	}
}

■E Fox Number

Fox Numberでない数を列挙する． n=p1p22は条件を満たさないことを使う （p1，p2は素数）．
kn∈[A-B, A+B]となる最小のkを以下で求める．
k=max([(A-B)/n], 1)
そして，kn∈[A-B, A+B]である間，kをインクリメント．
ここで，kn=p11+rkp22+skm と表わすことが出来る．
1+rk < 2+sk
ならば，knはFox Numberでないので，
isNotFoxNumber[kn]=true
これを妥当な範囲内の素数全てについて行う． 
import java.util.*;
import java.util.Map.Entry;
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-12;

	long a;
	int b;
	int p, m;
	int[] prime;
	boolean[] isPrime;
	boolean[] fox;

	void run(){
		a=sc.nextLong();
		b=sc.nextInt();

		fox=new boolean[2*b+1];
		fill(fox, true);
		
		for(int i=0;i<2*b+1;i++){
			if(i-b+a<2){
				fox[i]=false;
			}
		}

		m=(int)sqrt(a+b)+10;
		p=0;
		prime=new int[m];
		isPrime=new boolean[m+1];
		Arrays.fill(isPrime, true);
		isPrime[0]=isPrime[1]=false;
		for(int i=2; i<=m; i++){
			if(isPrime[i]){
				prime[p++]=i;
				for(int j=2*i; j<=m; j+=i)
					isPrime[j]=false;
			}
		}

		int e1=1, e2=2;
		for(int p2=0; p2<p; p2++){
			long n2=(long)prime[p2]*prime[p2];
			if(n2>a+b){
				break;
			}
			for(int p1=0; p1<p2; p1++){
				long n1=prime[p1];
				long n=n1*n2;
				if(n<0){
					debug(n);
				}
				if(n>a+b){
					break;
				}

				int c=0;
				for(long k=max((a-b)/n, 1); k*n<=a+b; k++){
					c++;
					int pc1=0;
					for(long i=k; i%prime[p1]==0; i/=prime[p1]){
						pc1++;
					}
					int pc2=0;
					for(long i=k; i%prime[p2]==0; i/=prime[p2]){
						pc2++;
					}

					if(e1+pc1<e2+pc2){
						if(k*n>=a-b){
							fox[(int)(k*n-a+b)]=false;
						}
					}
				}
			}
		}

		int c=0;
		for(int i=0; i<2*b+1; i++){
			if(fox[i]){
				c++;
			}
		}

		println(c+"");
	}

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

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

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

	public static void main(String[] args){
		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
	}
}

■結果

ooooo----- 500pts. 17th
まぁまぁの成績．
投稿者 時刻: 1 件のコメント:
ラベル:
登録: 投稿 (Atom)