Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What are the problem?
@RoadLynton

AtCoderログ:0043 - ABC 175 B

問題

問題文

$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$ の全てが成立すること」が知られているので、これを使えば良いでしょう。コードは以下のようになりました。

abc175b-1.cpp
#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 の解説公式解説

回答と同じ方針でした。

リンク

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
0
Help us understand the problem. What are the problem?