問題
問題文
$1, \dots ,N$ の番号がついた $N$ 本の棒があります。棒 $i~(1 \le i \le N)$ の長さは $L_i$ です。
このうち、三角形を作ることのできるような長さの異なる $3$ 本の棒を選ぶ方法は何通りあるでしょうか。
つまり、$3$ つの整数 $1 \le i < j < k \le N$ の組であって次の $2$ つの条件の両方を満たすものの個数を求めてください。
・$L_i, L_j, L_k$ がすべて異なる
・$3$ 辺の長さが $L_i, L_j, L_k$ であるような三角形が存在する。
制約
・$1 \le N \le 100$
・$1 \le L_i \le 10^9$
・入力は全て整数である
収録されている問題セット
回答
回答1 (AC)
辺の長さを保持する配列を l(n) とするとき、変数 i, j, k を三重ループで回し、対応する l.at(i), l.at(j), l.at(k) がすべて異なることと、3 辺の長さが l.at(i), l.at(j), l.at(k) であるような三角形が存在することを確認し、存在する場合にはカウンタ triangle を増加する、という手順を繰り返せば良いでしょう。繰返し回数は $N(N-1)(N-2)/6=O(N^3)$ となります(理由は補足を参照下さい)が、$N$ は高々100なので、この方針で問題ないでしょう。
難しそうなのは三角形が存在することをどうやってチェックするかという部分ですが、これについては「$3$ 辺の長さが $a,b,c$ である三角形が存在するための条件は $a<b+c$, $b<c+a$, $c<a+b$ の全てが成立すること」が知られているので、これを使えば良いでしょう。コードは以下のようになりました。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> l(n);
for (int i=0; i<n; i++) {
cin >> l.at(i);
}
int triangle = 0;
for ( int i=0; i<n; i++ ) {
for ( int j=i+1; j<n; j++ ) {
if ( l.at(i)==l.at(j) ){
continue;
}
for ( int k=j+1; k<n; k++ ){
if ( l.at(i)==l.at(k) || l.at(j)==l.at(k) ){
continue;
}
if ( l.at(i)<l.at(j)+l.at(k) && l.at(j)<l.at(k)+l.at(i) && l.at(k)<l.at(i)+l.at(j) ) {
triangle += 1;
}
}
}
}
cout << triangle << endl;
}
補足：繰返し回数の見積もり
繰返し回数が $N(N-1)(N-2)/6$ 回になることを2種類のアプローチで説明します。
-
場合の数による説明：$1 \le i, j, k \le N$ から異なる $i,j,k$ を選ぶ選び方は $N(N-1)(N-2)$ 通りあります。このうち $i<j<k$ となる組み合わせは6つに1つなので、繰返し回数は $N(N-1)(N-2)/6$ 回となります (例えば $3,6,8$ を使った選び方は $(3,6,8)$, $(3,8,6)$, $(6,3,8)$, $(6,8,3)$, $(8,3,6)$, $(8,6,3)$ の6通りで、このうち $i<j<k$ となっているのは $(3,6,8)$ の1通りです)。
-
計算式による説明：数式を使うと、繰返し回数は $\sum_{i=1}^N \sum_{j=i+1}^N \sum_{k=j+1}^N 1$ となります。後は以下のようにひたすら計算することで結果を得ます。
$\sum_{i=1}^N \sum_{j=i+1}^N \sum_{k=j+1}^N 1$
$= \sum_{i=1}^N \sum_{j=i+1}^N (N-j)$
$= \sum_{i=1}^N [ (N-i-1)+(N-i-2)+ \cdots + 1 + 0 ]$
$= \sum_{i=1}^N \frac{(N-i-1)(N-i)}{2}$
$= \sum_{i=1}^N \frac{(i-N+1)(i-N)}{2}$
$= \sum_{i=1}^N \frac{i^2+(-2N+1)i+N(n-1)}{2}$
$= \frac{N(N+1)(2N+1)}{12} + \frac{(-2N+1)N(N+1)}{4} + \frac{N^2(N-1)}{2}$
$= \frac{N}{12}[(N+1)(2N+1)+3(-2N+1)(N+1)+6N(N-1) ]$
$= \frac{N}{12}[(N+1)(2N+1-6N+3)+6N(N-1) ]$
$= \frac{N}{12}[(N+1)(-4N+4)+6N(N-1) ]$
$= \frac{N(N-1)}{12}[ -4(N+1)+6N]$
$= \frac{N(N-1)(N-2)}{6}$
ここで $\sum_{i=1}^N 1 = N$, $\sum_{i=1}^N i = \frac{N(N+1)}{2}$,
$\sum_{i=1}^N i^2 = \frac{N(N+1)(2N+1)}{6}$ となることを利用しました。
調べたこと
AtCoder の解説 → 公式解説
回答と同じ方針でした。