Triangle #PHP

前回、sortというジャンルと何の関係があるんだ？という疑問がありましたが、本問はまさに sort
の問題でした。

1st

Correctness	Performance	Task Score
100%	100%	100%

Triangle-1.php

function solution($A) {
    $ans = 0;
    $N = count($A);
    if($N < 3) { return 0; }

    rsort($A);

    for($i = 2; $i < $N; $i++) {
        if($A[$i-2] + $A[$i-1] > $A[$i]) {
            if($A[$i-1] + $A[$i] > $A[$i-2]) {
                if($A[$i] + $A[$i-2] > $A[$i-1]) {
                    $ans = 1;
                }
            }
        }
    }
    return $ans;
}

TestTriangle-1.php

use PHPUnit\Framework\TestCase;
include 'Triangle-1.php';

define('MAX_LENGTH', 10);

class TriangleTest extends TestCase {

    public function testExpectOne_1() {
        $array = array(10, 2, 5, 1, 8, 20);
        $ans = solution($array);
        $this->assertEquals(1, $ans);
    }

    public function testExpectOne_2() {
        $array = array(10, 5, 8);
        $ans = solution($array);
        $this->assertEquals(1, $ans);
    }

    public function testExpectZero_1() {
        $array = array(10, 50, 5, 1);
        $ans = solution($array);
        $this->assertEquals(0, $ans);
    }

    public function testExpectZero_2() {
        $array = array(10, 50);
        $ans = solution($array);
        $this->assertEquals(0, $ans);
    }

    public function testRandomArray() {
        $key = 0;
        $array = array();
        for($i = 0; $i < MAX_LENGTH; $i++) {
            $array[] = mt_rand();
        }
        // ランダムにマイナス化
        for($i = 0; $i < MAX_LENGTH; $i++, $key = mt_rand(0, MAX_LENGTH-1)) {
            $array[$key] = -($array[$key]);
        }
        $ans = solution($array);
        $this->assertEquals(0, $ans);
    }
}

本問で肝要なのは、いかに O(N * log(N)) の計算量で済ませるか。
単純に発想すれば、３重ループで解決できそうやけど、それでは O(N^3) なので、発想の転換が必要。

参考にしたのは、このサイト。答えの考え方が書いてあったから、これで答えが分かった。
辺 a, b, c があるとき、a + b > c, b + c > a, c + a > b をすべて満たすと三角形が成立する。
言い換えれば、ある３つの値が与えられたとき、その中の最大値が残りの２つの値の和より大きい場合、
三角形は成立し得ない。
例えば、10, 8, 20 という３つの値において、最大値である 20 は、残りの２つの値の和（10 + 8 = 18）
より大きい。これは、a + b > c を満たさない。ゆえに三角形は成立し得ない。

これを３つの値でなく、N個の値のときに適用する。
本問は、「三角形を成立させる３辺は存在するか？存在すれば１、しなければ０を返せ」
というだけで、「その３辺はどれか答えよ。」ではないので、成立条件を満たすか否かだけを
判定すればいいんです。（後者も簡単に実現できます。）

ゆえに、降順に並べ、先頭から３つの値について、成立条件を満たすかを順次判定するプログラムを
作成すれば良いわけです。

それが以下の部分です。

    rsort($A);

    for($i = 2; $i < $N; $i++) {
        if($A[$i-2] + $A[$i-1] > $A[$i]) {
            if($A[$i-1] + $A[$i] > $A[$i-2]) {
                if($A[$i] + $A[$i-2] > $A[$i-1]) {
                    $ans = 1;
                }
            }
        }
    }

rsort はキーを振り直すので、元のキーは保持されません。

こんな感じでした。

閑話休題ですが、今回、テストプログラムを充実させました。
大した改変ではないですが、テストごとの成否が分かるようにしました。
あと、testRandomArray() だけは、よく失敗します。作ってから気づいたのですが、
assertEquals(1, ...)なんてよく言えたもんだ、と思いますね。ランダム値なので、結果予測不能で、
これをテストするなんてナンセンス。