2010年5月24日月曜日

Google Code Jam 2010 Round 1C

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

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

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

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しか解けないので省略.

■結果
ABC
small○(9)×(14)○(18)
large○(13)×(22)×(24)
point22018

40Point,1072位.

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

0 件のコメント: