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

TopCoder SRM 699 Div1 Medium: FromToDivisible

問題

Div 2 Hard の制約きついバージョンらしいのですが、Div 2 で書いたコードがそのまま通ります。

kenkoooo.hatenablog.com

コード

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

public class FromToDivisible {
  // 最大公約数
  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 <= 1001; 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;
  }
}