【競プロ AtCoder問題解説】C – Divide the Problems
コーディング力の強化は、エンジニアにとって不可欠なことです。スポーツ選手でいうところの、基礎体力みたいなものだとおもっています。AtCoder Beginner's Contestの問題からいくつか解説紹介していきます。
問題
AtCoder Beginner Contest 132のC問題
高橋君は、 N 個の競技プログラミング用の問題をつくりました。 それぞれの問題には 1から Nの番号がついており、問題
i の難易度は整数 diで表されます(大きいほど難しいです)。
高橋君はある整数 Kを決めることで、
難易度が K以上ならば「 ARC用の問題」
難易度が K 未満ならば「 ABC用の問題」
という風に、これらの問題を二種類に分類しようとしています。
「ARC用の問題」と「ABC用の問題」が同じ数になるような整数 Kの選び方は何通りあるでしょうか。
制約
2≦N≦10^5
Nは偶数である。
1≦di≦10^5
入力は全て整数である。
解説
競技ブログラミングがなぜ「競技」と言われるのかというと、それは問題に対して時間制限があるからです。たとえ、アルゴリズムが正しいとしても、設定された制限時間内に解くことができなければ、エラーとなってしまいます。
なので競技プログラミングの問題を解く際には、制約を意識してみましょう。
この問題の場合には、
2≦N≦10^5
Nは偶数である。
1≦di≦10^5
入力は全て整数である。
という制約があります。
ひとつの目安として、その問題がO(N)、つまり、たとえばfor文でN回の繰り返し処理を行う場合で10^8(=1億)回の繰り返しを越えてしまう場合には、制限時間オーバーとなってしまうというイメージを持っておきましょう。
その場合には、たとえアルゴリズムが正しく、答えが正しかったとしても他の方法でないと正解として受理されません。
ですので、この問題の場合には、もしも、Nとdiを範囲とする二重ループを書いてしまうと10^10のオーダーとなり、10^8を越えます。つまり、ほかのアルゴリズムを考える必要があるというわけです。
というわけでまず、回答のコードです
#include
#include
#define NUM 100000
#define LL long long
using namespace std;
int main()
{
LL i, pos, j, m, buf, n, first_max, second_min, K, N, d[NUM];
scanf("%lld", &N);
//標準入力からそれぞれの問題の難易度を読み込む
for (i = 0; i < N; i++)
{
scanf("%lld", &d[i]);
}
//問題を難易度順に並び替える
sort(d, d + N);
//問題をふたつにわける分ける配列番号の設定
first_max = N / 2 - 1;
second_min = N / 2;
//Kの初期化
K = 0;
//条件を満たすKの値を求める
for (n = d[first_max] + 1; n ＜= d[second_min]; n++)
{
K++;
}
//結果の表示
printf("%lld\n", K);
return 0;
}
問題文を読んでみましょう。
「難易度が K以上ならば「 ARC用の問題」
難易度が K 未満ならば「 ABC用の問題」
という風に、これらの問題を二種類に分類しようとしています。」
ここまで読んだ段階で、問題をふたつに分類したいということがわかります。さらに、
「「ARC用の問題」と「ABC用の問題」が同じ数になるような整数 Kの選び方は何通りあるでしょうか。」
問題をふたつに分類したいかつ、同じ数で分類したいということがわかります。
なので、やるべきことは、
同じ数にふたつにわける ＝ 半分こ
ということになります。
では半分こに分けてみましょう。問題の数はＮ個なので、配列番号のＮ／２を指定すれば半分にわけられます。つまり、配列の番号でいうと、０～Ｎ／２までとＮ／２＋１～Ｎ－１までのふたつにわけることができたということになります。
ふたたび問題文に戻ってみましょう。
「難易度が K以上ならば「 ARC用の問題」
難易度が K 未満ならば「 ABC用の問題」
という風に、これらの問題を二種類に分類しようとしています。
「ARC用の問題」と「ABC用の問題」が同じ数になるような整数 Kの選び方は何通りあるでしょうか。」
難易度の大きさで分類しているので、問題の配列dは難易度の順番で並び替えておきましょう。
これで、配列番号にN/2とN/2+1を指定してやると問題文の設定状況「ARC用の問題」と「ABC用の問題」のふたつに問題を分けることができます。
つまり、難易度がd[N/2]までならABCの問題、難易度がd[N/2+1]以上ならばARCの問題という状況です。
あとはこのように分割するKの個数を数えるだけです。