ABC094 C - Many Medians (300点)

問題概要

問題のリンク

$N$ 個の数 $X_1,X_2,...,X_N$ が与えられる。($N$ は偶数。)

ここで、$i=1,2,...,N$ に対して，$X_1,X_2,...,X_N$ から $X_i$ のみを除いたもの、すなわち $X_1,X_2,...,X_{i−1},X_{i+1},...,X_N$ の中央値を $B_i$ とする。$i=1,2,...,N$ に対して，$B_i$ を求めよ。

制約条件

• $2≤N≤200000$
• $N$ は偶数
• $1≤X_i≤10^9$
• 入力はすべて整数

考えたこと

まず配列$X$から$X_i$を除いた配列を作って中央値を求めるという方法が思いつくが、この時C#だと Remove メソッドの計算量は$O(N)$となるので、全ての$X$に対して上の処理をすると$O(N^2)$となるのでTLEする。
よって$O(N)$以下に計算量を収めたい。

偶数個の要素($N$)をもつ配列$X$から$X_i$、つまり1つの要素を除いた配列の中央値を求めるので、中央値は$X_{n/2-1}$か$X_{n/2}$のどちらかとなる。
以下の入力例1での場合を見てみるとわかりやすい。

よって、$X_i$が$X_{n/2-1}$より左側、すなわち$X_{n/2-1}$以下の場合は$X_{n/2}$が答えとなり、$X_{n/2}$より右側、すなわち$X_{n/2}$以上の場合は$X_{n/2-1}$が答えとなる。

この時計算量は$O(N)$となる。

解答

c.cs

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args) {
        int n = int.Parse(Console.ReadLine());
        List<int> x = Console.ReadLine().Split().Select(int.Parse).ToList();
        List<int> l = new List<int>(x);
        l.Sort();
        for(int i = 0; i < n; i ++) {
            Console.WriteLine(solve(n,l,x[i]));
        }
    }
    static int solve(int n, List<int> l, int x) {
        int ans = 0;
        if(x <= l[n/2-1]) ans = l[n/2];
        if(x >= l[n/2]) ans = l[n/2-1];
        return ans;
    }
}