見出し画像

AtCoder Beginner Contest 175を見直す B - Making Triangle

B - Making Triangle

複数の棒の長さが数列で与えられるので、その棒を使って全ての辺の長さが異なる三角形が作れる組み合わせはいくつあるか答える問題

あたらめて見てもB問題にしては難しい気がする。

解説を見て作成した解答

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using vi = vector<int>;

int main() {
   int n; 
   cin >> n;
   vi l(n);
   rep(i, n) cin >> l.at(i);
   int ans = 0;
   rep(i, n)rep(j, n)rep(k, n) {
       if(i < j && j < k) {
           if(l.at(i) == l.at(j)) continue;
           if(l.at(j) == l.at(k)) continue;
           if(l.at(k) == l.at(i)) continue;
           if((ll)l.at(i) + l.at(j) + l.at(k) <= max({l.at(i), l.at(j), l.at(k)}) * 2) continue;
           ans++;
       }

   }
   cout << ans << endl;
}

ループで全パターン試します。
「f(i < j && j < k)」の条件は重複を防ぐために記載しています。

if(l.at(i) == l.at(j)) continue;
if(l.at(j) == l.at(k)) continue;
if(l.at(k) == l.at(i)) continue;

また、上記3つの条件は、全ての辺の長さが異なると言う条件に当てはまらない組み合わせを弾くために記載しています。

if((ll)l.at(i) + l.at(j) + l.at(k) <= max({l.at(i), l.at(j), l.at(k)}) * 2) continue;

上記の条件は、三角形が作成できない組み合わせを弾くために記載しています。
最も長い辺が他の2つの辺の合計以上の場合、三角形は作れないです。よって、ABCの三辺があったとしてAが一番長い場合は、以下条件が真となればOKです。

B+C <= A

ただ、これだとBやCが最も長い場合に別の条件式を記載しないといけないので、一つの式で済ませるためにまず、両辺にAを足します。

A+B+C <= A+A
A+B+C <= 2A

B、Cが最長の場合も合わせて記載します。

A+B+C <= 2A
A+B+C <= 2B
A+B+C <= 2C

左辺は共通なので、以下のように記載ができます。

A+B+C <= 2 * max(A, B, C)

更に、制約を見ると辺の最大の長さは10^9なので、3倍すると(int)の上限を超えてオーバーフローしてしまうため(long long)にキャストしています。

まぁ、できかなったから言うんですがやっぱムズイ。

この記事が気に入ったらサポートをしてみませんか?