Codeforces Beta Round #17

Codeforces Beta Round #17(6/11 0:00~2:00)

時間的な都合でしばらくはTopCoderに参加できないので，Codeforcesに参加してきました．
Codeforcesは，SRM(TopCoder)のようなプログラミングコンテストの一つで，形式はICPCに近い感じです．SRMと違うと感じた点は，

・SRMが3問75分であるのに対し，Codeforcesは基本的に5問120分．
・SRMのように参加者をルーム毎に分けない．
・データの受け渡しには標準入出力を使う
・コードを提出したら，即座にシステムテストが行われる．また，テストに落ちても再提出できる．
・↑のため，Challenge PhaseやSystem Testが無い．

といった所です．

A Noldbach problem
正整数kとnが与えられる．2からnまでの素数で，
1+(i番目の素数)+(i+1番目の素数)
という形で表現出来るものがk個以上ある場合は"Yes"，そうでない時は"No"と出力せよ．

値の範囲が，2≦n≦1000，0≦k≦1000と狭かったため，簡単な実装ゲーでした．

view plainprint?

1. import java.util.*;  
2.   
3. public class A{  
4.   
5.  void exe(){  
6.   LinkedList<Integer> list=new LinkedList<Integer>();  
7.   for(int i=2; i<=1000; i++)  
8.    if(isPrime(i))  
9.     list.add(i);  
10.   Object[] primes=list.toArray();  
11.   
12.   Scanner sc=new Scanner(System.in);  
13.   int n=sc.nextInt();  
14.   int k=sc.nextInt();  
15.   int cnt=0;  
16.   for(int c=2; c<=n; c++){  
17.    if(!isPrime(c))  
18.     continue;  
19.    for(int i=0; i<primes.length-1; i++){  
20.     int p1=(Integer)primes[i];  
21.     int p2=(Integer)primes[i+1];  
22.     if(c==1+p1+p2){  
23.      cnt++;  
24.     }  
25.    }  
26.   }  
27.   if(cnt>=k)  
28.    System.out.println("YES");  
29.   else  
30.    System.out.println("NO");  
31.  }  
32.   
33.  boolean isPrime(int n){  
34.   if(n<=1)  
35.    return false;  
36.   if(n==2)  
37.    return true;  
38.   if(n%2==0)  
39.    return false;  
40.   int m=(int)Math.sqrt(n)+1;  
41.   for(int i=3; i<=m; i+=2)  
42.    if(n%i==0)  
43.     return false;  
44.   return true;  
45.  }  
46.   
47.  public static void main(String[] args){  
48.   Locale.setDefault(Locale.US);  
49.   new A().exe();  
50.  }  
51. }  

import java.util.*;

public class A{

 void exe(){
  LinkedList<Integer> list=new LinkedList<Integer>();
  for(int i=2; i<=1000; i++)
   if(isPrime(i))
    list.add(i);
  Object[] primes=list.toArray();

  Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int k=sc.nextInt();
  int cnt=0;
  for(int c=2; c<=n; c++){
   if(!isPrime(c))
    continue;
   for(int i=0; i<primes.length-1; i++){
    int p1=(Integer)primes[i];
    int p2=(Integer)primes[i+1];
    if(c==1+p1+p2){
     cnt++;
    }
   }
  }
  if(cnt>=k)
   System.out.println("YES");
  else
   System.out.println("NO");
 }

 boolean isPrime(int n){
  if(n<=1)
   return false;
  if(n==2)
   return true;
  if(n%2==0)
   return false;
  int m=(int)Math.sqrt(n)+1;
  for(int i=3; i<=m; i+=2)
   if(n%i==0)
    return false;
  return true;
 }

 public static void main(String[] args){
  Locale.setDefault(Locale.US);
  new A().exe();
 }
}

B Hierarchy
Nickの会社では，n人の従業員を雇用している．
Nickは，従業員の階層構造を作るため，1人を除いたn-1人の従業員に対し，それぞれ1人の監督者を設けることにした．
従業員a_iが，従業員b_iの監督者となる時の費用をc_iとした時，
a_i b_i c_i
の組がm個与えられる．
階層構造を作ったとき，最小のコストを計算せよ．

実際に木構造を作って階層構造を再現する必要があるかなと思いましたが，そんな必要ありませんでした．

view plainprint?

1. import java.util.*;  
2.   
3. public class B{  
4.  int n, m;  
5.  int[] q, a, b, c;  
6.   
7.  void exe(){  
8.   Scanner sc=new Scanner(System.in);  
9.   n=sc.nextInt();  
10.   q=new int[n];  
11.   for(int i=0; i<n; i++)  
12.    q[i]=sc.nextInt();  
13.   m=sc.nextInt();  
14.   a=new int[m];  
15.   b=new int[m];  
16.   c=new int[m];  
17.   for(int i=0; i<m; i++){  
18.    a[i]=sc.nextInt();  
19.    b[i]=sc.nextInt();  
20.    c[i]=sc.nextInt();  
21.   }  
22.   int max=0;  
23.   for(int i=0; i<n; i++){  
24.    if(q[i]>q[max])  
25.     max=i;  
26.   }  
27.   int cost=0;  
28.   for(int i=0; i<n; i++){  
29.    if(i==max)  
30.     continue;  
31.    int minj=-1;  
32.    for(int j=0; j<m; j++){  
33.     if(b[j]-1==i){  
34.      if(minj==-1||c[j]<c[minj]){  
35.       minj=j;  
36.      }  
37.     }  
38.    }  
39.    if(minj==-1){  
40.     System.out.println("-1");  
41.     return;  
42.    }  
43.    cost+=c[minj];  
44.   }  
45.   System.out.println(""+cost);  
46.  }  
47.   
48.  public static void main(String[] args){  
49.   Locale.setDefault(Locale.US);  
50.   new B().exe();  
51.  }  
52. }  

import java.util.*;

public class B{
 int n, m;
 int[] q, a, b, c;

 void exe(){
  Scanner sc=new Scanner(System.in);
  n=sc.nextInt();
  q=new int[n];
  for(int i=0; i<n; i++)
   q[i]=sc.nextInt();
  m=sc.nextInt();
  a=new int[m];
  b=new int[m];
  c=new int[m];
  for(int i=0; i<m; i++){
   a[i]=sc.nextInt();
   b[i]=sc.nextInt();
   c[i]=sc.nextInt();
  }
  int max=0;
  for(int i=0; i<n; i++){
   if(q[i]>q[max])
    max=i;
  }
  int cost=0;
  for(int i=0; i<n; i++){
   if(i==max)
    continue;
   int minj=-1;
   for(int j=0; j<m; j++){
    if(b[j]-1==i){
     if(minj==-1||c[j]<c[minj]){
      minj=j;
     }
    }
   }
   if(minj==-1){
    System.out.println("-1");
    return;
   }
   cost+=c[minj];
  }
  System.out.println(""+cost);
 }

 public static void main(String[] args){
  Locale.setDefault(Locale.US);
  new B().exe();
 }
}

C Balance
文字列が与えられて，ごにょごにょ操作し，ある条件を満たす物は幾つ出来るかといった内容．

組み合わせ問題は苦手ですので，飛ばしました…．
＼(＾o＾)／

D Notepad
b進数でn桁の数を，1ページあたりc個書いた時，一番最後のページには幾つの数字が書かれているか?

最終的には，
bⁿ-b^n-1 mod c
を求めるという問題に還元出来ましたが，
2≦b<10¹⁰⁶, 1≦n<10¹⁰⁶, 1≦c<10⁹
という条件に阻まれました．
＼(＾o＾)／

E Palisection
＼(＾o＾)／

・Result
○○×××

D問題が解ければ良かったのですが…．

・Rating
0->1580

初挑戦でしたが，無事Div1に昇格する事が出来ました．