Editorial - Tokio Marine & Nichido Fire Insurance Programming Contest 2022（AtCoder Beginner Contest 256)

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

Overall Editorial by cirno3153

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

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

A問題 - 2^N

Java/Kotlinでは、 \(2^N\) を表すために左シフトを用いることができます。

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();
      out.println(1 << N);
    }
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val N = sc.nextInt()
    println(1 shl N)
  }
}

また、 \(a^b\) を表すためにMath.powを使う手もあります。ただし、Math.powは実数を対象とするものなので、整数で扱う際には自作しておく方が無難です。今回の制約下では精度が足りているためACできますが、下記の例ではpow関数を自作する場合を書いておきます。

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();
      out.println(pow(2, N));
    }
  }
  public static long pow(long a, long b) {
    long ans = 1;
    for (long mul = a; b != 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;
    return ans;
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val N = sc.nextLong()
    println(pow(2L, N))
  }
}

fun pow(a: Long, b: Long): Long {
  var ans = 1L // 答え
  var mul = a // a^bitの値
  var bit = 1L // 2冪の値を取る
  while (b >= bit) {
    if ((b and bit) != 0L) ans *= mul // 2進数上で1となる桁の部分をansに足していく
    bit = bit shl 1
    mul *= mul
  }
  return ans
}

B問題 - Batters

野球がモチーフなので、駒を人、マスを塁と読み替えておきます。

この問題は、大きく分けて2つの方針が存在します。

1つ目の方針は、どの塁に人が居るかを管理するものです。

2つ目の方針は、誰がどの場所に居るかを管理するものです。

方針1: どの塁に人が居るかを管理する

まず、塁を管理する配列basesを作りましょう。各塁について人が居るか否かが分かれば良いので、basesはboolean型の配列となります。

そして、 \(A_i\) が与えられる、すなわちヒットを打つ度に進塁する処理を書けば良いです。

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)) {
      boolean[] bases = new boolean[4]; // Javaでは、boolean配列はfalseで初期化される
      int N = sc.nextInt();
      int run = 0; // 得た得点
      while (N --> 0) { // N --> 0 は、Nが1ずつ減って0になるまで動く(つまりN回ループが回る)
        int A = sc.nextInt();
        bases[0] = true;
        for (int i = bases.length - 1;i >= 0;-- i) { // 本塁に近い走者から処理すること！！
          if (!bases[i]) continue; // 人がこの塁に居ないなら処理をしない(ガード構文)
          bases[i] = false;
          if (i + A < bases.length) bases[i + A] = true; // 進塁
          else ++ run;
        }
      }
      out.println(run);
    }
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val bases = BooleanArray(4) // Kotlinでは、boolean配列はfalseで初期化される
    val N = sc.nextInt()
    var run = 0 // 得た得点
    repeat(N) {
      val A = sc.nextInt()
      bases[0] = true
      for (i in bases.size - 1 downTo 0) { // 本塁に近い走者から処理すること！！
        if (!bases[i]) continue // 人がこの塁に居ないなら処理をしない(ガード構文)
        bases[i] = false
        if (i + A < bases.size) bases[i + A] = true // 進塁
        else ++ run
      }
    }
    println(run)
  }
}

ところで、同じ塁には高々一人しか居ないということは、どの塁に人が居るか、という関係は人の居る塁の集合として考えることができます。

すなわち、basesはSetあるいはBitSetを用いて表すことができます。このとき、進塁処理をどう書けるか考えてみましょう。

上の配列での実装例からも分かるように、進塁処理はより本塁に近い人から順に行いたいです。ということは、Setを使う場合は大きい順に取り出せる必要があり、SortedSet(実際に使う場合はTreeSet)を用いる必要があります。

一方、BitSetの場合にはpreviousSetBitを用いて大きい順に取り出すことが容易に可能です。一般に、BitSetはboolean型の配列をより多機能にしたものとして扱うことができるので、今回はこちらを使うことが無難です。

なお、C++などではbitsetのshiftを用いて進塁処理を纏めて行うことができますが、何故かJavaには用意されていないのでこれを使うことができません。筆者はshiftができる自作のBitSetを所有しており、このようにデータ構造を自作するのも一つの手かもしれませんね。

Javaの実装例

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)) {
      BitSet bitset = new BitSet(4);
      int N = sc.nextInt();
      int run = 0; // 得た得点
      while(N --> 0) {
        int A = sc.nextInt();
        bitset.set(0);
        for (int i = bitset.length(); (i = bitset.previousSetBit(i - 1)) >= 0; ) { // https://docs.oracle.com/javase/jp/8/docs/api/java/util/BitSet.html#previousSetBit-int- に、この書き方が推奨されている
          bitset.set(i, false);
          if (i + A < 4) bitset.set(i + A); // 進塁
          else ++ run;
        }
      }
      out.println(run);
    }
  }
}

Kotlinの実装例

import java.util.BitSet
import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val bases = BitSet(4) // KotlinにもBitSetがあるはずだけど、動かない……
    val N = sc.nextInt()
    var run = 0 // 得た得点
    repeat(N) {
      val A = sc.nextInt()
      bases[0] = true
      var i = bases.length()
      while(true) {
        i = bases.previousSetBit(i - 1)
        if (i == -1) break // BitSet.previousSetBitはtrueのbitが無いと-1を返す
        bases[i] = false
        if (i + A < 4) bases[i + A] = true // 進塁
        else ++ run
      }
    }
    println(run)
  }
}

この実装は、もう少し簡便にする方法があります。

まず、得点=N-塁に残っている人数、を利用すれば、変数runを用いずとも答えを求めることができます。

また、塁に居る人の集合は最初からdistinctなので、そもそもSetなど使わなくても良い形になっています。それなら、Listを使えば簡単に実装できそうです。

Javaの実装例

import java.util.ArrayList;
import java.util.stream.Collectors;
import java.util.List;
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)) {
      List<Integer> bases = new ArrayList<>(4);
      int N = sc.nextInt();
      for (int i = 0;i < N;++ i) {
        int A = sc.nextInt();
        bases.add(0);
        bases = bases.stream()
          .map(x -> x + A) // 進塁処理
          .filter(x -> x < 4) // 本塁に戻ってきた人を除去
          .collect(Collectors.toList());
      }
      out.println(N - bases.size()); // 塁に出ていない人=本塁に戻ってきた人=得点
    }
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    var bases = mutableListOf<Int>()
    val N = sc.nextInt()
    repeat(N) {
      val A = sc.nextInt()
      bases.add(0)
      bases = bases
        .map {it + A} // 進塁処理
        .filter {it < 4}
        .toMutableList() // 本塁に戻ってきた人を除去
    }
    println(N - bases.size) // 塁に出ていない人=本塁に戻ってきた人=得点
  }
}

方針2: 誰がどの場所に居るかを管理する

配列personを、各人が居る塁として管理します。

すると、 \(i=1,\ldots, N\) について次の処理を行うことでこの問題が解けることが分かります。

\(person_i\) を \(0\) で初期化する
\(j=1,\ldots, i\) について、 \(person_j\) に \(A_i\) を加える

これは、1がヒットを打った打者が塁に出ることを、2が進塁処理を表しています。そして、最終的に \(person_i \geq 4\) となった走者は本塁に戻ってきているので、そのスコアを数えれば良いです。

Javaの実装例

import java.util.Arrays;
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();
      int[] person = new int[N]; // Javaでは、int配列は0で初期化される
      for (int i = 0;i < N;++ i) {
        int A = sc.nextInt();
        for (int j = 0;j <= i;++ j) person[j] += A;
      }
      out.println(Arrays.stream(person).filter(i -> i >= 4).count());
    }
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val N = sc.nextInt()
    val person = IntArray(N) // Kotlinでは、int配列は0で初期化される
    for (i in 0 until N) {
      val A = sc.nextInt()
      for (j in 0..i) person[j] += A
    }
    println(person.filter {it >= 4}.count())
  }
}

この処理を眺めると、 \(person_i = \sum_{j=i}^{N} A_j\) であることが分かります。従って、 \(\sum_{j=i}^N A_j \geq 4\) となるような \(i\) の個数が分かれば良いです。これは \(i\) が大きい方から考えていくと、どこかで \(4\) 以上になるはずなので、その時の \(i\) が答えとなります。

また、\(\sum_{j=i}^{N} A_j\) という形は後ろから累積和を取る形となっているので、累積和を取りながら計算することで高速化できます。

Javaの実装例

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();
      int[] A = IntStream.rangeClosed(0, N).map(i -> i == 0 ? 4 : sc.nextInt()).toArray(); // 先頭に4という番兵を置いておくことで、実装が楽になる
      int cumsum = 0; // 後ろから累積和を取った値
      for (int i = N;i >= 0;-- i) {
        cumsum += A[i];
        if (cumsum >= 4) {
          out.println(i);
          return;
        }
      }
    }
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val N = sc.nextInt()
    val A = IntArray(N + 1) {if (it == 0) 4 else sc.nextInt()} // 先頭に4という番兵を置いておくことで、実装が楽になる
    var cumsum = 0 // 後ろから累積和を取った値
    for (i in N downTo 0) {
      cumsum += A[i]
      if (cumsum >= 4) {
        println(i)
        return
      }
    }
  }
}

余談

実際に野球ゲームを作ることを考えた場合、どの塁に人が居るか、という情報はかなり重要になってきます。

一方、競技プログラミングの文脈ではこれは不必要な情報で、これを削ることにより高速化できるのは競プロの面白いところでも不思議なところでもあるように感じます。

C問題 - Filling 3x3 array

まずは、素直に全探索をすることを考えます。

\(M = \min(h_1, h_2, h_3, w_1, w_2, w_3)\) として、 \(9\) マス全てに \(1\) 以上 \(M\) 以下の数を入れる方法は全部で \(O(M^9)\) 通りあります。これらについて、それぞれ条件を満たしているか判定すれば答えは求まります。

しかし、これでは \(M \leq 30\) であることから最悪 \(30^9 \approx1.9 \times 10^{13}\) 通りの盤面を試す必要があり、AtCoderでは秒間 \(10^8\) 回程度の計算が限度なことから実行時間制限に間に合わないです。

そこで、探索するマスを削減することを考えます。

盤面を \(A\) で表し、 \(A_{y, x}\) はマス \((x, y)\) に書かれている数字を表すこととします。このとき、例えば \(A_{1, 1} + A_{1, 2} + A_{1, 3} = h_1\) より、 \(A_{1, 3} = h_1 - A_{1, 1} - A_{1, 2}\) と表せるので、 \(A_{1, 1}\) 及び \(A_{1, 2}\) が決まっているならば \(A_{1, 3}\) を全探索する必要はないことが分かります。同様に考えていくと、 \(A_{1, 1}, A_{1, 2}, A_{2, 1}, A_{2, 2}\) が分かれば全てのマスの埋め方が定まることが分かります。

この計算量は \(O(M^4)\) で、 \(30^4 \approx 8.1 \times 10^5\) であることから実行時間制限に間に合うことが分かります。

なぜ \(4\) マスを決め打てば十分なのか？

この問題で与えられる形は、連立方程式になっています。

\( \left\{ \begin{array}{l} A_{1, 1} + A_{1, 2} + A_{1, 3} = h_1 \\ A_{2, 1} + A_{2, 2} + A_{2, 3} = h_2 \\ A_{3, 1} + A_{3, 2} + A_{3, 3} = h_3 \\ A_{1, 1} + A_{2, 1} + A_{3, 1} = w_1 \\ A_{1, 2} + A_{2, 2} + A_{3, 2} = w_2 \\ A_{1, 3} + A_{2, 3} + A_{3, 3} = w_3 \\ \end{array} \right. \)

連立方程式を解くために自由に埋めていい変数の個数を解の自由度と呼び、これは行列を用いて計算できます。まず、連立方程式を行列の形で表しましょう。

\( \begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} A_{1, 1} \\ A_{1, 2} \\ A_{1, 3} \\ A_{2, 1} \\ A_{2, 2} \\ A_{2, 3} \\ A_{3, 1} \\ A_{3, 2} \\ A_{3, 3} \\ \end{pmatrix} =\begin{pmatrix} h_1 \\ h_2 \\ h_3 \\ w_1 \\ w_2 \\ w_3 \\ \end{pmatrix} \)

そして、左側の行列(係数行列と呼びます)の階数を求めると、変数の個数-階数が解の自由度になります。実際に求めると、階数は \(5\) となり、 \(9-5=4\) 個の変数を決めれば一意に定まることが分かります。

実装ですが、まずは愚直にfor文を用いて探索を行う方法が考えられます。

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[] h = new int[3], w = new int[3];
      for (int y = 0;y < 3;++ y) h[y] = sc.nextInt();
      for (int x = 0;x < 3;++ x) w[x] = sc.nextInt();
      final int MAX = 30;
      int ans = 0;
      for (int a11 = 1;a11 <= MAX;++ a11) {
        for (int a12 = 1;a12 <= MAX;++ a12) {
          int a13 = h[0] - a11 - a12;
          if (a13 <= 0) continue;
          for (int a21 = 1;a21 <= MAX;++ a21) {
            int a31 = w[0] - a11 - a21;
            if (a31 <= 0) continue;
            for (int a22 = 1;a22 <= MAX;++ a22) {
              int a23 = h[1] - a21 - a22;
              if (a23 <= 0) continue;
              int a32 = w[1] - a12 - a22;
              if (a32 <= 0) continue;
              int a33 = h[2] - a31 - a32;
              if (a33 != w[2] - a13 - a23 || a33 <= 0) continue;
              ++ ans;
            }
          }
        }
      }
      out.println(ans);
    }
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val h = IntArray(3) {sc.nextInt()}
    val w = IntArray(3) {sc.nextInt()}
    val WRITE = 1..30 // 書き込む値の範囲
    var ans = 0
    for (a11 in WRITE) {
      for (a12 in WRITE) {
        val a13 = h[0] - a11 - a12
        if (a13 <= 0) continue
        for (a21 in WRITE) {
          val a31 = w[0] - a11 - a21
          if (a31 <= 0) continue
          for (a22 in WRITE) {
            val a23 = h[1] - a21 - a22
            if (a23 <= 0) continue
            val a32 = w[1] - a12 - a22
            if (a32 <= 0) continue
            val a33 = h[2] - a31 - a32
            if (a33 != w[2] - a13 - a23 || a33 <= 0) continue
            ++ ans
          }
        }
      }
    }
    println(ans)
  }
}

しかし、この方法ではネストが深くなるため実装が難しいです。そこで、再帰を用いた実装が考えられます。

再帰で実装する場合、処理は以下のようになります。

まず、関数 \(\mathrm{dfs}(x, y, A, h, w)\) を次のように定義します。

\(A_{1, 1}, A_{1, 2}, \ldots, A_{y, x}\) ( \(A_{y, x}\) を含まない) まで値を決め打ったとき、残りのマスを埋めてできる盤面であって条件を満たす書き込み方は何通りあるか？

このような関数が存在するとき、答えは \(\mathrm{dfs}(1, 1, A, h, w)\) と等しくなります。さて、 \(\mathrm{dfs}(x, y, A, h, w)\) について定義していきましょう。

\(1 \leq x, y \leq 2\) のとき、 \(A_{y, x}\) に \(1\) 以上 \(M\) 以下の値をそれぞれ決め打った時の \(\mathrm{dfs}(x + 1, y, A, h, w)\) の値の総和に等しい
\(x = 3\) かつ \(y \neq 3\) のとき、 \(A_{y, x} = h_y - A_{y, 1} - A_{y, 2}\) となる。この値が \(0\) 以下なら条件を満たさないので \(0\) 、そうでないなら \(\mathrm{dfs}(1, y + 1, A, h, w)\) の値に等しい
\(x \neq 3\) かつ \(y = 3\) のとき、 \(A_{y, x} = w_x - A_{1, x} - A_{2, x}\) となる。この値が \(0\) 以下なら条件を満たさないので \(0\) 、そうでないなら \(\mathrm{dfs}(x + 1, y, A, h, w)\) の値に等しい
\(x = 3\) かつ \(y = 3\) のとき、 \(A_{3, 3} = h_3 - A_{3, 1} - A_{3, 2} = w_3 - A_{1, 3} - A_{2, 3}\) となる。この等式が成り立ち、かつ値が \(0\) 以上ならこの盤面が条件を満たすので \(1\) 、そうでないなら \(0\) となる

この関数は \((x, y)\) が \((1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)\) と動いて最後に終了します。また、 \(1 \leq x, y \leq 2\) 以外では再帰が高々1回しか呼ばれないことから、計算量は \(O(M^4)\) です。

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[] h = new int[3], w = new int[3];
      for (int y = 0;y < 3;++ y) h[y] = sc.nextInt();
      for (int x = 0;x < 3;++ x) w[x] = sc.nextInt();
      int[][] a = new int[3][3];
      out.println(dfs(0, 0, a, w, h));
    }
  }
  
  public static int dfs(int x, int y, int[][] a, int[] w, int[] h) {
    if (y == h.length - 1) {
      a[y][x] = w[x] - a[0][x] - a[1][x];
      if (a[y][x] <= 0) return 0; // 書き込み方が条件を満たさなかった
      if (x == w.length - 1) {
        return a[y][x] == h[y] - a[y][0] - a[y][1] ? 1 : 0; // 最後の1マスまで書き込めた
      }
      return dfs(x + 1, y, a, w, h);
    }
    if (x == w.length - 1) {
      a[y][x] = h[y] - a[y][0] - a[y][1];
      if (a[y][x] <= 0) return 0; // 書き込み方が条件を満たさなかった
      return dfs(0, y + 1, a, w, h);
    }
    int ans = 0;
    for (int i = 1;i <= 30;++ i) { // 自由に書き込めるマス、全探索する
      a[y][x] = i;
      ans += dfs(x + 1, y, a, w, h);
    }
    return ans;
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val h = IntArray(3) {sc.nextInt()}
    val w = IntArray(3) {sc.nextInt()}
    println(dfs(0, 0, Array(3) {IntArray(3)}, w, h))
  }
}

fun dfs(x: Int, y: Int, a: Array<IntArray>, w: IntArray, h: IntArray): Int {
  if (y == h.size - 1) {
    a[y][x] = w[x] - a[0][x] - a[1][x]
    if (a[y][x] <= 0) return 0 // 書き込み方が条件を満たさなかった
    if (x == w.size - 1) {
      return if (a[y][x] == h[y] - a[y][0] - a[y][1]) 1 else 0 // 最後の1マスまで書き込めた
    }
    return dfs(x + 1, y, a, w, h)
  }
  if (x == w.size - 1) {
    a[y][x] = h[y] - a[y][0] - a[y][1]
    if (a[y][x] <= 0) return 0 // 書き込み方が条件を満たさなかった
    return dfs(0, y + 1, a, w, h)
  }
  return (1..30).map { // 自由に書き込めるマス、全探索する
    a[y][x] = it
    dfs(x + 1, y, a, w, h)
  }.sum()
}

この実装はもう少し工夫することができます。

まず、座標を一次元に潰してしまいます。すなわち、 \((x, y)\) を代わりに \(3x+y\) で表します。

また、 \(h\) 及び \(w\) の定義を変更し、まだ埋めていないマスの総和とします。これにより、 \(A\) を持たずに再帰をすることができます。

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[] h = new int[3], w = new int[3];
      for (int y = 0;y < 3;++ y) h[y] = sc.nextInt();
      for (int x = 0;x < 3;++ x) w[x] = sc.nextInt();
      out.println(dfs(0, w, h));
    }
  }
  
  public static int dfs(int p, int[] w, int[] h) {
    int x = p % 3, y = p / 3;
    if (y == h.length - 1) {
      if (w[x] <= 0) return 0; // 書き込み方が条件を満たさなかった
      if (x == w.length - 1) {
        return w[x] == h[y] ? 1 : 0; // 最後の1マスまで書き込めた
      }
      h[y] -= w[x];
      int ans = dfs(p + 1, w, h);
      h[y] += w[x];
      return ans;
    }
    if (x == w.length - 1) {
      if (h[y] <= 0) return 0; // 書き込み方が条件を満たさなかった
      w[x] -= h[y];
      int ans = dfs(p + 1, w, h);
      w[x] += h[y];
      return ans;
    }
    int ans = 0;
    for (int i = 1;i <= 30;++ i) { // 自由に書き込めるマス、全探索する
      w[x] -= i;
      h[y] -= i;
      ans += dfs(p + 1, w, h);
      w[x] += i;
      h[y] += i;
    }
    return ans;
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val h = IntArray(3) {sc.nextInt()}
    val w = IntArray(3) {sc.nextInt()}
    println(dfs(0, w, h))
  }
}

fun dfs(p: Int, w: IntArray, h: IntArray): Int {
  val x = p % 3
  val y = p / 3
  if (y == h.size - 1) {
    if (w[x] <= 0) return 0 // 書き込み方が条件を満たさなかった
    if (x == w.size - 1) {
      return if (w[x] == h[y]) 1 else 0 // 最後の1マスまで書き込めた
    }
    h[y] -= w[x]
    val ans = dfs(p + 1, w, h)
    h[y] += w[x]
    return ans
  }
  if (x == w.size - 1) {
    if (h[y] <= 0) return 0 // 書き込み方が条件を満たさなかった
    w[x] -= h[y]
    val ans = dfs(p + 1, w, h)
    w[x] += h[y]
    return ans
  }
  return (1..30).map { // 自由に書き込めるマス、全探索する
    w[x] -= it
    h[y] -= it
    val ans = dfs(p + 1, w, h)
    w[x] += it
    h[y] += it
    ans
  }.sum()
}

更に、数学的な考察をすることでより高速に答えを求めることができます。

TODO: これから書く

D問題 - Union of Interval

まず、公式解説にもあるように問題を言い換えておきましょう。「 \(N\) 人のユーザがいて、 \(i\) 番目のユーザは時刻 \(L_i\) にログインし、時刻 \(R_i\) にログアウトしました。 \(1\) 人以上がログインしていた時刻の区間を求めてください」

これを解く方法は二通りあります。

方針1: 区間に対して加算できるアルゴリズムを用いる

この問題は、区間加算アルゴリズムを用いると解くことができます。

\(T_i\) を、時刻 \(i\) においてログインしている人数と定めます。この時、次の操作ができれば答えを求めることができます。

\(T_{L_i}\) から \(T_{R_i - 1}\) に \(1\) を加算する
\(T_i\) の値を得る

簡単な方法としてはimos法があります。この場合の計算量は、 \(M=\max(R)\) として \(O(N + M)\) です。

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();
      final int MAX = 200000;
      int[] imos = new int[MAX + 2]; // imos[i]は時刻iにログインしている人数
      while(N --> 0) {
        int L = sc.nextInt(), R = sc.nextInt();
        ++ imos[L]; // imos法では右半開区間のindexを指定すること！
        -- imos[R];
      }
      final int NOBODY_IS_HERE = -1;
      int left = NOBODY_IS_HERE;
      for (int i = 0;i <= MAX;++ i) {
        if (left == NOBODY_IS_HERE && imos[i] != 0) left = i; // 区間の左側
        else if (left != NOBODY_IS_HERE && imos[i] == 0) { // 区間の右側
          out.println(left + " " + i);
          left = NOBODY_IS_HERE;
        }
        imos[i + 1] += imos[i]; // imos法は累積和を用いて加算を行う
      }
    }
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val N = sc.nextInt()
    val MAX = 200000
    val imos = IntArray(MAX + 2) // imos[i]は時刻iにログインしている人数
    repeat(N) {
      val L = sc.nextInt()
      val R = sc.nextInt()
      ++ imos[L] // imos法では右半開区間のindexを指定すること！
      -- imos[R]
    }
    val NOBODY_IS_HERE = -1
    var left = NOBODY_IS_HERE
    for (i in 0..MAX) {
      if (left == NOBODY_IS_HERE && imos[i] != 0) left = i // 区間の左側
      else if (left != NOBODY_IS_HERE && imos[i] == 0) { // 区間の右側
        println("${left} ${i}")
        left = NOBODY_IS_HERE
      }
      imos[i + 1] += imos[i] // imos法は累積和を用いて加算を行う
    }
  }
}

TODO: これから書く

posted:
last update: