AtCoder ABC290 C問題 詳解

はじめに

問題
$数列Xに対しmを以下のように定める。$

• $Xは0 \leq x \lt m (m \in \mathbb{Z})を満たす全ての整数xを含む。$
• $Xはmを含まない。$

$このとき、A=A_{1}, \dots, A_{N} (0 \leq A_{i}), B=B_{1}, \dots, B_{K} (B_{i} \in A)におけるmの最大値を求めよ。$

問題の意味
$A$から$K$項を選んだ$B$に対して、$m$は$B$における$0$から始まる連続数列の項数を表します。
$A=7, 1, 2, 0, 5, 4$で$K=4$の場合、$m$の最大値は$B=0, 1, 2, \lbrace 4, 5, 7 \rbrace$における$3$となります。

詳解

総当たりの場合
計算量は$\mathcal{O}({}_N C_K)=\mathcal{O}(N!)$なのでTLEとなります。

アルゴリズム
$m$の最大値は$A$における連続数列の項数に一致するので、次のアルゴリズムが考えられます。

1. $A$に$i$が含まれないならば$m=i$として終了
2. $i=K-1$まで1を実行

計算量は$\mathcal{O}(N)$なのでTLEになりません。

Javaによる実装と動作例

実装

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in); 
        int N = s.nextInt();
        int K = s.nextInt();
        HashSet<Integer> A = new HashSet<>();
        int m = 0;
        for(int i = 0; i < N; i++) A.add(s.nextInt());
        for(; m < K; m++) if(!A.contains(m)) break;
        System.out.println(m);
    }
}

動作例

参照

• C - Max MEX