京都大学プログラミングコンテスト 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 件のコメント:
Eですが、区間ふるいという人が多くて、「あれ、それで間に合うかなぁ？」と思っていたのですが、補集合を列挙するのですか。盲点でした。
５問、すごいですね。
コメントを投稿