ABC 107 D Median of Medians
おもしろい問題だったので、けっこう悩んだが解けず。
まず、数列$ a_n (1 \le n \le N)のうち連続した部分列を$ a_{lr} (1 \le l \le r \le N)で表すとする。このとき、$ a_{lr}の中央値をすべて調べて、その中央値を求めればいいので、中央値を求めるコストが$ O(N)とすればナイーブにやると$ O(N^3 + N^2)となって、とても間に合わなくなる
中央値といえば二分探索なので、適当な値$ mを決めて、それよりも中央値が大きい部分列と小さい部分列の数を数える方向で考えてみる。$ a_{lr}のうち中央値が$ m以上の部分列、つまり、$ a_{lr}の過半数の要素が$ m以上となる、そんな部分列の個数を$ M_mとする。この$ M_mが$ O (N)で求まれば、あとは二分探索で$ O(N \log N)で答えが求まり間に合いそうである。なお、最初に$ a_nをソートし、それに対して二分探索を行うことになる。 と、ここまではいいが、そもそも$ M_mが$ O(N)で求まるかという問題がある。$ a_{lr}をすべて列挙すると$ O(N^2)になるので、てんでダメ。$ a_{lr}のうち$ m以上の要素の数をうまい具合にしゃくとり法で求められないかと思ったけれど、たとえば右端を1進めて新たに$ a_kを対象に含めたときに$ a_{lr}のうちどこまでを左端にできるかはっきりしない。というか対象の部分列も条件を満たす保証がないのでダメである。 ここからは解説の受け売り。$ a_{lr}のうち「中央値が$ m以上の部分列」ということは「$ m以上の要素数が過半数」、つまり「$ m以上の要素の数$ \ge$ m未満の要素の数」が成立する部分列ということになる。したがって、$ a_nの要素を$ m以上なら$ 1、$ m未満なら$ -1で置き換えたとすると、「総和が0以上」が成立する部分列を数え上げればよい。
「総和」「$ k以上」と聞くと、またしゃくとり法が使えるのではないかと一瞬思うが、そもそも負の値が入っているのでダメ。部分和の最大値を求めるわけではないし、と悩むところだが、累積和を$ S_kとすれば、$ a_{lr}のうち部分列の総和が$ 0以上の部分列の数は、すなわち$ S_i \lt S_j (l \le i \le j \le r)の数に等しくなるので、転倒数を数えるのと同じ手法が使える。 以下はマージソートを使って数えたもの。
code:java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
for (int i = 0; i < N; i++) {
}
int[] sorted = Arrays.copyOf(a, a.length);
Arrays.sort(sorted);
long target = N;
target = (target * (N + 1) / 2 + 1) / 2;
int left = -1, right = N;
while (right - left > 1) {
int mid = (left + right) / 2;
long count = numSubarraysWhooseMedianBiggerThan(a, sortedmid); if (target <= count) {
left = mid;
} else {
right = mid;
}
}
System.out.println(sortedleft); }
private static long numSubarraysWhooseMedianBiggerThan(int[] a, int t) {
int sum = 0;
for (int i = 0; i < a.length; i++) {
}
long n = a.length;
return n * (n + 1) / 2 - countInversion(b, 0, b.length);
}
private static long countInversion(int[] a, int left, int right) {
if (left + 1 >= right) return 0;
int mid = (left + right) / 2;
long count = countInversion(a, left, mid) + countInversion(a, mid, right);
int i = 0;
int li = left;
int ri = mid;
while (li < mid && ri < right) {
} else {
count += mid - li;
}
}
System.arraycopy(b, 0, a, left, b.length);
return count;
}
}