TopCoder SRM 513

TopCoder SRM 513(7/26 20:00~22:00)

珍しい時間帯のSRM．夕飯後は眠くなるので辛い．

■YetAnotherIncredibleMachine(Easy)

・解法

全探索．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class YetAnotherIncredibleMachine {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public int countWays(int[] mount, int[] length, int[] balls) {
  int n=length.length;
  int m=balls.length;
  long res=1;
  long mod=1000000009;
  for(int j=0;j<n;j++){ 
   int c=0;
   for(int x=-length[j];x<=0;x++){
    boolean f=true;
    for(int i=0;i<m;i++){
     if(mount[j]+x<=balls[i]&&balls[i]<=mount[j]+x+length[j]){
      f=false;
     }
    }
    if(f){
     c++;
    }
   }
   res=(res*c)%mod;
  }
  return (int)res;
 }

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

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

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


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

■PerfectMemory(Medium)

n(：偶数)枚のカードで神経衰弱を行う．一度めくったカードを全て記憶しておくことができるとしたとき，最適な戦略を用いた場合のゲーム終了までにめくる回数の期待値を求めよ．

解法

(残り枚数, 既に知っているカードの枚数)で期待値のDP．
既に知っているカードには，ペアは含まれない（=どの2枚も異なる）とする．
状態が(n, m)の時，n-mから1枚引く．

図では，暗い赤が知っているm枚（引かれないカード）， 明るい赤は暗い赤のカードに対応するペアの片割れ．

1.明るい赤を引いた時(m枚)

対応するカードを暗い赤から選ぶ． つまり，1ターンで，状態が(n-2,m-1)になる． よって，この時の期待値は1+dp(n-2,m-1)．

2.青を引いた時(n-2m枚)

引いたカードを暗い紫とする．この時対応するカードは青にある（明るい紫）． 次に，n-m-1(青+明るい赤+明るい紫)から1枚引く．

2.1.明るい赤を引いたとき(m枚)

次のターンで，対応する赤のペアを引く． この時の期待値は，2+dp(n-2,m)．

2.2.青を引いたとき(n-2m-2枚)

既に知っているカードが2枚増えるだけなので， この時の期待値は，1+dp(n,m+2)．

2.3.明るい紫を引いたとき(1枚)

紫ペアがなくなるので，この時の期待値は，1+(n-2,m)．

これらからDPテーブルを更新していきます．初期値の与え方が面倒なので，メモ化再帰でもいいかも知れません．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class PerfectMemory {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public double getExpectation(int N, int M) {
  int n=N*M;
  double[][] dp=new double[n+1][n+1];
  for(int j=2;j<=n;j+=2){
   for(int i=j;i>=j/2;i--){
    dp[j][i]=j/2;
   }
   for(int i=j/2-1;i>=0;i--){
    double p1=(double)(j-2*i)/(j-i);
    double p2=(double)i/(j-i);
    double q1=(double)i/(j-i-1);
    double q2=(double)(j-2*i-2)/(j-i-1);
    double q3=(double)1/(j-i-1);
    dp[j][i]+=(2+dp[j-2][i])*p1*q1;
    dp[j][i]+=(1+dp[j][i+2])*p1*q2;
    dp[j][i]+=(1+dp[j-2][i])*p1*q3;
    if(i>0){
     dp[j][i]+=(1+dp[j-2][i-1])*p2;
    }
   }
  }
  for(int i=0;i<=n;i+=2){
   // debug(i, dp[i]);
  }
  return dp[n][0];
 }

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

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

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


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

■Challenge Phase

撃墜無し．

■Result

oo- +0/-0
429.5pts. 104th
おそらくDiv.1では過去最高の成績です．加えてMediumを解けたのが初めてです．

■Rating

1620 -> 1727
大幅上昇．

TopCoder SRM 511

TopCoder SRM 511(7/3 1:00~3:00)

YellowCoderとしては初のSRM．

■Zoo(Easy)

・問題

うさぎと猫がN匹いる．きつねは，うさぎと猫の区別が分からない．
そこで，N匹のそれぞれに「自分と同じ種類でかつ自分より背の高い動物は何匹いますか？」と尋ねた．
この情報のみを用いて，N匹へのうさぎと猫の割り当て方の総数を求めよ．

・解法

N匹の答えをa[0],…,a[N-1]とし，
配列countを配列aに出てきた数字の個数とする．
例えば， a={0,1,0,1,2,3}
だったら，
count={2,2,1,1,0,0,…}
となる．
上の例では，一方が2匹，もう一方が4匹いると分かる．
まず，うさぎが2匹，猫が4匹とする．
このとき，a[i]が0または1のときに関しては，うさぎと猫をどのように割り当てても良い．
具体的には，
RRCC|CC
CCRR|CC
RCCR|CC
CRRC|CC
こんな感じ（2²通り）．
逆に，うさぎが4匹，猫が2匹としても，上と同じよう構成ができるので，
結局2*2²=8通り．
これは，5匹と2匹，6匹と2匹，…でも変わらない．
そのため，N=m+nと分かれる場合，
m≠nならば，2*2^min(m,n)通り，
m=nならば，2^m通り．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Zoo {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public long theCount(int[] a) {
  int n=a.length;
  int[] count=new int[n];
  for(int i:a){
   if(i>=n){
    return 0;
   }
   if(++count[i]>2){
    return 0;
   }
  }
  int p=0, q=0;
  int k=0;
  // debug(count);
  for(int i=n-1;i>=0;i--){
   if(count[i]==k+2){
    p=q=i+1;
   }
   else if(count[i]==k+1){
    if(k==0){
     p=i+1;
    }else if(k==1){
     q=i+1;
    }
   }
   else if(count[i]==k){
   }
   else{
    return 0;
   }
   k=count[i];
  }
  // debug(p,q);
  long ret=1;
  for(int i=0;i<min(p,q);i++){
   ret*=2;
  }
  return ret*(p!=q?2:1);
 }

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

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

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

■FiveHundredElevenAdd(Medium)

本番は解けませんでしたので，simezi_tanさんの記事を参照下さい．
SRM 511 Div1 Medium FiveHundredEleven - simezi_tanの日記

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class FiveHundredEleven {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 int[][] memo; // 0:win, 1:lose
 int[] cards;
 int n;

 int rec(int step,int mem){
  if(memo[step][mem]>=0){
   return memo[step][mem];
  }
  if(mem==511){
   // former player loses.
   return memo[step][mem]=0;
  }
  if(step==n){
   // the player can't choose a card.
   return memo[step][mem]=1;
  }
  int not=0;
  for(int i=0;i<n;i++){
   if((mem|cards[i])==mem){
    not++;
   }
  }
  boolean win=false;
  // search : not-step cards that don't affect mem are not used
  if(not>step){
   win|=rec(step+1,mem)==1;
  }
  // search : cards that affect mem.
  for(int i=0;i<n;i++){
   if((mem|cards[i])!=mem){
    win|=rec(step+1,mem|cards[i])==1;
   }
  }
  return memo[step][mem]=win?0:1;
 }

 public String theWinner(int[] cards) {
  this.cards=cards;
  n=cards.length;
  memo=new int[n+1][512];
  for(int i=0;i<n+1;i++){
   fill(memo[i],-1);
  }
  return rec(0,0)==0?"Fox Ciel":"Toastman";
 }

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

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

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

■Challenge Phase

撃墜無し．撃墜しようと準備していましたが，他の人のコードが中々読めませんでした．

■Result

o-- +0/-0
144.29pts. 491th

■Rating

1532 -> 1527
微減．次は，TCO Round3ですが，個人的には気楽に挑戦したいと思っています．

TCO Algorithm Round2

TCO Algorithm Round2(6/26 1:00~3:00)

驚異の悪運によりRound1を通過することが出来ていましたが，果してRound2は…．

■GuessTheNumberGame(Easy)

ある数字Mを1~Nまでの数で割り切れるかどうかを表す文字列を考える． 例えばM=4，N=5とすると4は1,2,4で割り切れ，3,5では割り切れないので， YYNYN となる． さて，N=5のとき， YNNYN となるようなMは存在しないため， この文字列は無効である（4で割り切れて、2で割り切れないから）． 長さMの文字列で，有効なものは何種類あるか． 2種類以上の素数の積からなる合成数は， 素因数のY or Nで一意に決まってしまうので，考慮しない． 例えば， YYY--XならX=Y YYN--XならX=N YNY--XならX=N YNN--XならX=N となる． 次に，ある素数の冪乗を考える． 例えば，M=9とすると，2の冪乗は2,4,8まで．この3つに着目した有効な文字列は， NNN YNN YYN YYY の4種類． つまり，p¹, p²,…, p^rについて有効な文字列はr+1種類． あとは，それらを掛け合わせるだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class GuessTheNumberGame {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public int possibleClues(int n) {
  long res=1;
  long mod=1000000007;
  boolean[] isP=new boolean[n+1];
  int[] p=new int[n+1];
  fill(isP,true);
  isP[0]=isP[1]=false;
  int k=0;
  for(int j=0;j<=n;j++){
   if(!isP[j]){
    continue;
   }
   p[k++]=j;
   for(int i=j*2;i<=n;i+=j){
    isP[i]=false;
   }
  }
  // debug(p);
  for(int i=0;i<k;i++){
   int c=0;
   for(long m=1;m<=n;m*=p[i]){
    c++;
   }
   // debug(i,p[i],c);
   res=(res*c)%mod;
  }
  return (int)res;
 }

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

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

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

■Challenge Phase

撃墜無し．

■Result

o-- +0/-0
196.11pts. 341th
辛くも逃げきることが出来ました．

■Rating

1431 -> 1530
Round3進出+初YellowCoderです． 今年のICPCは国内予選で落ちてしまったので，中々にショックでしたが， 代わりにGoogleとTopCoder両方のTシャツをゲットできそうです．

Aizu Online Judge 1149 Cut the Cakes

■1149 Cut the Cakes

やればできる．

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, w, h;
 int[] ps, ss;

 void run(){
  for(;;){
   n=sc.nextInt();
   w=sc.nextInt();
   h=sc.nextInt();
   if((n|w|h)==0){
    break;
   }
   ps=new int[n];
   ss=new int[n];
   for(int i=0; i<n; i++){
    ps[i]=sc.nextInt()-1;
    ss[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  LinkedList<R> list=new LinkedList<R>();
  list.add(new R(0, 0, w, h));
  for(int i=0; i<n; i++){
   R r=list.remove(ps[i]);
   debug(i, r.x, r.y, r.w, r.h);
   int x=r.x, y=r.y;
   for(int k=0; k<ss[i]; k++){
    if(y==r.y&&x<r.x+r.w){
     x++;
    }else if(x==r.x+r.w&&y<r.y+r.h){
     y++;
    }else if(y==r.y+r.h&&x>r.x){
     x--;
    }else if(x==r.x&&y>r.y){
     y--;
    }else{
     debug("Error!");
    }
    // debug(x,y);
   }
   debug(x, y);
   R r1=null, r2=null;
   if(x==r.x||x==r.x+r.w){
    r1=new R(r.x, r.y, r.w, y-r.y);
    r2=new R(r.x, r.y+r1.h, r.w, r.h-r1.h);
   }else{
    r1=new R(r.x, r.y, x-r.x, r.h);
    r2=new R(r.x+r1.w, r.y, r.w-r1.w, r.h);
   }
   debug("r1", r1.x, r1.y, r1.w, r1.h);
   debug("r2", r2.x, r2.y, r2.w, r2.h);
   if(r1.w*r1.h<r2.w*r2.h){
    list.add(r1);
    list.add(r2);
   }else{
    list.add(r2);
    list.add(r1);
   }
  }
  R[] rs=list.toArray(new R[0]);
  sort(rs);
  String ans="";
  for(R r : rs){
   ans+=(r.w*r.h)+" ";
   debug(r.x, r.y, r.w, r.h, r.w*r.h);
  }
  println(ans.substring(0, ans.length()-1));
 }

 class R implements Comparable<R>{
  int x, y, w, h;

  R(int x, int y, int w, int h){
   this.x=x;
   this.y=y;
   this.w=w;
   this.h=h;
  }

  @Override
  public int compareTo(R r){
   return w*h-r.w*r.h;
  }
 }

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

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

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

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

Aizu Online Judge 1131 Unit Fraction Partition

■1131 Unit Fraction Partition

自明な+ちょっと工夫した枝刈りでAC．

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 p0, q0, maxA, maxN;
 int ans;

 void run(){
  for(;;){
   p0=sc.nextInt();
   q0=sc.nextInt();
   maxA=sc.nextInt();
   maxN=sc.nextInt();
   if((p0|q0|maxA|maxN)==0){
    break;
   }
   solve();
  }
 }

 void solve(){
  int gcd=gcd(p0, q0);
  p0/=gcd;
  q0/=gcd;
  ans=0;
  dfs(0, 1, 1, 1, 0);
  // debug(ans);
  println(""+ans);
 }

 void dfs(int p, int q, int qNow, int a, int n){
  if(n>maxN){
   return;
  }
  if(a>maxA){
   return;
  }
  if(p*q0-q*p0>0){
   return;
  }
  {
   int p2=maxN-n;
   int q2=qNow;
   int pp=p*q2+q*p2;
   int qq=q*q2;
   if(pp*q0-qq*p0<0){
    return;
   }
  }
  // debug(p,q,qNow,a,n);
  if(p==p0&&q==q0){
   ans++;
   return;
  }
  for(int i=qNow; i*a<=maxA; i++){
   int p2=p*i+q;
   int q2=q*i;
   int gcd=gcd(p2, q2);
   p2/=gcd;
   q2/=gcd;
   dfs(p2, q2, i, i*a, n+1);
  }
 }

 int gcd(int m, int n){
  for(; m!=0;){
   int t=n%m;
   n=m;
   m=t;
  }
  return n;
 }

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

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

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

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

Aizu Online Judge 1156 Twirling Robot

■1156 Twirling Robot

(x座標，y座標，方向ベクトル)を状態としたDijkstra．コストのつけ方が特殊だが，少し注意すれば特に問題無い．

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 m, n;
 int[][] a;
 int[] c;

 void run(){
  for(;;){
   m=sc.nextInt();
   n=sc.nextInt();
   if((m|n)==0){
    break;
   }
   a=new int[n][m];
   for(int j=0; j<n; j++){
    for(int i=0; i<m; i++){
     a[j][i]=sc.nextInt();
    }
   }
   c=new int[4];
   for(int i=0; i<4; i++){
    c[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  int[][][] d=new int[n][m][4];
  for(int j=0; j<n; j++){
   for(int i=0; i<m; i++){
    fill(d[j][i], INF);
   }
  }
  int[] dx={1, 0, -1, 0};
  int[] dy={0, 1, 0, -1};
  PriorityQueue<P> que=new PriorityQueue<P>();
  que.offer(new P(0, 0, 0));
  d[0][0][0]=0;
  for(; !que.isEmpty();){
   P p=que.poll();
   if(p.d>d[p.y][p.x][p.v]){
    continue;
   }
   int[] cost=c.clone();
   if(a[p.y][p.x]!=4){
    cost[a[p.y][p.x]]=0;
   }
   for(int i=0; i<4; i++){
    P q=new P(p.x, p.y, (p.v+i)%4);
    q.x+=dx[q.v];
    q.y+=dy[q.v];
    if(q.x<0||q.x>=m||q.y<0||q.y>=n){
     continue;
    }
    if(d[q.y][q.x][q.v]>d[p.y][p.x][p.v]+cost[i]){
     q.d=d[q.y][q.x][q.v]=d[p.y][p.x][p.v]+cost[i];
     que.offer(q);
    }
   }
  }
  int ans=INF;
  for(int i=0; i<4; i++){
   ans=min(ans, d[n-1][m-1][i]);
  }
  println(ans+"");
 }

 class P implements Comparable<P>{
  int x, y, v;
  int d;

  P(int x, int y, int v){
   this.x=x;
   this.y=y;
   this.v=v;
  }

  @Override
  public int compareTo(P p){
   return d-p.d;
  }
 }

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

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

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

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

Aizu Online Judge 1136 Polygonal Line Search

■1136 Polygonal Line Search

回転および平行移動を適用したということは，各々の線分ベクトルを0,90,180,270°の何れかの角度回転させたことになる．従って，元の折れ線の内の1つの線分ベクトルと，探す対象の折れ線の内の1つの線分ベクトルを見れば何度回転させたか分かる．あとは，残りの線分ベクトルを回転させ，元の折れ線の線分ベクトルに一致するかを見ていけば良い．

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;
 int[] m;
 int[][] xs, ys;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   m=new int[n+1];
   xs=new int[n+1][];
   ys=new int[n+1][];
   for(int j=0; j<=n; j++){
    m[j]=sc.nextInt();
    xs[j]=new int[m[j]];
    ys[j]=new int[m[j]];
    for(int i=0; i<m[j]; i++){
     xs[j][i]=sc.nextInt();
     ys[j][i]=sc.nextInt();
    }
   }
   solve();
  }
 }

 void solve(){
  for(int i=1; i<=n; i++){
   if(m[0]==m[i]&&match(m[0], xs[0], ys[0], xs[i], ys[i])){
    println(i+"");
   }
  }
  println("+++++");
 }

 boolean match(int m, int[] xs1, int[] ys1, int[] xs2, int[] ys2){
  int[][][] a={{{1, 0}, {0, 1}}, {{0, -1}, {1, 0}}, {{-1, 0}, {0, -1}},
    {{0, 1}, {-1, 0}}};

  int k1=-1, k2=-1;
  for(int j=0; j<4; j++){
   int vx1=xs1[1]-xs1[0];
   int vy1=ys1[1]-ys1[0];
   int vx2=xs2[1]-xs2[0];
   int vy2=ys2[1]-ys2[0];
   if(vx1*a[j][0][0]+vy1*a[j][0][1]==vx2
     &&vx1*a[j][1][0]+vy1*a[j][1][1]==vy2){
    k1=j;
   }
   int vx3=xs2[m-2]-xs2[m-1];
   int vy3=ys2[m-2]-ys2[m-1];
   if(vx1*a[j][0][0]+vy1*a[j][0][1]==vx3
     &&vx1*a[j][1][0]+vy1*a[j][1][1]==vy3){
    k2=j;
   }
  }

  boolean f1=k1!=-1, f2=k2!=-1;
  for(int i=0; i<m-1; i++){
   int vx1=xs1[i+1]-xs1[i];
   int vy1=ys1[i+1]-ys1[i];
   int vx2=xs2[i+1]-xs2[i];
   int vy2=ys2[i+1]-ys2[i];
   int vx3=xs2[m-i-2]-xs2[m-i-1];
   int vy3=ys2[m-i-2]-ys2[m-i-1];
   if(k1!=-1){
    f1&=vx1*a[k1][0][0]+vy1*a[k1][0][1]==vx2
      &&vx1*a[k1][1][0]+vy1*a[k1][1][1]==vy2;
   }
   if(k2!=-1){
    f2&=vx1*a[k2][0][0]+vy1*a[k2][0][1]==vx3
      &&vx1*a[k2][1][0]+vy1*a[k2][1][1]==vy3;
   }
  }

  return f1||f2;
 }

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

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

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

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

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