0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

高橋君は、 N 個の競技プログラミング用の問題をつくりました。それぞれの問題には 1 から N の番号がついており、問題 i の難易度は整数 d i で表されます(大きいほど難しいです)。

高橋君はある整数 K を決めることで、

難易度が K 以上ならば「 A R C 用の問題」難易度が K 未満ならば「 A B C 用の問題」という風に、これらの問題を二種類に分類しようとしています。

「 A R C 用の問題」と「 A B C 用の問題」が同じ数になるような整数 K の選び方は何通りあるでしょうか。

2.制約

2 ≦ N ≦ 10⁵
N は偶数である。
1 ≦ d i ≦ 10⁵
入力は全て整数である。

3.入力例

入力

14
99592 10342 29105 78532 83018 11639 92015 77204 30914 21912 34519 80835 100000 1

出力

4.初見の感想

Kの取り方は「ABC問題の最大値＜K≦ARC用問題の最小値」という条件で表せる

→つまり「ARC用問題の最小値ーABC問題の最大値」でKのとりうる数がわかる

とりあえずソートは必要
ABC問題の最大値はN/2-1番目の配列、ARCの最小値はN/2番目の配列に格納されている

5.コードと簡単な解説

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

class Program
{
    static void Main(string[] args)
    {
　　//入力
        int N = int.Parse(Console.ReadLine());
        string[] input = Console.ReadLine().Split();
        int[] list = new int[N];
        for(int i = 0; i < N; i++)
        {
            list[i] = int.Parse(input[i]);
        }
        //ソート
        Array.Sort(list);
　　//計算&出力
        Console.WriteLine(list[N / 2] - list[N / 2 - 1]);
    }
}

6.最後に

今回はC問題が簡単だったみたいですね～

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

AtCoder Beginner Contest 132 C - Divide the Problems