けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

2016 Benelux Algorithm Programming Contest L - Sticky Situation (AtCoder 300 点くらい)

バチャやりました!

vjudge.net

L 問題ですが、一番易しい問題です。

問題へのリンク

問題概要

N 個の値 a_1, a_2, ..., a_N が与えられる。 このうちの 3 つをうまく選ぶことで、3 辺の長さがそれらになるような三角形を作ることができるかどうか判定せよ。

制約

  • 3 <= N <= 20000

解法

三角形の成立条件は a < b < c に対して、c < a+b で与えられる。

素朴に考えると O(N3) の探索をすることになるが、O(NlogN) でできる。まずはソートしておく。そして c を決めうちする

c の値を仮定すると、a < b < c なる a, b のうち a+b が最も大きくなるものが c を超えるかどうかを判定すればよい。そのような a, b は c 以下のうち大きい順に 2 つとればよい。

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

int N;
vector<long long> val;

int main() {
    while (cin >> N) {
        val.resize(N);
        for (int i = 0; i < N; ++i) cin >> val[i];
        sort(val.begin(), val.end());
        bool ok = false;
        for (int i = 0; i < N-2; ++i) {
            if (val[i + 2] < val[i] + val[i+1]) ok = true;
        }
        if (ok) cout << "possible" << endl;
        else cout << "impossible" << endl;
    }
}