CodeChef June Cook-off 2011

CodeChef June Cook-off 2011（6/20 1:00~3:30)

■Correctness of Knight Move

やるだけ．出力をバッファリングしないとTLEします（しました）．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.  Scanner sc=new Scanner(System.in);  
11.   
12.  int INF=1<<28;  
13.  double EPS=1e-9;  
14.   
15.  int n;  
16.  String s;  
17.   
18.  void run(){  
19.   n=sc.nextInt();  
20.   sc.nextLine();  
21.   String[] ans={"Yes", "No", "Error"};  
22.   for(int i=0; i<n; i++){  
23.    s=sc.nextLine();  
24.    println(ans[solve()]);  
25.   }  
26.   System.out.flush();  
27.  }  
28.   
29.  int solve(){  
30.   boolean legal=true;  
31.   if(s.length()!=5){  
32.    return 2;  
33.   }  
34.   legal&='a'<=s.charAt(0)&&s.charAt(0)<='h';  
35.   legal&='1'<=s.charAt(1)&&s.charAt(1)<='8';  
36.   legal&=s.charAt(2)=='-';  
37.   legal&='a'<=s.charAt(3)&&s.charAt(3)<='h';  
38.   legal&='1'<=s.charAt(4)&&s.charAt(4)<='8';  
39.   if(!legal){  
40.    return 2;  
41.   }  
42.   int x1=s.charAt(0)-'a';  
43.   int y1=s.charAt(1)-'1';  
44.   int x2=s.charAt(3)-'a';  
45.   int y2=s.charAt(4)-'1';  
46.   
47.   int dx=abs(x1-x2);  
48.   int dy=abs(y1-y2);  
49.   
50.   return (dx==1&&dy==2)||(dx==2&&dy==1)?0:1;  
51.  }  
52.   
53.  void println(String s){  
54.   System.out.println(s);  
55.  }  
56.   
57.  void print(String s){  
58.   System.out.print(s);  
59.  }  
60.   
61.  void debug(Object... os){  
62.   System.err.println(Arrays.deepToString(os));  
63.  }  
64.   
65.  public static void main(String[] args){  
66.   System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
67.   new Main().run();  
68.  }  
69. }  

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-9;

 int n;
 String s;

 void run(){
  n=sc.nextInt();
  sc.nextLine();
  String[] ans={"Yes", "No", "Error"};
  for(int i=0; i<n; i++){
   s=sc.nextLine();
   println(ans[solve()]);
  }
  System.out.flush();
 }

 int solve(){
  boolean legal=true;
  if(s.length()!=5){
   return 2;
  }
  legal&='a'<=s.charAt(0)&&s.charAt(0)<='h';
  legal&='1'<=s.charAt(1)&&s.charAt(1)<='8';
  legal&=s.charAt(2)=='-';
  legal&='a'<=s.charAt(3)&&s.charAt(3)<='h';
  legal&='1'<=s.charAt(4)&&s.charAt(4)<='8';
  if(!legal){
   return 2;
  }
  int x1=s.charAt(0)-'a';
  int y1=s.charAt(1)-'1';
  int x2=s.charAt(3)-'a';
  int y2=s.charAt(4)-'1';

  int dx=abs(x1-x2);
  int dy=abs(y1-y2);

  return (dx==1&&dy==2)||(dx==2&&dy==1)?0:1;
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

■Super-plane

Dunnoの挙動は分岐無しなので，適当なループで解けます．コンテスト中は勘違いしていて，BFSをしようとしてTLE食らいまくっていました．さらに，Javaの入出力がバッファリングしてなかったため，少し調整しないと通りませんでした．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.  // Scanner sc=new Scanner(System.in);  
11.   
12.  int INF=1<<28;  
13.  double EPS=1e-9;  
14.   
15.  int t, n;  
16.  int cs, ts, cg, tg;  
17.  E[] es;  
18.   
19.  void run() throws Exception{  
20.   BufferedReader br=new BufferedReader(new InputStreamReader(System.in));  
21.   t=Integer.parseInt(br.readLine());  
22.   for(; t>0; t--){  
23.    n=Integer.parseInt(br.readLine());  
24.    es=new E[n];  
25.    for(int i=0; i<n; i++){  
26.     String[] ss=br.readLine().split(" ");  
27.     int c1=Integer.parseInt(ss[0])-1;  
28.     int t1=Integer.parseInt(ss[1]);  
29.     int c2=Integer.parseInt(ss[2])-1;  
30.     int t2=Integer.parseInt(ss[3]);  
31.     es[i]=new E(c1, t1, c2, t2);  
32.    }  
33.    sort(es);  
34.    String[] ss=br.readLine().split(" ");  
35.    cs=Integer.parseInt(ss[0])-1;  
36.    ts=Integer.parseInt(ss[1]);  
37.    cg=Integer.parseInt(ss[2])-1;  
38.    tg=Integer.parseInt(ss[3]);  
39.    solve();  
40.   }  
41.   System.out.flush();  
42.  }  
43.   
44.  void solve(){  
45.   P p=new P(cs, ts);  
46.   boolean[] visited=new boolean[n];  
47.   int ans=0;  
48.   boolean ok=true;  
49.   E key=new E(p.c, p.t, 0, 0);  
50.   for(;; ans++){  
51.    if(p.c==cg&&p.t<=tg){  
52.     break;  
53.    }  
54.    key.c1=p.c;  
55.    key.t1=p.t;  
56.    int k=binarySearch(es, key);  
57.    if(k<0){  
58.     k=-1-k;  
59.    }  
60.    if(k==n){  
61.     ok=false;  
62.     break;  
63.    }  
64.    if(es[k].c1!=p.c){  
65.     ok=false;  
66.     break;  
67.    }  
68.    if(visited[k]){  
69.     ok=false;  
70.     break;  
71.    }  
72.    visited[k]=true;  
73.    p.c=es[k].c2;  
74.    p.t=es[k].t2;  
75.   }  
76.   if(ok){  
77.    println("Yes "+ans);  
78.   }else{  
79.    println("No");  
80.   }  
81.  }  
82.   
83.  class E implements Comparable<E>{  
84.   int c1, t1, c2, t2;  
85.   
86.   E(int c1, int t1, int c2, int t2){  
87.    this.c1=c1;  
88.    this.t1=t1;  
89.    this.c2=c2;  
90.    this.t2=t2;  
91.   }  
92.   
93.   @Override  
94.   public int compareTo(E e){  
95.    if(c1!=e.c1){  
96.     return c1-e.c1;  
97.    }else{  
98.     return t1-e.t1;  
99.    }  
100.   }  
101.  }  
102.   
103.  class P implements Comparable<P>{  
104.   int c, t;  
105.   
106.   P(int c, int t){  
107.    this.c=c;  
108.    this.t=t;  
109.   }  
110.   
111.   @Override  
112.   public int compareTo(P p){  
113.    if(c!=p.c){  
114.     return c-p.c;  
115.    }else{  
116.     return t-p.t;  
117.    }  
118.   }  
119.  }  
120.   
121.  void println(String s){  
122.   System.out.println(s);  
123.  }  
124.   
125.  void print(String s){  
126.   System.out.print(s);  
127.  }  
128.   
129.  void debug(Object... os){  
130.   System.err.println(Arrays.deepToString(os));  
131.  }  
132.   
133.  public static void main(String[] args){  
134.   System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
135.   try{  
136.    new Main().run();  
137.   }catch(Exception e){  
138.    e.printStackTrace();  
139.   }  
140.  }  
141. }  

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-9;

 int t, n;
 int cs, ts, cg, tg;
 E[] es;

 void run() throws Exception{
  BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  t=Integer.parseInt(br.readLine());
  for(; t>0; t--){
   n=Integer.parseInt(br.readLine());
   es=new E[n];
   for(int i=0; i<n; i++){
    String[] ss=br.readLine().split(" ");
    int c1=Integer.parseInt(ss[0])-1;
    int t1=Integer.parseInt(ss[1]);
    int c2=Integer.parseInt(ss[2])-1;
    int t2=Integer.parseInt(ss[3]);
    es[i]=new E(c1, t1, c2, t2);
   }
   sort(es);
   String[] ss=br.readLine().split(" ");
   cs=Integer.parseInt(ss[0])-1;
   ts=Integer.parseInt(ss[1]);
   cg=Integer.parseInt(ss[2])-1;
   tg=Integer.parseInt(ss[3]);
   solve();
  }
  System.out.flush();
 }

 void solve(){
  P p=new P(cs, ts);
  boolean[] visited=new boolean[n];
  int ans=0;
  boolean ok=true;
  E key=new E(p.c, p.t, 0, 0);
  for(;; ans++){
   if(p.c==cg&&p.t<=tg){
    break;
   }
   key.c1=p.c;
   key.t1=p.t;
   int k=binarySearch(es, key);
   if(k<0){
    k=-1-k;
   }
   if(k==n){
    ok=false;
    break;
   }
   if(es[k].c1!=p.c){
    ok=false;
    break;
   }
   if(visited[k]){
    ok=false;
    break;
   }
   visited[k]=true;
   p.c=es[k].c2;
   p.t=es[k].t2;
  }
  if(ok){
   println("Yes "+ans);
  }else{
   println("No");
  }
 }

 class E implements Comparable<E>{
  int c1, t1, c2, t2;

  E(int c1, int t1, int c2, int t2){
   this.c1=c1;
   this.t1=t1;
   this.c2=c2;
   this.t2=t2;
  }

  @Override
  public int compareTo(E e){
   if(c1!=e.c1){
    return c1-e.c1;
   }else{
    return t1-e.t1;
   }
  }
 }

 class P implements Comparable<P>{
  int c, t;

  P(int c, int t){
   this.c=c;
   this.t=t;
  }

  @Override
  public int compareTo(P p){
   if(c!=p.c){
    return c-p.c;
   }else{
    return t-p.t;
   }
  }
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  try{
   new Main().run();
  }catch(Exception e){
   e.printStackTrace();
  }
 }
}

■Result

--o--

またもやこれは酷い…．CodeChefとは相性が悪いようです．C++に乗り換えるのも手だと思われます．