読者です 読者をやめる 読者になる 読者になる

sataniC++

C++、競プロ、数学などについて色々考えたりします。

yukicoder No.21 平均の差

問題

問題のURLはこちらです。
No.21 平均の差 - yukicoder


考えたこと

グループの数K3以上であるため、「最大値と最小値の差」を求めれば良いですね。
グループの分け方としては、「最大値」「最小値」「余り」とします。

以下の図を見たら明らかですね。
(図中の赤い線は「入力n_i」、青い囲みは「グループ」、緑の点は「グループの平均値」を表しています)
f:id:satanic0258:20160406201308p:plain

最大値と最小値のみを使っているので、余りはどのようなグループ分けをしてもいいことがわかりますね。

また、このことから入力Kは使うことはありません。


コード(C++)

#85889 No.21 平均の差 - yukicoder

#include <iostream>
#include <algorithm>

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    int N, K, maxNum=1, minNum=1000;
    std::cin >> N >> K;
    for(int i=0; i<N; ++i){
        int input;
        std::cin >> input;
        maxNum = std::max(maxNum, input);
        minNum = std::min(minNum, input);
    }
    std::cout << maxNum-minNum << "\n";

    return 0;
}

コードの説明など

入力されたデータ全てに対して、std::maxやstd::minで最大値maxNumや最小値minNumを更新しているだけです。

なお、maxNumとminNumの初期値ですが、「最大値はデータが取りうる最小の値」、「最小値はデータが取りうる最大の値」としています。これによって最初のデータからどんどん最大値・最小値を更新していくことが出来ます。


備考

一度だけデータの数のループを回しているので、計算量はO(N)で済みます。


感想など

ぱっと問題を見ると「平均値だからグループの分け方による各平均値の値を求めて…」となりそうですが、よく考えてみると最大と最小の値しか使わないことがわかります。

しかし問題文では「小数点以下を切り上げ…」とあったり、サンプルでは最小値だけを使わなくても求める値が出ていたりと、問題の作者さんの工夫が見られます。

このような発想の転換をすると効率的に解くことが出来る問題というのも競プロの問題には結構多いと思うので、頭をやわらかくして考えることが大事です。
簡単なケースなどで考えてみたり、紙に書いてみたりするといいんじゃないでしょうか。