AtCoder Beginner Contest 143 - D - Triangles
https://gyazo.com/eacda4025e9ecff90b432a6c7488ae3a
計算量を落とす系, upper_boundとlower_boundの扱いに注意
考えたこと
Nの最大が$ 10^3 なので、全ての組み合わせを見ようとすると $ 10^9で間に合わない
3つのうち2つを固定して、残り1つを求めるのを計算量落とせないか(2分探索とかでいけないか? )
a, b, c のうち b,cを固定して、aを求めてみる
条件から a < b + c がわかる、これでLの配列をソートして二分探索してあげれば、aは求めれる
... がこれだけではダメで、例えば b = 10, c = 30としたら、 aは40より小さい数全ておkかと言われるとそうでなくて, a = 1だと 30 < 10 + 1 となり満たさなくなる
ある値よりは大きくないといけないことがわかる. 残りの条件を式分解してみる
b < a + c -> b - c < a
c < a + b -> c - b < a
さらにこれをまとめると b, cのうち、大きい方から小さい方の数を引いた数より大きいことがaの条件だとわかる
仮にb > c だとして、 b-c > c-bをみたすので, b-cだけ考えればいい
OK, これでb,cを固定した場合のaの範囲がわかった、あとはこれでb, cの組み合わせ全てに対して行えばいい
計算量は$ N^2logNとなる
提出したコード
code: D.cpp
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) #define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i) #define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i) #define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i) template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
int main() {
int n; cin >> n;
vector<int> l(n);
sort(l.begin(), l.end());
ll ans = 0;
// a < b + c で b,cを固定してaを求める
rep(i, n-1) for(int j=i+1; j < n; j++) {
// 式変形をして
// b < a + c -> b - c < a ,,, c < a + b -> c - b < a
// 2つあるけど、まとめると、 b,cのうち大きい方から小さい方を引いたときの数より大きいことがaの条件
// これで2つの条件が出来た
// a < b + c を求める , lower_boundで "以上" を求めた後に、-1すれば "より小さい" になる
auto right_idx = lower_bound(l.begin(), l.end(), li+lj); // a > c - b を求める , これは普通にupper_boundで "より大きい" を求める
auto left_idx = upper_bound(l.begin(), l.end(), max(li, lj) - min(li, lj)); // 同じ組み合わせの除外のために, "jより大きいこと" という条件も追加する
ans += max((long)0, (right_idx-l.begin()-1) - max((long)j, (left_idx-l.begin())));
}
cout << ans << endl;
return 0;
}
lower_boundとupper_boundの使い分けや、ある値より小さいのために-1している細かいの注意
同じ組み合わせを足さないように、jより大きいこと という条件も追加している.