drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ 三角形 三角形の成立条件 バチャやりました！ 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, … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2018%2F06%2F09%2F152500" title="2016 Benelux Algorithm Programming Contest L - Sticky Situation - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2018-06-09 15:25:00 rich https://drken1215.hatenablog.com/entry/2018/06/09/152500 1.0 100%