#1196857 (C++23(gcc16)) No.3780 Erase and Mex

• 問題: No.3780 Erase and Mex
• ユーザー: C
• 提出日時: 2026-11-04 14:23:57
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 12 ms / 2,000 ms
• コード長: 7,461 bytes
• コンパイル時間: 7,384 ms
• コンパイル使用メモリ: 391,320 KB
• 実行使用メモリ: 9,920 KB
• 最終ジャッジ日時: 2026-11-04 14:24:12
• 合計ジャッジ時間: 12,603 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 43

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/polygon/point_data.hpp>
#include <boost/polygon/voronoi.hpp>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
using namespace atcoder;
using ll=long long;
using ld=long double;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pll=pair<ll,ll>;
using pi=pair<int,int>;

// using mint=modint998244353;
using mint=modint1000000007;
// using mint2=static_modint<2>;

// using BoostPoint=boost::polygon::point_data<int>;
// using Voronoi=boost::polygon::voronoi_diagram<double>;

// using mint=LazyMontgomeryModInt<998244353>;
using vm=vector<mint>;
// using vvm=vector<vm>;

int main()
{
  	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	/**
	 * ならし計算量O(N)
	 *
	 * 1. MEX木
	 * x>=2 を MEX 操作で生成するには、少なくとも
	 * 0,1,...,x-1 がそれぞれ 1 個ずつ必要である
	 * この集合を x の「証明書」と呼ぶ
	 *
	 * 各数の生成過程を木で表すことを考える
	 * 葉は元の要素、内部頂点は MEX 操作に対応する
	 * MEX 操作は使用した要素を消費するので、異なる数の
	 * 生成木は互いに葉を共有しない
	 *
	 * また、任意の元の要素は、単独の MEX 操作を高々 2 回
	 * 行うことで 0 または 1 に変換できる
	 *
	 * 2. 最小コスト F(x) 
	 * c[i] を、元の数列における値 i の出現回数とする。
	 *
	 * 元の N 個の要素に加えて、値 B>N の要素を無限個
	 * 自由に利用できると仮定する。
	 *
	 * F(x) = {0,1,...,x-1} を構築するために必要な要素数の最小値 (2<=x<=N)
	 *
	 * 元の要素も追加した要素も、使用すればコスト 1 と数える
	 * 元の要素をすべて使用する必要はない
	 *
	 * 追加要素 B は 0,1 の生成には利用できるが、
	 * 2,...,x-1 を直接供給することはできない
	 * 一方、元から存在する i>=2 は i を直接供給できる
	 *
	 * 重要なのは、F(x) の定義には予算 N の制約がないことである
	 * したがって F(x)>N でも良い
	 *
	 * 元の問題との関係は　x が達成可能 <=> F(x)<=N　である
	 *
	 * 実際、F(x)<=N なら、追加要素の役割を未使用の元の要素で
	 * 代用できる。残った要素も 0 に変換して最後の MEX 操作に
	 * 含めれば、ちょうど 1 個の x を残せる
	 *
	 * 逆に、元の N 個だけで x を生成できたなら、
	 * 最後の操作に必要な証明書を取り出すことで
	 * コスト N 以下の構築が得られる
	 *
	 * 3. 上から貪欲で　F(x) を計算する（想定解と同じ）
	 * F(x) は O(x) 時間で計算できる。
	 *
	 * 初めは 0,...,x-1 がそれぞれ 1 個ずつ必要なので、
	 * d=1, u=0 として i=x-1,x-2,...,2 の順に処理する
	 *
	 * d = 各未処理の値に対する共通の需要
	 * u = 直接使用した元の要素数
	 *
	 * 値 i が d 個必要なとき、元の i を　g=min(d,c[i])　個だけ直接使用する
	 *
	 * 残りの d-g 個の i は MEX で生成する必要があり、
	 * それぞれが 0,...,i-1 を 1 個ずつ要求する
	 *
	 * よって　u+=g、d=2*d-g　と更新する
	 *
	 * 小さい値に対する需要は常にすべて等しいので、
	 * 変数 d 一つで管理できる
	 *
	 * この貪欲法が最適なのは、元の i を直接使用せずに
	 * i を生成している場合、その生成木を元の i 一つに
	 * 置き換えても損をしないからである
	 *
	 * 元の i が別の場所で 0,1 の生成に使われていた場合も、
	 * 取り除いた生成木の葉を代わりに使えば良い
	 *
	 * 最後には 0,1 がそれぞれ d 個必要なので、F(x)=u+2*d　を得る。
	 *
	 * 4. F(x) の増分
	 * x+1 の証明書は、x の証明書に x を一つ追加したものである
	 *
	 * F(x+1) を達成する最適な生成木の集合を考え、
	 * その中で x を生成する木の葉数を L とする
	 *
	 * この木を丸ごと取り除くと、残りは x の証明書になる
	 * 残った構築は元の要素の使用回数制約も満たすので、
	 * そのコストは少なくとも F(x) である
	 *
	 * よって　F(x+1)>=F(x)+L　(1)　が成り立つ。
	 *
	 * (i) c[x]>0 の場合
	 *
	 * L>=1 より、F(x+1)>=F(x)+1 である。
	 *
	 * 一方、元の x を一つ確保しておき、残りで x の証明書を
	 * 最小コスト F(x) で構築すればよい。
	 *
	 * なぜなら、x の証明書は x 自体を要求しないので、
	 * 元の x が使用されるとしても 0,1 の生成用だけであり、
	 * その役割は追加要素 B で代用できるからである。
	 *
	 * 確保した x を証明書に追加すればよいので、
	 * F(x+1)<=F(x)+1 も成り立つ
	 *
	 * したがって　F(x+1)-F(x)=1　(2)
	 *
	 * (ii) c[x]=0 の場合
	 *
	 * 元の x は存在せず、追加要素 B も x より大きい
	 * したがって、x を生成する木の根は必ず MEX 操作である
	 *
	 * この操作は 0,...,x-1 をそれぞれ少なくとも 1 個要求する
	 * よって根には少なくとも x 個の子があり、
	 * 各子は少なくとも 1 個の葉を持つ
	 *
	 * つまり L>=x であり、(1) より　F(x+1)-F(x)>=x　(3)　を得る。
	 *
	 * 以上より、次の重要な性質が成立する
	 *
	 * c[x]>0  => F(x+1)-F(x)=1
	 * c[x]=0  => F(x+1)-F(x)>=x
	 *
	 * この性質は F(x)<=N かどうかとは無関係に成立する
	 * 特に F(x) は狭義単調増加である。
	 *
	 * 5. アルゴリズム
	 * N>=2 なら 2 は必ず達成可能であり、答えは高々 N である
	 *
	 * F(2)=2 から始め、x=2,3,...,N-1 の順に F(x+1) を求める
	 *
	 * c[x]>0 なら、F を 1 増やすだけでよい。
	 * c[x]=0 なら、貪欲法で F(x+1) を最初から再計算する。
	 *
	 * F(x+1)>N となったら終了する。
	 * F は狭義単調増加なので、それ以降はすべて達成不可能である
	 *
	 * 6. ならし計算量 O(N)
	 * c[x]>0 の遷移は O(1) 時間であり、F(x+1)-F(x)=1
	 *
	 * 一方、c[x]=0 の遷移では O(x) 時間で再計算するが、F(x+1)-F(x)>=x　である
	 *
	 * したがって、いずれの場合も　遷移の計算量 = O(F(x+1)-F(x))
	 *
	 * ここで、F(x+1)<=N となる「成功した遷移」のみを考える
	 * 最後に成功した対象を y とすると、計算量の総和は
	 *
	 * O(sum_{x=2}^{y-1} (F(x+1)-F(x)))
	 * = O(F(y)-F(2))
	 * = O(N)
	 *
	 * となる。差分が望ましく打ち消し合うのがポイントである。
	 *
	 * 最後に F>N となる失敗した遷移は、O(N)ですが、高々 1 回しかない（すぐ終了するため）
	 */

	int T;
	cin>>T;
	while(T--){
		int N,a;
		cin>>N;

		if(N==1){
			cin>>a;
			cout<<max(1,a)<<'\n';
			continue;
		}

		vi c(N);
		rep(i,0,N){
			cin>>a;
			if(a<N)c[a]++;
		}

		int F=2,ans=2; //F=F(2)
		rep(x,2,N){
			//F(x+1)を計算する
			if(c[x]>0)F++;
			else{
				//再計算する
				int d=1,u=0;
				rrep(i,2,x+1){
					int g=min(d,c[i]);
					u+=g;
					d=2*d-g;
					if(u+2*d>N)break;
				}
				F=u+2*d;
			}
			if(F>N)break;
			else ans++;//狭義単調増加ので
		}

		cout<<ans<<'\n';
	}

}