Editorial - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）

Contest Duration: 2022-06-25 21:00:00+0900 - 2022-06-25 22:40:00+0900 (local time) (100 minutes) Back to Home

Overall Editorial by cirno3153

このユーザー解説はJava/Kotlinにおける実装例を紹介するものとなっています。

A問題
B問題
C問題
D問題

A問題 - A to Z String 2

文字列を実際に構築して出力する場合、実装例は以下のようになります。

Javaの実装例

import java.util.Scanner;
import static java.lang.System.out;
public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int N = sc.nextInt(), X = sc.nextInt();
      StringBuilder sb = new StringBuilder(); // 文字列の連結にはStringBuilderを使う
      for (char i = 'A';i <= 'Z';++ i) for (int j = 0;j < N;++ j) sb.append(i);
      String S = sb.toString(); // 連結した文字列
      out.println(S.charAt(X - 1)); // Javaは0-indexedなので、1を引く
    }
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val N = sc.nextInt()
    val X = sc.nextInt()
    val S = ('A'..'Z').map {it.toString().repeat(N)}.joinToString(separator="") // 連結した文字列
    println(S[X - 1]) // Kotlinは0-indexedなので、1を引く
  }
}

ですが、 \(1\) 文字を出力するために文字列全体を構築するのは少々筋が悪いように感じます。

\(X\) 番目の文字は、 \(\lceil \frac{X}{N} \rceil\) 番目のアルファベットと表すことができます。

ここで、 \(\lceil \frac{X}{N} \rceil = \lfloor \frac{X + N - 1}{N} \rfloor\) であることを使うと式を切り捨ての形で表すことができ、通常の除算で計算できます。

また、アルファベットはASCII上で連続しているため、 \(i\) 番目のアルファベットは \(i + 97\) で表せます。ここで \(97\) はAの文字コードで、Aをintにキャストすることで得られます。

Javaの実装例

import java.util.Scanner;
import static java.lang.System.out;
public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int N = sc.nextInt(), X = sc.nextInt();
      out.println((char)((X - 1) / N + 'A'));
    }
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val N = sc.nextInt()
    val X = sc.nextInt()
    println(((X - 1) / N + 'A'.toInt()).toChar())
  }
}

B問題 - 1D Pawn

実際にシミュレーションをして求めてみましょう。

コマが昇順に並んでおり、どの操作でもコマを跨ぐような操作が行われないことから、常に \(1\) つ大きい番目のコマが隣にあるかが分かっていれば移動できるかが判定できます。

実装の際は、予め \(N+1\) 番目にダミーのコマを置いておくことで一番右のマスか否かの判定を省略することができます(このようなダミーのコマを番兵と呼びます)。

Javaの実装例

import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;
import static java.lang.System.out;
public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int N = sc.nextInt(), K = sc.nextInt(), Q = sc.nextInt();
      int[] A = new int[K + 1];
      for (int i = 0;i < K;++ i) A[i] = sc.nextInt();
      A[K] = N + 1; // 番兵、一番右のマスの右にもコマがあることにすれば場合分けが要らない
      while(Q --> 0) {
        int L = sc.nextInt() - 1;
        if (A[L] + 1 == A[L + 1]) continue; // 隣にコマがある
        ++ A[L]; // 隣にコマが無い
      }
      out.println(Arrays.stream(A)
                  .filter(i -> i <= N) // 番兵を除外
                  .mapToObj(i -> String.valueOf(i))
                  .collect(Collectors.joining(" ")) // お作法、これで空白区切りになる
                 );
    }
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val N = sc.nextInt()
    val K = sc.nextInt()
    val Q = sc.nextInt()
    val A = IntArray(K + 1) {if (it == K) N + 1 else sc.nextInt()} // 番兵、一番右のマスの右にもコマがあることにすれば場合分けが要らない
    repeat(Q) {
      val L = sc.nextInt() - 1
      if (A[L] + 1 != A[L + 1]) ++ A[L] // 隣にコマが無い
    }
    println(A.filter {it != N + 1}.joinToString(separator=" "))
  }
}

C問題 - Robot Takahashi

このような問題では、 \(X\) を動かした時に \(f(X)\) がどのように変化するかを観察する方法が有効です。

\(X\) が非常に大きい時、高橋君は全員を子供と判定するので \(f(X)\) は子供の数に等しいです。

\(X\) を減らしていくと、 \(X=W_i\) となった時に \(i\) 番目の人を大人と判定するようになります。このとき、 \(f(X)\) の更新は \(i\) 番目の人が大人か否かだけから分かります。

従って、 \(X\) を減らしていくシミュレーションをすることでこの問題を解くことができます。計算量は \(W\) を降順に並び替える部分がボトルネックとなり、 \(O(N \log N)\) です。

実装上は、 \(W\) を降順に並び替えるのではなく昇順に並び替えても構いません。

Javaの実装例

import java.util.Arrays;
import java.util.TreeMap;
import java.util.Scanner;
import java.util.stream.IntStream;
import static java.lang.System.out;
public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int N = sc.nextInt();
      char[] S = sc.next().toCharArray();
      int[] W = IntStream.range(0, N).map(i -> sc.nextInt()).toArray();
      TreeMap<Integer, Integer> diff = new TreeMap<>(); // 各iについて、Xをiまで上げた時に正しく判定される数の変化を管理する
      for (int i = 0;i < N;++ i) diff.merge(W[i], S[i] == '0' ? 1 : -1, (l, r) -> l + r);
      
      int f = (int)IntStream.range(0, N).filter(i -> S[i] == '1').count(); // 最初は全員が大人と判定される
      int ans = f;
      for (int i : diff.values()) { // Xを昇順に増やしていったときに差分更新を行う
        f += i;
        ans = Math.max(ans, f);
      }
      out.println(ans);
    }
  }
}

Kotlinの実装例

import java.util.Scanner
import kotlin.math.max
fun main() {
  Scanner(System.`in`).use { sc -> 
    val N = sc.nextInt()
    val S = sc.next().toCharArray()
    val W = IntArray(N) {sc.nextInt()}
    val diff = sortedMapOf<Int, Int>() // 各iについて、Xをiまで上げた時に正しく判定される数の変化を管理する
    for (i in 0 until N) diff.merge(W[i], if (S[i] == '0') 1 else -1) {l, r -> l + r}
    
    var f = S.filter {it == '1'}.count() // 最初は全員が大人と判定される
    var ans = f
    for (i in diff.values) { // Xを昇順に増やしていったときに差分更新を行う
      f += i
      ans = max(ans, f)
    }
    println(ans)
  }
}

直接答えを求めることもできます。

\(X\) が与えられたとき、 \(f(X)\) を求める関数を設計してみましょう。このような関数があれば、答えは \(\max(f(W_1), f(W_2), \ldots, f(W_N), f(\infty))\) で求められます。

求めるべきは、 \(S_i = 0\) かつ \(W_i < X\) である、あるいは \(S_i = 1\) かつ \(W_i \geq X\) であるような \(i\) の個数です。

簡単のため、 \(W_i < X\) であるような \(i\) の個数を求める方法を説明します。

これは、 \(W\) が昇順に並んでいるならば、二分探索を用いて判定することができます。

\(W_i \geq X\) も同様に判定することができて、計算量は二分探索の \(O(\log N)\) となります。従って、全体の計算量は \(O(N \log N)\) です。

Javaの実装例

import java.util.Arrays;
import java.util.Scanner;
import java.util.function.IntUnaryOperator;
import java.util.stream.IntStream;
import static java.lang.System.out;
public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int N = sc.nextInt();
      char[] S = sc.next().toCharArray();
      int[] W = IntStream.range(0, N).map(i -> sc.nextInt()).toArray();
      int[] child = IntStream.range(0, N)
        .filter(i -> S[i] == '0')
        .map(i -> 2 * W[i]) // Arrays.binarySearchは同一キーの場合の答えが規定されないので、隙間を空けて被らないようにする
        .sorted()
        .toArray();
      int[] adult = IntStream.range(0, N)
        .filter(i -> S[i] == '1')
        .map(i -> 2 * W[i]) // Arrays.binarySearchは同一キーの場合の答えが規定されないので、隙間を空けて被らないようにする
        .sorted()
        .toArray();
      IntUnaryOperator f = x ->
        -(Arrays.binarySearch(child, 2 * x - 1) + 1) + // childかつW[i]<xの数
        adult.length + (Arrays.binarySearch(adult, 2 * x - 1) + 1); // adultかつW[i]≧xの数、補集合を数えている
      int ans = Arrays.stream(W)
        .map(f::applyAsInt)
        .max().getAsInt();
      out.println(Math.max(ans, f.applyAsInt(1_000_000_001)));
    }
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val N = sc.nextInt()
    val S = sc.next()
    val W = IntArray(N) {sc.nextInt()}
    val child = (0 until N)
      .filter {S[it] == '0'}
      .map {2 * W[it]} // binarySearchは同一キーの場合の答えが規定されないので、隙間を空けて被らないようにする
      .sorted()
    val adult = (0 until N)
      .filter {S[it] == '1'}
      .map {2 * W[it]} // binarySearchは同一キーの場合の答えが規定されないので、隙間を空けて被らないようにする
      .sorted()
    val f = {x: Int -> 
      -(child.binarySearch(2 * x - 1) + 1) + // childかつW[i]<xの数
      adult.size + (adult.binarySearch(2 * x - 1) + 1) } // adultかつW[i]≧xの数、補集合を数えている
    println((0..N)
      .map {if (it == N) 1_000_000_001 else W[it]}
      .map(f)
      .max())
  }
}

D問題 - Jumping Takahashi 2

方針1: \(S\) を決め打つ

\(S\) を決め打った時、ジャンブ台間の移動関係は有向グラフとなります。

この時、この有向グラフに始点となるようなジャンプ台が存在するか判定したいです。

\(O(N^3 \log S)\) 解法

始点を全探索します。この時、幅優先探索を用いれば \(O(N^2)\) でその頂点から全ての頂点に辿り着くか判定することができます。

Javaの実装例

import java.util.ArrayDeque;
import java.util.BitSet;
import java.util.Queue;
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int N = sc.nextInt();
      Trampoline[] trampolines = new Trampoline[N];
      for (int i = 0;i < N;++ i) {
        trampolines[i] = new Trampoline(sc.nextLong(), sc.nextLong(), sc.nextLong());
      }
      long[][] graph = new long[N][N]; // 各ジャンプ台間を移動するために必要な訓練回数
      for (int i = 0;i < N;++ i) {
        for (int j = 0;j < N;++ j) graph[i][j] = trampolines[i].needS(trampolines[j]);
      }
      
      long ok = 4_000_000_001L, ng = 0; // okは答え以上の値、ngは答え未満の値
      binarySearch: while(ok - ng > 1) { // 二分探索
        long check = ok + ng >> 1;
        Queue<Integer> bfs = new ArrayDeque<>();
        BitSet reachable = new BitSet(N);
        for (int start = 0;start < N;++ start) { // 始点がstartとしたとき、全ての頂点に辿り着けるか探索する
          reachable.clear();
          reachable.set(start);
          bfs.add(start);
          while(!bfs.isEmpty()) {
            int from = bfs.poll();
            for (int to = 0;to < N;++ to) {
              if (reachable.get(to) || graph[from][to] > check) continue;
              reachable.set(to);
              bfs.add(to);
            }
          }
          if (reachable.cardinality() == N) { // 全ての頂点に辿り着けた
            ok = check;
            continue binarySearch;
          }
        }
        ng = check;
      }
      out.println(ok);
    }
  }
  
  static class Trampoline {
    final long x, y; // 入力が大きく、Sを計算するときにオーバーフローする可能性があるため大きい型を使う
    final long P;
    Trampoline(long x, long y, long P) {
      this.x = x;
      this.y = y;
      this.P = P;
    }
    long needS(Trampoline target) {
      return (Math.abs(x - target.x) + Math.abs(y - target.y) + P - 1) / P;
    }
  }
}

Kotlinの実装例

import java.util.ArrayDeque
import java.util.BitSet
import java.util.Scanner
import kotlin.math.abs
fun main() {
  Scanner(System.`in`).use { sc ->
    val N = sc.nextInt()
    val trampolines = Array(N) {Trampoline(sc.nextLong(), sc.nextLong(), sc.nextLong())}
    val graph = Array(N) {from ->  LongArray(N) {to -> trampolines[from].needS(trampolines[to])}} // 各ジャンプ台間を移動するために必要な訓練回数

    var ok = 4_000_000_000L // okは答え以上の値
    var ng = 0L // ngは答え未満の値
    binarySearch@ while(ok - ng > 1) { // 二分探索
      val check = (ok + ng) / 2
      val bfs = ArrayDeque<Int>()
      val reachable = BitSet(N)
      for (start in 0 until N) { // 始点がstartとしたとき、全ての頂点に辿り着けるか探索する
        reachable.clear()
        bfs.add(start)
        reachable.set(start)
        while (!bfs.isEmpty()) {
          val from = bfs.poll()
          for (to in 0 until N) {
            if (reachable[to] || graph[from][to] > check) continue
            reachable[to] = true
            bfs.add(to)
          }
        }
        if (reachable.cardinality() == N) { // 全ての頂点に辿り着けた
          ok = check
          continue@binarySearch
        }
      }
      ng = check
    }
    println(ok)
  }
}

data class Trampoline(val x: Long, val y: Long, val P: Long) { // 入力が大きく、Sを計算するときにオーバーフローする可能性があるため大きい型を使う
  fun needS(other: Trampoline) = (abs(x - other.x) + abs(y - other.y) + P - 1) / P
}

\(O(N^2 \log S)\) 解法

上の解法では始点を全探索しましたが、実は始点の候補は一つで良いです。

具体的には、グラフを強連結成分分解したとき、始点は必ず最も前の強連結成分に属するはずです。

従って、まずはグラフを強連結成分分解し、最も前の強連結成分から頂点を一つ任意に選んで始点とすれば良いです。

肝心の強連結成分分解ですが、AtCoderLibraryForJavaなどを使うと良いです。

Javaの実装例

import java.util.ArrayDeque;
import java.util.BitSet;
import java.util.Queue;
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int N = sc.nextInt();
      Trampoline[] trampolines = new Trampoline[N];
      for (int i = 0;i < N;++ i) {
        trampolines[i] = new Trampoline(sc.nextLong(), sc.nextLong(), sc.nextLong());
      }
      long[][] graph = new long[N][N]; // 各ジャンプ台間を移動するために必要な訓練回数
      for (int i = 0;i < N;++ i) {
        for (int j = 0;j < N;++ j) graph[i][j] = trampolines[i].needS(trampolines[j]);
      }
      
      long ok = 4_000_000_001L, ng = 0; // okは答え以上の値、ngは答え未満の値
      while(ok - ng > 1) { // 二分探索
        long check = ok + ng >> 1;
        Queue<Integer> bfs = new ArrayDeque<>();
        BitSet reachable = new BitSet(N);
        
        SCC scc = new SCC(N); // 全ての頂点に辿り着ける頂点が存在するならば、強連結成分分解したグラフの先頭の頂点集合に含まれる全ての頂点が条件を満たす
        for (int from = 0;from < N;++ from) {
          for (int to = 0;to < N;++ to) {
            if (graph[from][to] <= check) scc.addEdge(from, to);
          }
        }
        int start = scc.build()[0][0]; // 始点をstartとしたとき、全ての頂点に辿り着けるか探索する
        reachable.clear();
        reachable.set(start);
        bfs.add(start);
        while(!bfs.isEmpty()) {
          int from = bfs.poll();
          for (int to = 0;to < N;++ to) {
            if (reachable.get(to) || graph[from][to] > check) continue;
            reachable.set(to);
            bfs.add(to);
          }
        }
        if (reachable.cardinality() == N) ok = check; // 全ての頂点に辿り着けた
        else ng = check;
      }
      out.println(ok);
    }
  }
  
  static class Trampoline {
    final long x, y; // 入力が大きく、Sを計算するときにオーバーフローする可能性があるため大きい型を使う
    final long P;
    Trampoline(long x, long y, long P) {
      this.x = x;
      this.y = y;
      this.P = P;
    }
    long needS(Trampoline target) {
      return (Math.abs(x - target.x) + Math.abs(y - target.y) + P - 1) / P;
    }
  }
}

/**
 * @verified https://atcoder.jp/contests/practice2/tasks/practice2_g
 */
class SCC {

  static class Edge {
    int from, to;
    public Edge(int from, int to) {
      this.from = from; this.to = to;
    }
  }

  final int n;
  int m;
  final java.util.ArrayList<Edge> unorderedEdges;
  final int[] start;
  final int[] ids;
  boolean hasBuilt = false;

  public SCC(int n) {
    this.n = n;
    this.unorderedEdges = new java.util.ArrayList<>();
    this.start = new int[n + 1];
    this.ids = new int[n];
  }

  public void addEdge(int from, int to) {
    rangeCheck(from);
    rangeCheck(to);
    unorderedEdges.add(new Edge(from, to));
    start[from + 1]++;
    this.m++;
  }

  public int id(int i) {
    if (!hasBuilt) {
      throw new UnsupportedOperationException(
        "Graph hasn't been built."
      );
    }
    rangeCheck(i);
    return ids[i];
  }
    
  public int[][] build() {
    for (int i = 1; i <= n; i++) {
      start[i] += start[i - 1];
    }
    Edge[] orderedEdges = new Edge[m];
    int[] count = new int[n + 1];
    System.arraycopy(start, 0, count, 0, n + 1);
    for (Edge e : unorderedEdges) {
      orderedEdges[count[e.from]++] = e;
    }
    int nowOrd = 0;
    int groupNum = 0;
    int k = 0;
    // parent
    int[] par = new int[n];
    int[] vis = new int[n];
    int[] low = new int[n];
    int[] ord = new int[n];
    java.util.Arrays.fill(ord, -1);
    // u = lower32(stack[i]) : visiting vertex
    // j = upper32(stack[i]) : jth child
    long[] stack = new long[n];
    // size of stack
    int ptr = 0;
    // non-recursional DFS
    for (int i = 0; i < n; i++) {
      if (ord[i] >= 0) continue;
      par[i] = -1;
      // vertex i, 0th child.
      stack[ptr++] = 0l << 32 | i;
      // stack is not empty
      while (ptr > 0) {
        // last element
        long p = stack[--ptr];
        // vertex
        int u = (int) (p & 0xffff_ffffl);
        // jth child
        int j = (int) (p >>> 32);
        if (j == 0) { // first visit
          low[u] = ord[u] = nowOrd++;
          vis[k++] = u;
        }
        if (start[u] + j < count[u]) { // there are more children
          // jth child
          int to = orderedEdges[start[u] + j].to;
          // incr children counter
          stack[ptr++] += 1l << 32;
          if (ord[to] == -1) { // new vertex
            stack[ptr++] = 0l << 32 | to;
            par[to] = u;
          } else { // backward edge
            low[u] = Math.min(low[u], ord[to]);
          }
        } else { // no more children (leaving)
          while (j --> 0) {
            int to = orderedEdges[start[u] + j].to;
            // update lowlink
            if (par[to] == u) low[u] = Math.min(low[u], low[to]);
          }
          if (low[u] == ord[u]) { // root of a component
            while (true) { // gathering verticies
              int v = vis[--k];
              ord[v] = n;
              ids[v] = groupNum;
              if (v == u) break;
            }
            groupNum++; // incr the number of components
          }
        }
      }
    }
    for (int i = 0; i < n; i++) {
      ids[i] = groupNum - 1 - ids[i];
    }
    
    int[] counts = new int[groupNum];
    for (int x : ids) counts[x]++;
    int[][] groups = new int[groupNum][];
    for (int i = 0; i < groupNum; i++) {
      groups[i] = new int[counts[i]];
    }
    for (int i = 0; i < n; i++) {
      int cmp = ids[i];
      groups[cmp][--counts[cmp]] = i;
    }
    hasBuilt = true;
    return groups;
  }

  private void rangeCheck(int i) {
    if (i < 0 || i >= n) {
      throw new IndexOutOfBoundsException(
        String.format("Index %d out of bounds for length %d", i, n)
      );
    }
  }
}

Kotlinの実装例

import java.util.ArrayDeque
import java.util.BitSet
import java.util.Scanner
import kotlin.math.abs
import kotlin.math.min

fun main() {
  Scanner(System.`in`).use { sc ->
    val N = sc.nextInt()
    val trampolines = Array(N) {Trampoline(sc.nextLong(), sc.nextLong(), sc.nextLong())}
    val graph = Array(N) {from -> LongArray(N) {to -> trampolines[from].needS(trampolines[to])}} // 各ジャンプ台間を移動するために必要な訓練回数

    var ok = 4_000_000_000L // okは答え以上の値
    var ng = 0L // ngは答え未満の値
    while(ok - ng > 1) { // 二分探索
      val check = (ok + ng) / 2
      val bfs = ArrayDeque<Int>()
      val reachable = BitSet(N)
      val scc = SCC(N) // 全ての頂点に辿り着ける頂点が存在するならば、強連結成分分解したグラフの先頭の頂点集合に含まれる全ての頂点が条件を満たす
      for (from in 0 until N) {
        for (to in 0 until N) {
          if (graph[from][to] <= check) scc.addEdge(from, to)
        }
      }
      val start = scc.build()[0][0] // 始点をstartとしたとき、全ての頂点に辿り着けるか探索する
      bfs.add(start)
      reachable.set(start)
      while (!bfs.isEmpty()) {
        val from = bfs.poll()
        for (to in 0 until N) {
          if (reachable[to] || graph[from][to] > check) continue
          reachable[to] = true
          bfs.add(to)
        }
      }
      if (reachable.cardinality() == N) ok = check // 全ての頂点に辿り着けた
      else ng = check
    }
    println(ok)
  }
}

data class Trampoline(val x: Long, val y: Long, val P: Long) { // 入力が大きく、Sを計算するときにオーバーフローする可能性があるため大きい型を使う
  fun needS(other: Trampoline) = (abs(x - other.x) + abs(y - other.y) + P - 1) / P
}

class SCC(private val n: Int) {
  private data class Edge(var from: Int, var to: Int)

  private var m = 0
  private val unorderedEdges = mutableListOf<Edge>()
  private val start = IntArray(n + 1)
  private val ids = IntArray(n)
  private var hasBuilt = false
  fun addEdge(from: Int, to: Int) {
    rangeCheck(from)
    rangeCheck(to)
    unorderedEdges.add(Edge(from, to))
    start[from + 1]++
    m++
  }

  fun id(i: Int): Int {
    if (!hasBuilt) throw UnsupportedOperationException("Graph hasn't been built.")
    rangeCheck(i)
    return ids[i]
  }

  fun build(): Array<IntArray> {
    for (i in 1..n) start[i] += start[i - 1]
    val count = start.clone()
    val orderedEdges = arrayOfNulls<Edge>(m).let { edges ->
      for (e in unorderedEdges) edges[count[e.from]++] = e
      Array(m) {edges[it]!!}
    }
    var nowOrd = 0
    var groupNum = 0
    var k = 0
    // parent
    val par = IntArray(n)
    val vis = IntArray(n)
    val low = IntArray(n)
    val ord = IntArray(n) {-1}
    // u = lower32(stack[i]) : visiting vertex
    // j = upper32(stack[i]) : jth child
    val stack = LongArray(n)
    // size of stack
    var ptr = 0
    // non-recursional DFS
    for (i in 0 until n) {
      if (ord[i] >= 0) continue
      par[i] = -1
      // vertex i, 0th child.
      stack[ptr++] = 0L shl 32 or i.toLong()
      // stack is not empty
      while (ptr != 0) {
        // last element
        val p = stack[--ptr]
        // vertex
        val u = (p and 0xffffffffL).toInt()
        // jth child
        var j = (p ushr 32).toInt()
        if (j == 0) { // first visit
          ord[u] = nowOrd++
          low[u] = ord[u]
          vis[k++] = u
        }
        if (start[u] + j < count[u]) { // there are more children
          // jth child
          val to = orderedEdges[start[u] + j].to
          // incr children counter
          stack[ptr++] += 1L shl 32
          if (ord[to] == -1) { // new vertex
            stack[ptr++] = 0L shl 32 or to.toLong()
            par[to] = u
          } else { // backward edge
            low[u] = min(low[u], ord[to])
          }
        } else { // no more children (leaving)
          while (j-- > 0) {
            val to = orderedEdges[start[u] + j].to
            // update lowlink
            if (par[to] == u) low[u] = min(low[u], low[to])
          }
          if (low[u] == ord[u]) { // root of a component
            while (true) { // gathering verticies
              val v = vis[--k]
              ord[v] = n
              ids[v] = groupNum
              if (v == u) break
            }
            groupNum++ // incr the number of components
          }
        }
      }
    }
    for (i in 0 until n) ids[i] = groupNum - 1 - ids[i]
    val counts = IntArray(groupNum)
    for (x in ids) counts[x]++
    val groups = Array(groupNum) {IntArray(counts[it])}
    for (i in 0 until n) {
      val cmp = ids[i]
      groups[cmp][--counts[cmp]] = i
    }
    hasBuilt = true
    return groups
  }

  private fun rangeCheck(i: Int) {
    if (i < 0 || i >= n) {
      throw IndexOutOfBoundsException(String.format("Index %d out of bounds for length %d", i, n))
    }
  }
}

方針2: \(S\) を増やしていく

訓練を繰り返すことで、ジャンプ台間の移動可能な関係、すなわち有向辺が増えていきます。

そこで、何番目の辺が増えた段階で目標を達成できるかを考えてみましょう。

\(f(i, n)\) を \(i\) 番目までの辺を貼ったグラフにおいて、頂点 \(n\) から辿り着ける頂点の集合と定義します。

\(i\) 番目の辺が \((u, v)\) であったとき、 \(f(i, n)\) がどのように変化するかを考えます。

\(u \in f(i, n)\) のとき

頂点 \(n\) から \(u\) に到達可能なので、 \(u\) から \(v\) を通り、 \(v\) から到達可能な全ての頂点に辿り着くことができます。従って、 \(f(i, n) = f(i - 1, n) \cup f(i - 1, v)\) です。

\(u \notin f(i, n)\) のとき

頂点 \(n\) から辿り着く頂点であって辺 \((u, v)\) を通るようなものが存在しないので、 \(f(i, n) = f(i - 1, n)\) です。

\(f(i, n) = f(i - 1, n) \cup f(i - 1, v)\) の計算にBitSet::orを使うとすると、計算量は \(O(\frac{N^4}{w})\) となります。ここで \(w\) はワードサイズで、 \(64\) であるとして良いです。

Javaの実装例

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int N = sc.nextInt();
      Trampoline[] trampolines = new Trampoline[N];
      for (int i = 0;i < N;++ i) {
        trampolines[i] = new Trampoline(sc.nextLong(), sc.nextLong(), sc.nextLong());
      }
      ArrayList<Edge> edges = new ArrayList<>();
      for (int i = 0;i < N;++ i) {
        for (int j = 0;j < N;++ j) edges.add(new Edge(i, j, trampolines[i].needS(trampolines[j])));
      }
      edges.sort((l, r) -> Long.compare(l.weight, r.weight)); // 辺は重みが小さい順に増やしていく
      BitSet[][] dp = new BitSet[edges.size() + 1][N]; // dp[i][j]は、i番目まで辺を追加したときに頂点jから辿り着ける頂点の集合
      for (int i = 0;i < N;++ i) {
        dp[0][i] = new BitSet(N);
        dp[0][i].set(i);
      }
      for (int i = 0;i < edges.size();++ i) {
        Edge e = edges.get(i);
        for (int j = 0;j < N;++ j) {
          dp[i + 1][j] = (BitSet) dp[i][j].clone();
          if (dp[i][j].get(e.from)) {
            dp[i + 1][j].or(dp[i][e.to]);
            if (dp[i + 1][j].cardinality() == N) { // 全ての頂点に辿れる頂点を発見したら終わり
              out.println(e.weight);
              return;
            }
          }
        }
      }
    }
  }
  
  static class Edge {
    final int from, to;
    final long weight;
    Edge(int from, int to, long weight) {
      this.from = from;
      this.to = to;
      this.weight = weight;
    }
  }
  
  static class Trampoline {
    final long x, y; // 入力が大きく、Sを計算するときにオーバーフローする可能性があるため大きい型を使う
    final long P;
    Trampoline(long x, long y, long P) {
      this.x = x;
      this.y = y;
      this.P = P;
    }
    long needS(Trampoline target) {
      return (Math.abs(x - target.x) + Math.abs(y - target.y) + P - 1) / P;
    }
  }
}

Kotlinの実装例

import java.util.BitSet
import java.util.Scanner
import kotlin.math.abs
fun main() {
  Scanner(System.`in`).use { sc ->
    val N = sc.nextInt()
    val trampolines = Array(N) {Trampoline(sc.nextLong(), sc.nextLong(), sc.nextLong())}
    val edges = Array(N * N) {Edge(it / N, it % N, trampolines[it / N].needS(trampolines[it % N]))}
      .sortedWith(compareBy(Edge::weight)) // 辺は重みが小さい順に増やしていく

    var now = Array(N) {
      val set = BitSet(N)
      set[it] = true
      set } // now[i]は現時点で頂点iから辿れる頂点集合
    for (e in edges) {
      val next = Array(N) {i -> // next[i]は辺を一つ追加したときに頂点iから辿れる頂点集合
        val set = now[i].clone() as BitSet
        if (now[i][e.from]) set.or(now[e.to])
        set
      }
      if (next.any {it.cardinality() == N}) { // 全ての頂点に辿れる頂点を発見したら終わり
        println(e.weight)
        return
      }
      now = next
    }
  }
}

data class Edge(val from: Int, val to: Int, val weight: Long) {}

data class Trampoline(val x: Long, val y: Long, val P: Long) { // 入力が大きく、Sを計算するときにオーバーフローする可能性があるため大きい型を使う
  fun needS(other: Trampoline) = (abs(x - other.x) + abs(y - other.y) + P - 1) / P
}

方針3: 最短経路問題に帰着する

辺を追加していき、 \(i\) 番目までに追加した辺だけで辿れるか否か判定する問題は、有名な解き方が存在します。

これは、 \(i\) 番目に追加された辺の重みを \(i\) として、 \(i\) 以下の辺だけを使った経路が存在するかを求めれば良いです。この方法で解ける類題

更に言い換えると、頂点の組 \(u, v\) に対して、 \(u\) から \(v\) に重み \(i\) 以下の辺だけを使って辿り着けるかを求めればよく、これは \(u\) から \(v\) まで重みを最小化する経路を選んだ時に \(i\) 以下か否かを判定すればよいです。今回の場合は \(i\) ではなく距離 \(\lceil \frac{|x_u - x_v| + |y_u - y_v|}{P_u} \rceil\) を重みとして使えば良いですね。

さて、これは一種の最短距離問題として表せます。

重みが \(w_1, w_2, \ldots, w_n\) となるようなパスに対して、この経路の重みは \(\overset{n}{\underset{i=1}{\max}}\ w_i\) で表せます。

また、同じ頂点対に対して重みが \(w_1, w_2, \ldots, w_n\) となるような経路がある時、その頂点対の最短距離は \(\overset{n}{\underset{i=1}{\min}}\ w_i\) で表せます。

従って、この問題は \((\max, \min)\) 半環上における最短距離問題であると定式化できます。

\((\max, \min)\) 半環は束なので冪等半環です。最短距離問題としてよく使われるDijkstra法は冪等半環に対して適用できるので、この半環を用いて最短距離を解くことができます。

\(d(u, v)\) を \(u\) から \(v\) へ向かう最短距離として、全点間最短距離問題を解くことでこの値を求めておきます。

この時、頂点 \(u\) を始点としたときの答えは \(\overset{N}{\underset{v=1}{\max}}\ d(u, v)\) であり、最終的な答えは \(\overset{N}{\underset{u=1}{\min}}\ \overset{N}{\underset{v=1}{\max}}\ d(u, v)\) です。

計算量は全点間最短距離問題がボトルネックとなり、Dijkstra法、Floyd-Warshall法ともに \(O(N^3)\) です。

Javaの実装例

Dijkstra法を用いる場合

import java.util.Arrays;
import java.util.BitSet;
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int N = sc.nextInt();
      Trampoline[] trampolines = new Trampoline[N];
      for (int i = 0;i < N;++ i) {
        trampolines[i] = new Trampoline(sc.nextLong(), sc.nextLong(), sc.nextLong());
      }
      long[][] graph = new long[N][N]; // 各ジャンプ台間を移動するために必要な訓練回数
      for (int i = 0;i < N;++ i) {
        for (int j = 0;j < N;++ j) graph[i][j] = trampolines[i].needS(trampolines[j]);
      }
      long[][] dist = new long[N][N]; // dist[i][j]は、iからjまで移動するときに必要な訓練回数
      for (int s = 0;s < N;++ s) dist[s] = shortestPath(s, graph);
      long ans = Long.MAX_VALUE;
      for (int from = 0;from < N;++ from) {
        long max = 0;
        for (int to = 0;to < N;++ to) max = Math.max(max, dist[from][to]);
        ans = Math.min(ans, max);
      }
      out.println(ans);
    }
  }
  
  static long[] shortestPath(int s, long[][] graph) { // sから各頂点への最短距離をO(N^2)で求める
    int N = graph.length;
    long[] dist = new long[N];
    final long INF = 1_000_000_000_000_000_000L;
    Arrays.fill(dist, INF);
    dist[s] = 0;
    BitSet check = new BitSet(N);
    int from = s;
    do {
      check.set(from);
      for (int to = 0;to < N;++ to) {
        if (Math.max(dist[from], graph[from][to]) < dist[to]) dist[to] = Math.max(dist[from], graph[from][to]);
      }
      from = -1;
      for (int next = 0;next < N;++ next) {
        if (!check.get(next) && (from == -1 || dist[from] > dist[next])) from = next;
      }
    } while(from != -1);
    return dist;
  }
  
  static class Trampoline {
    final long x, y; // 入力が大きく、Sを計算するときにオーバーフローする可能性があるため大きい型を使う
    final long P;
    Trampoline(long x, long y, long P) {
      this.x = x;
      this.y = y;
      this.P = P;
    }
    long needS(Trampoline target) {
      return (Math.abs(x - target.x) + Math.abs(y - target.y) + P - 1) / P;
    }
  }
}

Floyd-Warshall法を用いる場合

import java.util.Scanner;
import static java.lang.System.out;
public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int N = sc.nextInt();
      Trampoline[] trampolines = new Trampoline[N];
      for (int i = 0;i < N;++ i) {
        trampolines[i] = new Trampoline(sc.nextLong(), sc.nextLong(), sc.nextLong());
      }
      long[][] graph = new long[N][N]; // 各ジャンプ台間を移動するために必要な訓練回数
      for (int i = 0;i < N;++ i) {
        for (int j = 0;j < N;++ j) graph[i][j] = trampolines[i].needS(trampolines[j]);
      }
      long[][] dist = new long[N][]; // dist[i][j]は、iからjまで移動するときに必要な訓練回数
      for (int i = 0;i < N;++ i) dist[i] = graph[i].clone();
      for (int k = 0;k < N;++ k) for (int i = 0;i < N;++ i) for (int j = 0;j < N;++ j) dist[i][j] = Math.min(dist[i][j], Math.max(dist[i][k], dist[k][j]));
      // Floyd-Warshall法は添え字の順番を忘れがちだけど、実はどのような添え字の順番でも3回書けば正しくなることが知られているよ
      // 詳しくは https://arxiv.org/abs/1904.01210 や https://qiita.com/tmaehara/items/f56be31bbb7a468a04ed を見てね
      long ans = Long.MAX_VALUE;
      for (int from = 0;from < N;++ from) {
        long max = 0;
        for (int to = 0;to < N;++ to) max = Math.max(max, dist[from][to]);
        ans = Math.min(ans, max);
      }
      out.println(ans);
    }
  }
  
  static class Trampoline {
    final long x, y; // 入力が大きく、Sを計算するときにオーバーフローする可能性があるため大きい型を使う
    final long P;
    Trampoline(long x, long y, long P) {
      this.x = x;
      this.y = y;
      this.P = P;
    }
    long needS(Trampoline target) {
      return (Math.abs(x - target.x) + Math.abs(y - target.y) + P - 1) / P;
    }
  }
}

Kotlinの実装例

Dijkstra法を用いる場合

import java.util.BitSet
import java.util.Scanner
import kotlin.math.abs
import kotlin.math.max
fun main() {
  Scanner(System.`in`).use { sc ->
    val N = sc.nextInt()
    val trampolines = Array(N) {Trampoline(sc.nextLong(), sc.nextLong(), sc.nextLong())}
    val graph = Array(N) {from -> LongArray(N) {to -> trampolines[from].needS(trampolines[to])}} // 各ジャンプ台間を移動するために必要な訓練回数
    val dist = Array(N) { shortestPath(it, graph)} // dist[i][j]は、iからjまで移動するときに必要な訓練回数
    println((0 until N).map { dist[it].max()!! }.min())
  }
}

fun shortestPath(start: Int, graph: Array<LongArray>): LongArray { // sから各頂点への最短距離をO(N^2)で求める
  val vertex = graph.size
  val INF = 1_000_000_000_000_000L
  val dist = LongArray(vertex) {if (it == start) 0L else INF}
  val check = BitSet(vertex)
  var from = start
  do {
    check.set(from)
    for (to in 0 until vertex) {
      if (max(dist[from], graph[from][to]) < dist[to]) dist[to] = max(dist[from], graph[from][to])
    }
    from = -1
    for (next in 0 until vertex) {
      if (!check[next] && (from == -1 || dist[from] > dist[next])) from = next
    }
  } while(from != -1)
  return dist
}

data class Trampoline(val x: Long, val y: Long, val P: Long) { // 入力が大きく、Sを計算するときにオーバーフローする可能性があるため大きい型を使う
  fun needS(other: Trampoline) = (abs(x - other.x) + abs(y - other.y) + P - 1) / P
}

Floyd-Warshall法を用いる場合

import java.util.Scanner
import kotlin.math.abs
import kotlin.math.max
import kotlin.math.min
fun main() {
  Scanner(System.`in`).use { sc ->
    val N = sc.nextInt()
    val trampolines = Array(N) {Trampoline(sc.nextLong(), sc.nextLong(), sc.nextLong())}
    val graph = Array(N) {from -> LongArray(N) {to -> trampolines[from].needS(trampolines[to])}} // 各ジャンプ台間を移動するために必要な訓練回数
    val dist = Array(N) { graph[it].clone()} // dist[i][j]は、iからjまで移動するときに必要な訓練回数
    for (k in 0 until N) for (i in 0 until N) for (j in 0 until N) dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]))
    // Floyd-Warshall法は添え字の順番を忘れがちだけど、実はどのような添え字の順番でも3回書けば正しくなることが知られているよ
    // 詳しくは https://arxiv.org/abs/1904.01210 や https://qiita.com/tmaehara/items/f56be31bbb7a468a04ed を見てね
    println((0 until N).map { dist[it].max()!! }.min())
  }
}

data class Trampoline(val x: Long, val y: Long, val P: Long) { // 入力が大きく、Sを計算するときにオーバーフローする可能性があるため大きい型を使う
  fun needS(other: Trampoline) = (abs(x - other.x) + abs(y - other.y) + P - 1) / P
}

TODO: これから書く

posted:
last update: