読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 699 Div2 Hard: FromToDivisibleDiv2

競技プログラミング SRM

問題

N 個の頂点があり、各頂点に 1 から N の番号が振られています。各 a[i] と b[i] について、 a[i] の倍数の全ての頂点から b[i] の倍数の全ての頂点へ距離 1 の有向辺を張ります。S から T への距離を求めてください。

解法

条件より 距離が 500 以上になることはないので、距離 500 の BFS をやるイメージで行きます。辺 x から辺 y について、b[x] と a[y] の LCM が N 以下であれば移動できると考えると簡単なグラフにできます。

コード

import java.util.ArrayDeque;
import java.util.ArrayList;

public class FromToDivisibleDiv2 {
  // 最大公約数
  private static long gcd(long a, long b) {
    return b == 0 ? a : gcd(b, a % b);
  }

  // 最小公倍数
  static long lcm(long a, long b) {
    return a * b / gcd(a, b);
  }

  final int INF = Integer.MAX_VALUE / 2;
  public int shortest(int N, int S, int T, int[] a, int[] b) {
    int M = a.length;

    ArrayList<Integer> cur = new ArrayList<>();
    ArrayList<Integer> next = new ArrayList<>();
    ArrayDeque<int[]> edges = new ArrayDeque<>();
    for (int i = 0; i < M; i++) {
      if (S % a[i] == 0 && T % b[i] == 0) return 1;
      if (S % a[i] == 0) cur.add(b[i]);
      else edges.add(new int[]{a[i], b[i]});
    }

    for (int d = 2; d <= 500; d++) {
      next.clear();
      int s = edges.size();
      for (int i = 0; i < s; i++) {
        int[] edge = edges.pollFirst();
        boolean used = false;
        for (int v : cur) {
          if (lcm(v, edge[0]) <= N) {
            used = true;
            if (T % edge[1] == 0) return d;
            next.add(edge[1]);
            break;
          }
        }
        if (!used) edges.addLast(edge);
      }

      ArrayList<Integer> tmp = cur;
      cur = next;
      next = tmp;
    }
    return -1;
  }
}