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

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

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

■A KUPC

文字ごとの出現回数をカウントして，
min(count['K'], count['U'], count['P'], count['C'])
が答え．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5. import static java.lang.Math.*;  
6. import static java.util.Arrays.*;  
7.   
8. public class Main{  
9.     Scanner sc=new Scanner(System.in);  
10.     int INF=1<<28;  
11.     double EPS=1e-12;  
12.   
13.     void run(){  
14.         String s=sc.next();  
15.         int[] count=new int[256];  
16.         for(char c : s.toCharArray()){  
17.             count[c]++;  
18.         }  
19.         int ans=min(count['K'], min(count['U'], min(count['P'], count['C'])));  
20.         println(ans+"");  
21.     }  
22.   
23.     void debug(Object... os){  
24.         System.err.println(Arrays.deepToString(os));  
25.     }  
26.   
27.     void print(String s){  
28.         System.out.print(s);  
29.     }  
30.   
31.     void println(String s){  
32.         System.out.println(s);  
33.     }  
34.   
35.     public static void main(String[] args){  
36.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
37.         new Main().run();  
38.     }  
39. }  

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]を決定できる．

view plainprint?

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

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を食らいまくる．

view plainprint?

1. package c;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7. import static java.lang.Math.*;  
8. import static java.util.Arrays.*;  
9.   
10. public class Main{  
11.     Scanner sc=new Scanner(System.in);  
12.     int INF=1<<28;  
13.     double EPS=1e-12;  
14.   
15.     void run(){  
16.         TreeSet<string> set=new TreeSet<string>();  
17.         println("?a");  
18.         System.out.flush();  
19.         set.add("a");  
20.         String next="";  
21.         char ch='a';  
22.         for(; sc.hasNext();){  
23.             String s=sc.next();  
24.             boolean out=false;  
25.             out|=s.charAt(0)!='a';  
26.             out|=set.contains(s);  
27.             if(out){  
28.                 println("!OUT");  
29.                 break;  
30.             }  
31.             set.add(s);  
32.             println("?"+s.charAt(s.length()-1)+next+ch+"a");  
33.             if(ch++=='z'){  
34.                 next+='z';  
35.                 ch='a';  
36.             }  
37.             System.out.flush();  
38.         }  
39.     }  
40.   
41.     void debug(Object... os){  
42.         System.err.println(Arrays.deepToString(os));  
43.     }  
44.   
45.     void print(String s){  
46.         System.out.print(s);  
47.     }  
48.   
49.     void println(String s){  
50.         System.out.println(s);  
51.     }  
52.   
53.     public static void main(String[] args){  
54.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
55.         new Main().run();  
56.     }  
57. }</string></string>  

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+適当な枝刈りで通ってしまった． 想定解法は乱択アルゴリズムという珍しい問題．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5. import static java.lang.Math.*;  
6. import static java.util.Arrays.*;  
7.   
8. public class Main{  
9.     Scanner sc=new Scanner(System.in);  
10.     int INF=1<<28;  
11.     double EPS=1e-12;  
12.   
13.     int n, k;  
14.     int[][] a, sum;  
15.     int[] count, seq;  
16.     boolean[] brank;  
17.     boolean end=false;  
18.   
19.     void run(){  
20.         n=sc.nextInt();  
21.         k=sc.nextInt();  
22.         a=new int[k][n];  
23.         brank=new boolean[n];  
24.         sum=new int[k][n+1];  
25.         fill(brank, true);  
26.         for(int j=0; j<k; j++){  
27.             for(int i=0; i<n/2; i++){  
28.                 int k=sc.nextInt();  
29.                 a[j][k-1]=1;  
30.                 brank[k-1]=false;  
31.             }  
32.             for(int i=0; i<n; i++){  
33.                 sum[j][i+1]=sum[j][i]+a[j][i];  
34.             }  
35.         }  
36.         count=new int[k];  
37.         seq=new int[n];  
38.         rec(0);  
39.     }  
40.   
41.     void rec(int x){  
42.         if(end){  
43.             return;  
44.         }  
45.   
46.         // 枝刈り  
47.         for(int j=0; j<k; j++){  
48.             int rem=sum[j][n]-sum[j][x];  
49.             if(count[j]+rem<n/8){  
50.                 return;  
51.             }  
52.             if(count[j]>3*n/8){  
53.                 return;  
54.             }  
55.         }  
56.   
57.         if(x==n){  
58.             end=true;  
59.             for(int i=0; i<n; i++){  
60.                 print(seq[i]+"");  
61.             }  
62.             println("");  
63.             return;  
64.         }  
65.   
66.         if(brank[x]){  
67.             rec(x+1);  
68.             return;  
69.         }  
70.   
71.         seq[x]=0;  
72.         rec(x+1);  
73.   
74.         seq[x]=1;  
75.         for(int j=0; j<k; j++){  
76.             count[j]+=a[j][x];  
77.         }  
78.         rec(x+1);  
79.         for(int j=0; j<k; j++){  
80.             count[j]-=a[j][x];  
81.         }  
82.   
83.     }  
84.   
85.     void debug(Object... os){  
86.         System.err.println(Arrays.deepToString(os));  
87.     }  
88.   
89.     void print(String s){  
90.         System.out.print(s);  
91.     }  
92.   
93.     void println(String s){  
94.         System.out.println(s);  
95.     }  
96.   
97.     public static void main(String[] args){  
98.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
99.         new Main().run();  
100.     }  
101. }  

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=p₁p₂²は条件を満たさないことを使う （p₁，p₂は素数）．
kn∈[A-B, A+B]となる最小のkを以下で求める．
k=max([(A-B)/n], 1)
そして，kn∈[A-B, A+B]である間，kをインクリメント．
ここで，kn=p₁^1+r_kp₂^2+s_km と表わすことが出来る．
1+r_k < 2+s_k
ならば，knはFox Numberでないので，
isNotFoxNumber[kn]=true
これを妥当な範囲内の素数全てについて行う．

view plainprint?

1. import java.util.*;  
2. import java.util.Map.Entry;  
3. import java.lang.*;  
4. import java.math.*;  
5. import java.io.*;  
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.     int INF=1<<28;  
12.     double EPS=1e-12;  
13.   
14.     long a;  
15.     int b;  
16.     int p, m;  
17.     int[] prime;  
18.     boolean[] isPrime;  
19.     boolean[] fox;  
20.   
21.     void run(){  
22.         a=sc.nextLong();  
23.         b=sc.nextInt();  
24.   
25.         fox=new boolean[2*b+1];  
26.         fill(fox, true);  
27.           
28.         for(int i=0;i<2*b+1;i++){  
29.             if(i-b+a<2){  
30.                 fox[i]=false;  
31.             }  
32.         }  
33.   
34.         m=(int)sqrt(a+b)+10;  
35.         p=0;  
36.         prime=new int[m];  
37.         isPrime=new boolean[m+1];  
38.         Arrays.fill(isPrime, true);  
39.         isPrime[0]=isPrime[1]=false;  
40.         for(int i=2; i<=m; i++){  
41.             if(isPrime[i]){  
42.                 prime[p++]=i;  
43.                 for(int j=2*i; j<=m; j+=i)  
44.                     isPrime[j]=false;  
45.             }  
46.         }  
47.   
48.         int e1=1, e2=2;  
49.         for(int p2=0; p2<p; p2++){  
50.             long n2=(long)prime[p2]*prime[p2];  
51.             if(n2>a+b){  
52.                 break;  
53.             }  
54.             for(int p1=0; p1<p2; p1++){  
55.                 long n1=prime[p1];  
56.                 long n=n1*n2;  
57.                 if(n<0){  
58.                     debug(n);  
59.                 }  
60.                 if(n>a+b){  
61.                     break;  
62.                 }  
63.   
64.                 int c=0;  
65.                 for(long k=max((a-b)/n, 1); k*n<=a+b; k++){  
66.                     c++;  
67.                     int pc1=0;  
68.                     for(long i=k; i%prime[p1]==0; i/=prime[p1]){  
69.                         pc1++;  
70.                     }  
71.                     int pc2=0;  
72.                     for(long i=k; i%prime[p2]==0; i/=prime[p2]){  
73.                         pc2++;  
74.                     }  
75.   
76.                     if(e1+pc1<e2+pc2){  
77.                         if(k*n>=a-b){  
78.                             fox[(int)(k*n-a+b)]=false;  
79.                         }  
80.                     }  
81.                 }  
82.             }  
83.         }  
84.   
85.         int c=0;  
86.         for(int i=0; i<2*b+1; i++){  
87.             if(fox[i]){  
88.                 c++;  
89.             }  
90.         }  
91.   
92.         println(c+"");  
93.     }  
94.   
95.     void debug(Object... os){  
96.         System.err.println(Arrays.deepToString(os));  
97.     }  
98.   
99.     void print(String s){  
100.         System.out.print(s);  
101.     }  
102.   
103.     void println(String s){  
104.         System.out.println(s);  
105.     }  
106.   
107.     public static void main(String[] args){  
108.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
109.         new Main().run();  
110.     }  
111. }  

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
まぁまぁの成績．