C++の練習を兼ねて, AtCoder Beginner Contest 106 の 問題D（AtCoder Express 2）を解いてみた.
■感想.
① 時間内では, C011_scrambled ～ C016_scrambled で, TLEとなったので, ロジック見直しが必要となった.
※下記ソース: ABC_106_D_1.cpp
② 解答を確認して, 計算量の削減方法について, 大変参考になった.
※下記ソース: ABC_106_D_2.cpp
本家のサイトAtCoder Beginner Contest 106 解説をご覧下さい。
■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 |
// C011_scrambled ～ C016_scrambled で, TLEとなった. #include <iostream> #include <vector> #include <algorithm> using namespace std; #define FOR(i, a, b) for(int i=(a); i<(b); ++i) struct city { int li; // 都市Li. int ri; // 都市Ri. }; int main() { // 1. 入力情報取得. int N, M, Q; cin >> N >> M >> Q; // 2. 都市情報を保存. vector<city> cities; FOR(i, 0, M) { city c; cin >> c.li >> c.ri; cities.push_back(c); } // 3. Q個の質問に解答. FOR(i, 0, Q) { int p, q; cin >> p >> q; // 条件を満たす列車の本数を計算. int c = 0; for (vector<city>::const_iterator i = cities.begin(); i != cities.end(); i++) { if(p <= i->li && i->ri <= q) c++; } cout << c << endl; } // 4. 後処理. return 0; } |
|
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 |
// 解き直し. // AtCoder Beginner Contest 106 解説. // https://img.atcoder.jp/abc106/editorial.pdf #include <iostream> using namespace std; #define FOR(i, a, b) for(int i=(a); i<(b); ++i) int main() { // 1. 入力情報取得. int N, M, Q; cin >> N >> M >> Q; // 2. 都市情報を保存. int cities[501][501] = {}; FOR(i, 0, M) { int l, r; cin >> l >> r; cities[l][r]++; } // L方向に累積和. FOR(r, 0, 501) FOR(l, 1, 501) cities[r][l] += cities[r][l - 1]; // 3. Q個の質問に解答. FOR(i, 0, Q) { int p, q; cin >> p >> q; // 条件を満たす列車の本数を計算. int c = 0; FOR(r, p, q + 1) c += (cities[r][q] - cities[r][p - 1]); cout << c << endl; } // 4. 後処理. return 0; } |
■参照サイト
AtCoder Beginner Contest 106