Lesson 8: MinPerimeterRectangle (Min Perimeter Rectangle)

Lesson 8: MinPerimeterRectangle
https://codility.com/programmers/lessons/8

一番簡単な答えは、aとbの値を全部チェックすることですね.　ただ a * b = Nなので、sqrt(N)以下のaにだけ関して調べて行けばいいということになります。

この方針で100%もらえてしまいます。

#include <math.h> int solution(int N)
{      int a;

    int sqrtN = sqrt(N);      int min = 2147483647; //the initial value for the min (INT_MAX).

    for (a = 1; a <= sqrtN; a++){          if (N % a == 0){
            int b = N / a;
            min = a + b < min ? a + b : min;
        }
    }
    
    return min * 2; }


しかし、この上のコードはあまり効率的ではありません。
sqrt(N)から１に向かって下って'a'をチェックして行き、最初にN% a == 0になった時の値で答えを計算して返すのがより良い方法です。（N / a = bですから(a * N / a) * 2を返せば良いですね）。

何故これで良いのか考えてみましょう。まず 1 <= x < y <= sqrt(N) というようなxとyの値を考えましょう。xとyはどちらも整数です。

もし、ここで下記のことが言えれば、yが大きい方がかならず外周が小さいと言えますね。


2 * (y + N / y) < 2 * (x + N / x)

式を一つずつ変形して行きましょう。

(y + N / y) < (x + N / x)

(y + N / y) - (x + N / x) < 0

(y - x) + (N / y - N / x) < 0

(y - x) < -(N / y - N / x)

(y - x) < -N / y + N / x

(y - x) < N / x - N / y

(y - x) < Ny - Nx / xy

(y - x) < N(y - x) / xy

1 < N / xy

ここで、1 <= x < y <= sqrt(N)なのですから、0 < xy < Nとなりますね。（yが最大値のsqrt(N)でもxはそれより小さいため、sqrt(N) * sqrt(N) = Nよりxyは小さくなりますね）

つまり上の1 < N / xyは成り立つことがわかります。最初の2 * (y + N / y) < 2 * (x + N / x)は正しいということですね。

ということは'a'の値を探す時に、sqrt(N)以下の大きい方から見ていって１に近づいて行き、最初のN % a == 0が見つかった時点で、一番小さい外周を返すaもbも確定したと考えてよいということになります。

これで１００％のスコアがもらえます。

#include <math.h> int solution(int N)
{      int a;
    int sqrtN = sqrt(N);

    for (a = sqrtN; a >= 1; a--){
        if (N % a == 0){
            break;
        }
    }

    return (a + N / a) * 2;
}