Lesson 3: MinAvgTwoSlice (Min Avg Two Slice)

https://codility.com/programmers/lessons/3
Lesson 3: MinAvgTwoSliceの解答がこちらになります。

基本、数学の問題だそうです。

Codilityの例題PDFにかかれたprefix sumのアルゴリズムの工夫だけでとけるのかな？と思って、ずっと考えてたのですがどうやら違いそうだという事でググってしまいました。

とりあえず下に色々みてわかった簡単な説明を。

まず、一番小さい平均を出す連続した配列のスロットは２つか３つのスロットを見ればわかるということです。

例えば、４つの大きさの連続した配列のスロットが一番小さい平均を出すと仮定してみましょう。これは２＋２の二つに分割できますよね。そうすると、前者か後者の２の平均がもし、全体の４つの平均より小さかった場合、仮定に反しますね。もし、大きかったらどうなるでしょう？もう一方のペアのほうの平均がもとの４つの平均より小さくなりますね。だから、２＋２に分割しても同じなのです。これは例えば５つのスロットを２＋３に分解しても同じ事です。

もっと一般化できますよね。適当なサイズの連続した配列のスロット中の値の平均が一番小さいと仮定した場合、先頭部分から２つか３つのペアをとってそれより小さいものが出来ると、最初の仮定に違反します。どちらにしろ、同じ平均を出せる部分が切り出せるということになりますから、２つか３つの平均だけを先頭から見て言って、一番小さいもので最初に現れた部分のインデックスを返せば良いという事です

これで１００％とれました。

int solution(int A[], int N) 
{
    int i = 0;
    
    if (N == 2){
        return 0;
    }

    //initialize the current minimum average of the first two slots.
    double minavg = (A[0] + A[1]) / 2.0;
    int idx = 0;
    

    for (i = 2; i < N; i++){
        double tmp1 = (A[i - 1] + A[i]) / 2.0;
        double tmp2 = (A[i - 2] + A[i - 1] + A[i]) / 3.0;
        
        if (tmp1 < minavg){
            idx = i - 1;
            minavg = tmp1;
        }
        if (tmp2 < minavg){
            idx = i - 2;
            minavg = tmp2;
        }
    }
    return idx;
}