C - Manga Editorial by cirno3153

問題を読み替えます。

\(i=1, 2, \ldots\) に対して、 \(i\) 巻目を持っている場合は \(1\) 冊、持っていない場合は \(2\) 冊を消費することで \(i\) 巻目を読める。 この時、最大で何巻まで読むことができるか？

これは、 \(i=1, 2, \ldots\) に対して上のシミュレーションを行い、必要な冊数が \(N\) を超えない最大の \(i\) を出力すれば良いです。 \(i\) 巻目を持っているか判定するためにTreeSetなどの平衡二分木を用いるなら \(O(N \log N)\) 、HashSetなどのハッシュテーブルを用いるならば \(\mathrm{expected} \ O(N)\) 、van Emde Boas Treeなどを用いるならば \(O(N \log \log \max a)\) です。

また、そもそも \(a_i \leq N\) を仮定して良い( \(N\) より大きい巻を持っていても読まない)ので、この範囲の配列を作ることで \(O(N)\) を達成できます。

C++の実装例

#include<iostream>
#include<vector>
using namespace std;
int main() {
  int N;
  cin >> N;
  vector<bool> set(N + 2);
  for (int i = 0;i < N;++ i) {
    int a;
    cin >> a;
    set[min(N + 1, a)] = true;
  }
  for (int read = 1;N >= 0;++ read) {
    N -= set[read] ? 1 : 2; // その巻を読むために使う本の冊数
    if (N < 0) cout << read - 1 << endl; // 本が無くなったら、無くなる直前の冊数を出力
  }
}

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();
      boolean[] a = new boolean[N + 2];
      for (int i = 0;i < N;++ i) a[Math.min(N + 1, sc.nextInt())] = true;
      for (int read = 1;N >= 0;++ read) {
        N -= a[read] ? 1 : 2; // その巻を読むために使う本の冊数
        if (N < 0) out.println(read - 1); // 本が無くなったら、無くなる直前の冊数を出力
      }
    }
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    var N = sc.nextInt()
    val a = BooleanArray(N + 2)
    repeat(N) {a[Math.min(N + 1, sc.nextInt())] = true}
    var read = 0
    while(N >= 0) N -= if (a[++ read]) 1 else 2 // その巻を読むために使う本の冊数
    println(read - 1) // 本が無くなったら、無くなる直前の冊数を出力
  }
}

Pythonの実装例

N = int(input())
a = [False] * (N + 2)
for i in map(int, input().split()): a[min(N + 1, i)] = True
read = 0
while N >= 0:
  read += 1
  N -= 1 if a[read] else 2 # その巻を読むために使う本の冊数
print(read - 1) # 本が無くなったら、無くなる直前の冊数を出力

posted:
last update: