Google Code Jam 2010 Round 1B

■問題A

既に作られているディレクトリ構造と，これから作ろうとしているディレクトリ構造が与えられる．mkdirコマンドは何回実行する必要があるか．

□解法A
実装ゲー．ちまちましたミスでかなり手間取ってしまいました．

view plainprint?

1. import java.io.*;  
2. import java.util.*;  
3.   
4. public class A {  
5.   
6.  class Node{  
7.   HashMap<String, Node> children=new HashMap<String, Node>();  
8.  }  
9.   
10.  long cal(int N, int M, String[] exist, String[] create){  
11.   Node root=new Node();  
12.     
13.   for(int i=0;i<N;i++){  
14.    String[] s=exist[i].split("/");  
15.    Node node=root;  
16.    for(int k=1;k<s.length;k++){  
17.     if(!node.children.containsKey(s[k]))  
18.      node.children.put(s[k], new Node());  
19.     node=node.children.get(s[k]);  
20.    }  
21.   }  
22.     
23.   long ret=0;  
24.   for(int i=0;i<M;i++){  
25.    String[] s=create[i].split("/");  
26.    Node node=root;  
27.    for(int k=1;k<s.length;k++){  
28.     if(!node.children.containsKey(s[k])){  
29.      ret++;  
30.      node.children.put(s[k], new Node());  
31.     }  
32.     node=node.children.get(s[k]);  
33.    }  
34.   }  
35.     
36.   return ret;  
37.  }  
38.    
39.  void a() throws Exception{  
40.   Scanner sc=new Scanner(new FileReader("D:\\google_code_jam\\gcj2010\\round1b\\a\\A-large.in"));  
41.   BufferedWriter bw=new BufferedWriter(new FileWriter("D:\\google_code_jam\\gcj2010\\round1b\\a\\A-large.out"));  
42.   
43.   int T=sc.nextInt();  
44.   for(int k=0;k<T;k++){  
45.    int N=sc.nextInt();  
46.    int M=sc.nextInt();  
47.    sc.nextLine();  
48.      
49.    String[] exist=new String[N];  
50.    for(int i=0;i<N;i++)  
51.     exist[i]=sc.nextLine();  
52.      
53.    String[] create=new String[M];  
54.    for(int i=0;i<M;i++)  
55.     create[i]=sc.nextLine();  
56.      
57.    long ans=cal(N,M,exist,create);  
58.    System.out.println("Case #"+(k+1)+": "+ans);  
59.    bw.write("Case #"+(k+1)+": "+ans);  
60.    bw.newLine();  
61.   }  
62.   bw.close();  
63.  }  
64. }  

import java.io.*;
import java.util.*;

public class A {

 class Node{
  HashMap<String, Node> children=new HashMap<String, Node>();
 }

 long cal(int N, int M, String[] exist, String[] create){
  Node root=new Node();
  
  for(int i=0;i<N;i++){
   String[] s=exist[i].split("/");
   Node node=root;
   for(int k=1;k<s.length;k++){
    if(!node.children.containsKey(s[k]))
     node.children.put(s[k], new Node());
    node=node.children.get(s[k]);
   }
  }
  
  long ret=0;
  for(int i=0;i<M;i++){
   String[] s=create[i].split("/");
   Node node=root;
   for(int k=1;k<s.length;k++){
    if(!node.children.containsKey(s[k])){
     ret++;
     node.children.put(s[k], new Node());
    }
    node=node.children.get(s[k]);
   }
  }
  
  return ret;
 }
 
 void a() throws Exception{
  Scanner sc=new Scanner(new FileReader("D:\\google_code_jam\\gcj2010\\round1b\\a\\A-large.in"));
  BufferedWriter bw=new BufferedWriter(new FileWriter("D:\\google_code_jam\\gcj2010\\round1b\\a\\A-large.out"));

  int T=sc.nextInt();
  for(int k=0;k<T;k++){
   int N=sc.nextInt();
   int M=sc.nextInt();
   sc.nextLine();
   
   String[] exist=new String[N];
   for(int i=0;i<N;i++)
    exist[i]=sc.nextLine();
   
   String[] create=new String[M];
   for(int i=0;i<M;i++)
    create[i]=sc.nextLine();
   
   long ans=cal(N,M,exist,create);
   System.out.println("Case #"+(k+1)+": "+ans);
   bw.write("Case #"+(k+1)+": "+ans);
   bw.newLine();
  }
  bw.close();
 }
}

■問題B

沢山のヒヨコちゃんがレール上にいる．それぞれのヒヨコはある方向に走っており，後方のヒヨコちゃんは，前方のヒヨコちゃんに追いついてしまったら，前方のヒヨコちゃんと同じ速度に減速する．また，クレーンを使って隣り合う2匹のヒヨコちゃんを交換することが出来る．N匹のヒヨコに対し，初期位置xi[m]と速度vi[m/s]が与えられる．K(≦N)匹のヒヨコがT[s]以内でB[m]の地点に到達するように，クレーンでヒヨコを移動させた時，その最小回数はいくらか．

□解法B
ヒヨコ?クレーン?といった感じで，問題文を理解するのにかなりの時間が掛かってしまいました．分かった後はこれまた実装ゲー．

view plainprint?

1. import java.io.*;  
2. import java.util.*;  
3.   
4. public class B {  
5.   
6.  String cal(int N,int K,long B,int T,int[] x,int[] v){  
7.   boolean[] barn=new boolean[N];  
8.   int nBarn=0;  
9.   for(int i=0;i<N;i++){  
10.    int p=x[i]+v[i]*T;  
11.    if(p>=B)  
12.     nBarn++;  
13.    barn[i]=p>=B;  
14.   }  
15.   if(nBarn<K)  
16.    return "IMPOSSIBLE";  
17.   
18.   int pick=0;  
19.   int j=N;  
20.   for(int k=0;k<K;k++){  
21.    while(!barn[--j]);  
22.    for(int i=j;i+1<N&&!barn[i+1];i++){  
23.     boolean f=barn[i];  
24.     barn[i]=barn[i+1];  
25.     barn[i+1]=f;  
26.     pick++;  
27.    }  
28.   }  
29.     
30.   return ""+pick;  
31.  }  
32.    
33.  void a() throws Exception{  
34.   Scanner sc=new Scanner(new FileReader("D:\\google_code_jam\\gcj2010\\round1b\\b\\B-large.in"));  
35.   BufferedWriter bw=new BufferedWriter(new FileWriter("D:\\google_code_jam\\gcj2010\\round1b\\b\\B-large.out"));  
36.   
37.   int C=sc.nextInt();  
38.   for(int k=0;k<C;k++){  
39.    int N=sc.nextInt();  
40.    int K=sc.nextInt();  
41.    long B=sc.nextLong();  
42.    int T=sc.nextInt();  
43.    int[] x=new int[N];  
44.    int[] v=new int[N];  
45.   
46.    for(int i=0;i<N;i++)  
47.     x[i]=sc.nextInt();  
48.    for(int i=0;i<N;i++)  
49.     v[i]=sc.nextInt();  
50.      
51.    String ans=cal(N,K,B,T,x,v);  
52.    System.out.println("Case #"+(k+1)+": "+ans);  
53.    bw.write("Case #"+(k+1)+": "+ans);  
54.    bw.newLine();  
55.   }  
56.   bw.close();  
57.  }  
58.    
59. }  

import java.io.*;
import java.util.*;

public class B {

 String cal(int N,int K,long B,int T,int[] x,int[] v){
  boolean[] barn=new boolean[N];
  int nBarn=0;
  for(int i=0;i<N;i++){
   int p=x[i]+v[i]*T;
   if(p>=B)
    nBarn++;
   barn[i]=p>=B;
  }
  if(nBarn<K)
   return "IMPOSSIBLE";

  int pick=0;
  int j=N;
  for(int k=0;k<K;k++){
   while(!barn[--j]);
   for(int i=j;i+1<N&&!barn[i+1];i++){
    boolean f=barn[i];
    barn[i]=barn[i+1];
    barn[i+1]=f;
    pick++;
   }
  }
  
  return ""+pick;
 }
 
 void a() throws Exception{
  Scanner sc=new Scanner(new FileReader("D:\\google_code_jam\\gcj2010\\round1b\\b\\B-large.in"));
  BufferedWriter bw=new BufferedWriter(new FileWriter("D:\\google_code_jam\\gcj2010\\round1b\\b\\B-large.out"));

  int C=sc.nextInt();
  for(int k=0;k<C;k++){
   int N=sc.nextInt();
   int K=sc.nextInt();
   long B=sc.nextLong();
   int T=sc.nextInt();
   int[] x=new int[N];
   int[] v=new int[N];

   for(int i=0;i<N;i++)
    x[i]=sc.nextInt();
   for(int i=0;i<N;i++)
    v[i]=sc.nextInt();
   
   String ans=cal(N,K,B,T,x,v);
   System.out.println("Case #"+(k+1)+": "+ans);
   bw.write("Case #"+(k+1)+": "+ans);
   bw.newLine();
  }
  bw.close();
 }
 
}

■問題C

a1, …, ak=nという数列がある．nはk番目，kはi番目，iはj番目，…という操作の結果，最終的にa1は1番目，となるような数列はいくつあるか．与えられる数はnのみ．

□解法C
コーディングが間に合わず．

■結果

	A	B	C
small	○(12)	○(13)	×(14)
large	○(14)	○(17)	×(30)
point	26	30	0

56Point，1257位．

1000位以内に入れなかったのでRound2に進めず…．18:00からのRound1Cで1000位以内に入れなかったら敗退．