SRM 166 DIV2 Level One - 三角形の組合せ

ようやくまともな問題。ま、一番簡単なラインを進んでるから当然か。

工場で働いてるんだけど、毎日毎日金属のスクラップが出るので、そいつを利用して三角形のピクチャーフレームを作りたいと思ってる(センスねぇな)

金属片の長さが与えられるので、三角形のピクチャーフレームを作ることが可能な組合せの数を求めると。

{1,2,3,4,5}なら、{2, 3, 4},{2, 4, 5},{3, 4, 5}の3つの組合せが可能。1 + 2 = 3なので、三角形にはならない。1 + 2 < 4なら4は長すぎ、どう考えても届かない。

組合せがでてきた。

#include <vector>
#include <algorithm>
using namespace std;

class Workshop
{
public:
    static int pictureFrames(vector<int> pieces)
    {
        int count = 0;

        if (pieces.size() < 3)
            return 0;

        sort(pieces.begin(), pieces.end());

        for (int i = 0; i < pieces.size() - 2; i++)
            for (int j = i + 1; j < pieces.size() - 1; j++)
                for (int k = j + 1; k < pieces.size(); k++)
                    if(pieces[k] < pieces[i] + pieces[j])
                        count++;
                    else
                        break;

        return count;
    }
};

全体の組合せの数は、nC3個。結構な量なので、速度改善を入れてみた。

あらかじめソートしておけば、1 2 3が来た時点で、1 2 4という組合せはありえないということがわかるので処理をすっ飛ばして、次のフェーズに行く事ができる。

あらかじめソートしておけば、一番長い辺を探す必要も無い。

ソートって素敵過ぎる。