zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC175-B「Making Triangle」です。
ポイント
三角不等式を利用する問題です。三角形ABCの成立条件は，最大辺の長さを $c$ ，それ以外を $a$ ， $b$ とおけば，以下のようになります。
\begin{align}
c > a + b
\end{align}
c > a + b
\end{align}
こいつを全ての組み合わせに対して考えていけばOKです。全ての組み合わせの列挙の方法は，始めのインデックスを指定したfor文を利用しましょう。
また，最大限は数列をソートすることで，各組み合わせの一番最後の要素を指定すればOKです。「全ての辺の長さが異なる」という条件も見逃さないようにしましょう。
おさえるべき内容
三角不等式の利用
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;
int N;
ll L[110];
int main(){
cin >> N;
rep(i, N) cin >> L[i];
// 最大辺を指定するためのソート
sort(L, L+N);
int ans = 0;
// 全ての組み合わせを初めのインデックスを指定するfor文で列挙
rep(i, N-2){
repi(j, i+1, N-1){
repi(k, j+1, N){
// 「全ての辺の長さが異なる」＋「三角不等式」
if ((L[i]!=L[j]) && (L[j]!=L[k]) && (L[k] < L[i] + L[j])) ans++;
}
}
}
cout << ans << endl;
}
コメント