AtCoder Beginner Contest 143 D - 今日から始める競プロ日記
はじめに
AtCoder Beginner Contest 143（ABC143）に参加。
今回はDまで解いて4完。
D問題の想定解ではO(N^2 logN)で解けるらしいのだけど、
O(N^3)で解けてしまったので、
解説動画を見ながら想定解の方も自分なりにまとめてみる。
D - Triangles
- 棒がN本
- i番目の棒の長さはLi
- ここから三本選んで三角形を作る
- 何種類の三角形が作れるか
制約
3 <= N <= 2*10^3 1 <= Li <= 10^3
コンテスト中に解いた方針
蟻本の三角形の問題で（p. 21）、 三角形の条件は「最も長い棒の長さ > 他の2本の棒の長さの和」とあった。
なので棒の長さでソートして、 一番長い棒、二番目に長い棒、それ以外の棒と分かった状態で判定していけば計算がちょっと少なく済みそうだなと思った。
あと、三本目を選ぶときに長い棒から選んでいるのである棒で三角形が作れないことが分かったら、 それより短い棒でも三角形が作れないからそこで止めても良さそうだなと思った（枝刈りみたいな感じ）。
コンテスト中に書いたコード（ちょっといじった）
897ms
#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[i];
// 棒の高さをソート
sort(L.begin(), L.end());
// 組み合わせの個数をカウント
long long cnt = 0;
// L[i] : 候補の中で一番長い棒
for(int i = N-1; i >= 2; i--)
{
// L[j] : 候補の中で二番に長い棒
for(int j = i-1; j >= 1; j--)
{
// L[k] : それ以外の棒
for(int k = j-1; k >= 0; k--)
{
// 条件を満たすか判定
if(L[i] < L[j]+L[k]) cnt++;
else break; // ダメだったらそれより短いものもダメだからbreak
}
}
}
// 解を出力
cout << cnt << endl;
return 0;
}
想定解の方針
公式の解説動画を見ながらまとめてみる。
まず三角形の条件をまとめる
- 三本の棒の長さを a < b < c とする
- このとき、a + b > c となるように選択
この条件を満たすように効率よく棒を探索すればよい。
- 棒を長さでソート
- aとbをfor文で回す（ただし、a < b）
- そのときに a + b > c を満たす棒の範囲の端を二分探索で見つける
解説動画を参考に書いたコード
#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[i];
// ソート
sort(L.begin(), L.end());
// 組み合わせをカウント
int cnt = 0;
// aとbの棒をfor文二重で回す
// 条件 : a < b < c and a + b > c
for(int b = 0; b < N; b++)
{
for(int a = 0; a < b; a++)
{
// 二つの棒の長さの和
int ab = L[a] + L[b];
// 二分探索で条件を満たす三本目のグループの右端+1を見つける
// （イテレータとイテレータの差をとって何番目か求めている）
int r = lower_bound(L.begin(), L.end(), ab) - L.begin();
// 左端
int l = b+1;
// カウント
cnt += max(0, r-l);
}
}
// 解を出力
cout << cnt << endl;
return 0;
}
おわりに
今回はたまたまコンテスト中に解けたからよかったけど、 本来なら解けなかったかもしれない問題なのでしっかり覚えておきたい。
