kmjp's blog

競技プログラミング参加記です

AtCoder ARC #101 : D - Median of Medians

時間通りには参加しませんでした。
https://beta.atcoder.jp/contests/arc101/tasks/arc101_b

問題

M要素の整数列B[1..M]の中央値は、Bを昇順に並べたときのfloor(M/2+1)番目の値と定義する。

ここでN要素の整数列A[1...N]が与えられる。
Aの部分列はN*(N+1)/2通りあるが、これらの中央値からなる数列を作ったとき、その中央値を求めよ。

解法

AtCoderでは以前もあったが、中央値に関する問題は二分探索で解くとよいことが多い。
二分探索で、「解がv以上になるかどうか」を判定するには、Aの中身をv未満なら0、v以上なら1としたとき、中央値が1になるかを判定すればよい。

この際、N*(N+1)/2通りのうち半数以上で中央値が1になればよいことがわかる。
括弧列に似た要領で、0/1のどちらが多いかはBIT等をつかえばO(NlogN)で数え上げることができる。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> bt;

int N;
int A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	int ret=-1;
	for(i=29;i>=0;i--) {
		int cand=ret+(1<<i);
		ZERO(bt.bit);
		int cur=101010;
		ll tot=0;
		bt.add(cur,1);
		FOR(x,N) {
			cur+=((A[x]>=cand)?1:-1);
			tot+=bt(cur);
			bt.add(cur,1);
		}
		if(tot>=1LL*N*(N+1)/2-tot) ret=cand;
	}
	cout<<ret<<endl;
	
}

まとめ

これは割とすんなり。