ACM ICPC 2015 アジア地区予選 C : Sibling Rivalry

C : Sibling Rivalry
本戦時にぼくが戦犯してしまった問題。復習の時です。

本戦時

スタート地点から、幅優先探索でa, b, cそれぞれの手数に対して移動先を木に追加して行って、単体ではORを、全体（abc）ではANDを取ろうと考える。

重すぎ。幅優先探索を2重に書いて頭がこんがらがる。それでもあと少しでできそう！　と粘着し、友foldoriがDを通す機会を奪ってしまった。

解説時

ゴール地点から、abcで行ける地点を新たにゴール地点として追加していく方針。

最初聞いたとき分からなくて、解説の人に”C, please!”と叫んだ。でもやるだけだよね、となる。あとでkimiyukiさんに教えてもらった。ありがとうございます。

ときはいま

教えてもらった解法でちょちょいで書けそう！　👉書く。WA。
（AIZU ONLINE JUDGE: Code Review）

最初絶望したけど、普通に間違いの箇所に気づけた。ゴールのノードを追加していく作業を、ゴールまで辿り着けるか探索している作業中に追加していたため、同じ手数で若い番号が先にゴールにつけたら（新たにゴール場所として追加してしまって）、遅い番号のノードがゴールにつけたと勘違いしてしまう。

こういうコードを撃墜できるようになりたいな。

ゴールに追加する作業を、後回しにすることでAC。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
  void run() {
    int n = ni();
    int m = ni();
    int a = ni(), b = ni(), c = ni();
    int[] abc = { a, b, c };
    boolean[][] link = new boolean[n][n];
    for ( int i = 0; i < m; ++i ) {
      int u = ni() - 1;
      int v = ni() - 1;
      link[ u ][ v ] = true;
    }

    int[] goals = new int[n];
    int inf = 1 << 28;
    Arrays.fill( goals, inf );
    goals[ n - 1 ] = 0; // ゴールはゴール
    // 最悪でもn回より多くゴールは増えない。
    for ( int g = 0; g < n; ++g ) {
      ArrayList<Integer> additional_goal = new ArrayList<>();
      for ( int i = 0; i < n; ++i ) {
        if ( goals[ i ] != inf ) {
          // ゴールだったらやめる。
          continue;
        }
        boolean flag = true;
        for ( int j = 0; j < 3; ++j ) {
          int MAX_STEP = abc[ j ];
          Queue<Integer> queue = new LinkedList<>();
          Queue<Integer> qstep = new LinkedList<>();
          boolean[][] done = new boolean[MAX_STEP + 1][n];
          queue.add( i );
          qstep.add( 0 );
          done[ 0 ][ i ] = true;
          boolean subf = false;
          // どれかgoalsに辿り着ければよい。幅優先
          while (queue.size() > 0) {
            int e = queue.poll();
            int s = qstep.poll();
            if ( s == MAX_STEP ) {
              if ( goals[ e ] != inf ) {
                subf |= true;
              }
              continue;
            }
            for ( int next = 0; next < n; ++next ) {
              if ( !link[ e ][ next ] )
                continue;
              int ns = s + 1;
              if ( done[ ns ][ next ] )
                continue;
              queue.add( next );
              qstep.add( ns );
              done[ ns ][ next ] = true;
            }
          }
          // abc 全てのステップ数に対してゴールに辿り着ける手がなくてはならない。
          flag &= subf;
        }
        // ゴールの追加
        if ( flag ) {
          additional_goal.add( i );
          // debug( i + 1, g + 1 );
          // goals[ i ] = g + 1; // これがだめ。反則。
        }
      }
      for ( int i : additional_goal ) {
        goals[ i ] = g + 1;
      }
    }

    System.out.println( goals[ 0 ] != inf ? goals[ 0 ] : "IMPOSSIBLE" );
  }

  public static void main(String[] args) {
    new Main().run();
  }

  Scanner sc;

  Main() {
    sc = new Scanner( System.in );
  }

  int ni() {
    return sc.nextInt();
  }

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

軽い実装（普通の実装）が思いつけないのは単に練習不足。モチベに頼らないでいろいろできるようになりたい身体が動かない。