AtCoder Beginner Contest 175 B問題「Making Triangle」解説(C++,Python3,Java)

Ruteです。

AtCoder Beginner Contest 175 B問題「Making Triangle」の解説を行います。

問題URL:
https://atcoder.jp/contests/abc175/tasks/abc175_b

問題概要

$N$本の棒のうち、三角形を作ることのできるような長さの異なる$3$本の棒を選ぶ方法は何通りあるかを求めよ。

制約

・$1 \leq N \leq 100$
・$1 \leq L_i \leq 10^9$
・入力は全て整数

解法

ans = 0と初期化しておきます。
以下の様な繰返し処理を実装すれば良いです。
・以下の繰返し処理を$(0,n)$の範囲で行う(カウンタ変数を$i$とする)
　・以下の繰返し処理を$(i+1,n)$の範囲で行う(カウンタ変数を$j$とする)
　　・以下の繰返し処理を$(j+1,n)$の範囲で行う(カウンタ変数を$k$とする)
　　　L[i] == L[j]である or L[i] == L[k]である or L[j] == L[k]であるを満たしているかを判定する。
　　　・満たしていない場合(長さが異なる条件を満たしている)
　　　　　以下の式が成り立つかを判定し、成り立つ場合はansに1を加算する。

L[i]+L[j] > L[k] \space and \space L[j]+L[k] > L[i] \space and \space L[i]+L[k] > L[j] 

ansが求める組み合わせの数なので、これを出力すれば良いです。

計算量は$O(N^3)$で、制約上では間に合います。
以下、Python3,C++,Javaでの解答例を示します。

各言語解答例

Python3での解答例

ABC175B.py

N = int(input())
L = list(map(int,input().split()))
ans = 0
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if L[i] == L[j] or L[j] == L[k] or L[i] == L[k]:
                continue
            else:
                if L[i]+L[j] > L[k] and L[j]+L[k] > L[i] and L[k]+L[i] > L[j]:
                    ans += 1
print(ans)

C++での解答例

ABC175B.cpp

#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<long long> L(n);
  for (int i = 0; i < n; i++){
    int l;
    cin >> l;
    L.at(i) = l;
  int ans = 0;
  for (int i = 0; i < n; i++){
    for (int j = i+1; j < n; j++){
      for (int k = j+1; k < n; k++){
        if (L.at(i) == L.at(j) || L.at(i) == L.at(k) || L.at(j) == L.at(k)){
          continue;
        }else{
          if (L.at(i)+L.at(j) > L.at(k) && L.at(j)+L.at(k) > L.at(i) && L.at(i)+L.at(k) > L.at(j){
            ans++;
          }
        }
      }
    }
  }
  cout << ans << endl;
}

Javaでの解答例

ABC175B.cpp

import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    long L[]; L = new long[n];
    for (int i = 0; i < n; i++){
      long l = scan.nextLong();
      L[i] = l;
    }
    int ans = 0;
    for (int i = 0; i < n; i++){
      for (int j = i+1; j < n; j++){
        for (int k = j+1; k < n; k++){
          if (L[i] == L[j] || L[i] == L[k] || L[j] == L[k]){
            continue;
          }else{
            if (L[i]+L[j] > L[k] && L[i]+L[k] > L[j] && L[j]+L[k] > L[i]){
              ans++;
            }
          }
        }
      }
    }
    System.out.println(ans);
  }
}