AtCoderログ：0107 - ABC 132 C

問題

問題文

高橋君は、$N$ 個の競技プログラミング用の問題をつくりました。それぞれの問題には $1$ から $N$ の番号がついており、問題 $i$ の難易度は整数 $d_i$ で表されます(大きいほど難しいです)。
高橋君はある整数 $K$ を決めることで、
・難易度が $K$ 以上ならば「ARC 用の問題」
・難易度が $K$ 未満ならば「ABC 用の問題」
という風に、これらの問題を二種類に分類しようとしています。
「ARC 用の問題」と「ABC 用の問題」が同じ数になるような整数 $K$ の選び方は何通りあるでしょうか。

制約

・$2 \le N \le 10^5$
・$N$ は偶数である。
・$1 \le d_i \le 10^5$
・入力は全て整数である。

収録されている問題セット

• AtCoder Problems Boot camp for beginners Easy 100 [#014]

回答

回答1 (AC)

難易度を配列に保存して昇順(小さい順)にソートした場合、$N/2-1$ 番目の要素は「ABC用の問題」のうち一案難しい問題の難易度、$N/2$ 番目の要素は「ARC用の問題」のうち一番易しい問題の難易度となるので、この間である整数 $K$ はすべて設問の条件を満たします。コードは以下のようになりました。

abc132c-1.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;

  vector<int> d(n);
  for ( int i=0; i<n; i++ ) {
    cin >> d.at(i);
  }
  
  sort( d.begin(), d.end() );
  
  int abcmax = d.at(n/2-1);
  int arcmin = d.at(n/2);
  
  cout << arcmin-abcmax << endl;
}

調べたこと

AtCoder の解説 → ユーザ解説

回答1と同じ方針でした。

AtCoder の解説 → コンテスト全体の解説

回答1と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0106 - ABC 161 C
• 次の記事 → AtCoderログ：0108 - ABC 142 C