CodeChef June Cook-off 2011

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

■Correctness of Knight Move

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

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の入出力がバッファリングしてなかったため，少し調整しないと通りませんでした．

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++に乗り換えるのも手だと思われます．