C++の練習を兼ねて, AtCoder Beginner Contest 077 の 問題C（Snuke Festival）を解いてみた.
■感想.
① N が 最大 10の5乗 と指示があったので, for文 の 3重ループは, TLE になると推測し, 二分探索などを模索した.
② lower_bound, upper_bound という便利な関数が用意されていることが, ネット上の情報で判明したので, 計算量削減に使えないか, 検討してみた.
③ 最初, A を 基準に試行錯誤してみたが, 条件を満たす組み合わせの数え上げが上手くいかず, 次に, B を 基準に試行錯誤してみたところ, 条件を満たす組み合わせの数え上げが上手くいった.
④ 本家の解答を見たところ, おおよそ解答方針が一致していたので, 時間かかってしまったものの, とりあえず粘ってみた甲斐があったと思われる.
本家のサイトARC084/ABC077 解説をご覧下さい。
■C++版プログラム
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <iostream> #include <algorithm> #include <vector> using namespace std; #define FOR(i, a, b) for(int i=(a); i<(b); ++i) typedef long long LL; int main() { // 1. 入力情報取得. int N; cin >> N; vector<LL> A, B, C; FOR(i, 0, N) { LL a; cin >> a; A.push_back(a); } FOR(i, 0, N) { LL b; cin >> b; B.push_back(b); } FOR(i, 0, N) { LL c; cin >> c; C.push_back(c); } // 2. 各A ～ C を, 昇順sort. sort(A.begin(), A.end()); sort(B.begin(), B.end()); sort(C.begin(), C.end()); // 3. B を 基準にして, B[j] (0 <= j <= N - 1) に対して, // lower_bound, upper_bound で, A[i] < B[j] < C[k] となるi, k の組み合わせを計算していく. // ※ A を 基準にすると, 上手く行かなかった. // lower_bound、upper_boundの基本的な使い方. // https://qiita.com/kontotto/items/c718ec114b1532a2d159 LL combination = 0; for(auto itr = B.begin(); itr != B.end(); ++itr) { // 3-1. B[j] を 取り出す. LL b = *itr; // 3-2. lower_bound で, A[i] を 取得. auto ita = lower_bound(A.begin(), A.end(), b); LL a = ita - A.begin(); // 3-3. upper_bound で, C[k] を 取得. auto itc = upper_bound(C.begin(), C.end(), b); LL c = C.end() - itc; // cout << *ita << " " << *itc << endl; // cout << a << " " << c << endl; // 3-4. 条件を満たす組み合わせを加算. combination += a * c; // 条件を満たす A の要素数 × 条件を満たす C の要素数. } // 4. 出力 ～ 後処理. cout << combination << endl; return 0; } |
■参照サイト
AtCoder Beginner Contest 077
lower_bound、upper_boundの基本的な使い方