Google Code Jam 2010 Round 1C

1Bで1000位以内に入れなかったので再び挑戦．

■問題A

ビルとビルの間に複数のロープを張っていく．双方のビルに張るロープの位置が与えられた時，何箇所が交差するか．

□解法A
これは見た瞬間解法が分かったので，small，large共に開始10分以内に提出できました．

view plainprint?

1. import java.io.*;  
2. import java.util.*;  
3. public class A {  
4.  int cal(int n,int[] a,int[] b){  
5.   int res=0;  
6.   for(int j=0;j<n-1;j++)  
7.    for(int i=j+1;i<n;i++)  
8.     if((a[j]-a[i])*(b[j]-b[i])<0)  
9.      res++;  
10.   return res;  
11.  }  
12.  void a() throws Exception{  
13.   Scanner sc=new Scanner(new FileReader("D:\\google_code_jam\\gcj2010\\round1c\\a\\A-large.in"));  
14.   BufferedWriter bw=new BufferedWriter(new FileWriter("D:\\google_code_jam\\gcj2010\\round1c\\a\\A-large.out"));  
15.   int T=sc.nextInt();  
16.   for(int k=0;k<T;k++){  
17.    int N=sc.nextInt();  
18.    int[] a=new int[N];  
19.    int[] b=new int[N];  
20.    for(int i=0;i<N;i++){  
21.     a[i]=sc.nextInt();  
22.     b[i]=sc.nextInt();  
23.    }  
24.    int ans=cal(N,a,b);  
25.    System.out.println("Case #"+(k+1)+": "+ans);  
26.    bw.write("Case #"+(k+1)+": "+ans);  
27.    bw.newLine();  
28.   }  
29.   bw.close();  
30.  }  
31. }  

import java.io.*;
import java.util.*;
public class A {
 int cal(int n,int[] a,int[] b){
  int res=0;
  for(int j=0;j<n-1;j++)
   for(int i=j+1;i<n;i++)
    if((a[j]-a[i])*(b[j]-b[i])<0)
     res++;
  return res;
 }
 void a() throws Exception{
  Scanner sc=new Scanner(new FileReader("D:\\google_code_jam\\gcj2010\\round1c\\a\\A-large.in"));
  BufferedWriter bw=new BufferedWriter(new FileWriter("D:\\google_code_jam\\gcj2010\\round1c\\a\\A-large.out"));
  int T=sc.nextInt();
  for(int k=0;k<T;k++){
   int N=sc.nextInt();
   int[] a=new int[N];
   int[] b=new int[N];
   for(int i=0;i<N;i++){
    a[i]=sc.nextInt();
    b[i]=sc.nextInt();
   }
   int ans=cal(N,a,b);
   System.out.println("Case #"+(k+1)+": "+ans);
   bw.write("Case #"+(k+1)+": "+ans);
   bw.newLine();
  }
  bw.close();
 }
}

■問題B
問題の内容がさっぱり分かりませんでした…．

□解法B
省略．

■問題C

白と黒のタイルで構成されたボードからチェスボード(白と黒の市松模様)を切り出していく．出来るだけ大きいチェスボードから切り出していった時，どの大きさのものが幾つ出来るか．

□解法C
コードが物凄く汚い&smallしか解けないので省略．

■結果

	A	B	C
small	○(9)	×(14)	○(18)
large	○(13)	×(22)	×(24)
point	22	0	18

40Point，1072位．

というわけで敗退．40Pointでも，早く解けた人はRound 2に進出出来たので，時間差といえば時間差です．が，もう少し，頭の切り替えが早ければ，1000以内に入れたかもしれません．