時間通りには参加しませんでした。
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; }
まとめ
これは割とすんなり。