C++の練習を兼ねて, AtCoder Beginner Contest 084 の 問題C（Special Trains) ～ 問題D (2017-like Number) を解いてみた.
■感想.
1. 問題C は, いったん解いてみたが, ロジックのバグを直すことが出来なかったため, 解答を参照して, 復習した.
2. 問題D は, いったん解いて, TLE版まで持ってこれたので, 2017に似た数のテーブルを持たせたりして, 計算量を減らすように修正したところ, AC版に到達出来た.
本家のサイトABC 084 解説をご覧下さい.
■C++版プログラム(問題C／WA版).
|
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 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) struct train { int c; // 駅間にかかる列車時間(秒). int s; // 開通式開始後(秒). int f; // 列車の発車頻度(秒). }; // 駅(start + 1) ～ 駅N までの 開通式開始秒後を計算. // @param start: 駅番号 - 1. // @param N: 駅情報のサイズ. // @param v: 駅情報. // @return : 計算結果. int getTrainTime(int start, int N, vector<train> v){ int buf[N] = {}; FOR(i, start, N - 1){ if(i == start) { buf[i + 1] = v[i].s + v[i].c; continue; } buf[i + 1] += buf[i]; buf[i + 1] += v[i].c; int dt = buf[i] - v[i].s; cout << dt << endl; if(dt >= 0) buf[i + 1] += (dt % v[i].f); else buf[i + 1] += (-dt); } return buf[N - 1]; } int main() { // 1. 入力情報取得. int N; cin >> N; vector<train> v; FOR(i, 0, N - 1) { train t; cin >> t.c >> t.s >> t.f; v.push_back(t); } // 2. 各駅 ～ 駅N の 開通式開始秒後を計算. int ans[N] = {}; FOR(i, 0, N - 1) ans[i] = getTrainTime(i, N, v); // 3. 出力 ～ 後処理. FOR(i, 0, N) cout << ans[i] << endl; return 0; } |
■C++版プログラム(問題C／AC版).
|
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 |
// 解き直し. // ABC 084 解説. // https://img.atcoder.jp/abc084/editorial.pdf #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) struct train { int c; // 駅間にかかる列車時間(秒). int s; // 開通式開始後(秒). int f; // 列車の発車頻度(秒). }; int main() { // 1. 入力情報取得. int N; cin >> N; vector<train> v; FOR(i, 0, N - 1) { train t; cin >> t.c >> t.s >> t.f; v.push_back(t); } // 2. 解説通り. int ans[N] = {}; FOR(i, 0, N) { int t = 0; FOR(j, i, N - 1){ train vj = v[j]; if(t < vj.s) t = vj.s; else if(t % vj.f == 0); else t = t + vj.f - t % vj.f; t += vj.c; } cout << t << endl; } return 0; } |
■C++版プログラム(問題D／TLE版).
|
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 |
// TLE版(01.txt - 07.txt). #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define FORN(i, a, b, n) for(int i = (a); i < (b); i += n) // 2017に似た数であるかの判定. // @param m: 素数マップ. // @param n: 与えられた奇数. // @return: 2017に似た数 … true, そうでない場合 … false. bool is2017Like(map<int, int> m, int n){ int x = (n + 1) / 2; // cout << "n=" << n << " x=" << x << endl; if(m[n] == 1 && m[x] == 1) return true; else return false; } int main() { // 1. 入力情報取得. int Q; cin >> Q; int left[Q], right[Q]; FOR(i, 0, Q) cin >> left[i] >> right[i]; // 2. 素数を用意する. map<int, int> m; vector<int> v; m[2]++; v.push_back(2); FORN(i, 3, 100002, 2) { bool isPrime = true; FORN(j, 3, sqrt(i) + 1, 2) { if(i % j == 0){ isPrime = false; break; } } if(isPrime) m[i]++, v.push_back(i); } // 3. 2017に似た数の個数を計算. FOR(i, 0, Q){ // 3-1. 各変数初期化. int l = left[i]; int r = right[i]; int like2017 = 0; // 3-2. l ～ r で, 2017に似た数の個数をカウント. FORN(j, l, r + 1, 2) if(j % 2 == 1 && j >= l && j <= r && is2017Like(m, j)) like2017++; // 3-3. 出力. cout << like2017 << endl; } return 0; } |
■C++版プログラム(問題D／AC版).
|
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 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define FORN(i, a, b, n) for(int i = (a); i < (b); i += n) int main() { // 1. 入力情報取得. int Q; cin >> Q; int left[Q], right[Q]; FOR(i, 0, Q) cin >> left[i] >> right[i]; // 2. 素数を用意する. map<int, int> m; vector<int> v; m[2]++; v.push_back(2); FORN(i, 3, 100002, 2) { bool isPrime = true; FORN(j, 3, sqrt(i) + 1, 2) { if(i % j == 0){ isPrime = false; break; } } if(isPrime) m[i]++, v.push_back(i); } // 3. 2017に似た数を用意する. // ex. 3, 5, 13, 37, 61, 73, 157, 193, 277, 313 vector<int> v2017; for(auto &p : v) { int x = (p + 1) / 2; if(m[x] == 1) v2017.push_back(p); } // FOR(i, 0, 10) cout << v2017[i] << endl; // 4. 2017に似た数の個数を計算. FOR(i, 0, Q){ // 4-1. 各変数初期化. int l = left[i]; int r = right[i]; int like2017 = 0; // 4-2. l ～ r で, 2017に似た数の個数をカウント. vector<int>::iterator lItr, rItr; lItr = lower_bound(v2017.begin(), v2017.end(), l); rItr = upper_bound(v2017.begin(), v2017.end(), r); int lIndex = distance(v2017.begin(), lItr); int rIndex = distance(v2017.begin(), rItr); // cout << "l=" << l << " r=" << r << " lIndex=" << lIndex << " rIndex=" << rIndex << endl; int diff = rIndex - lIndex; like2017 += diff; // 4-3. 出力. cout << like2017 << endl; } 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 40 41 42 43 44 45 46 47 48 49 50 |
[入力例] 1 3 7 [出力例(debug版)] l=3 r=7 lIndex=0 rIndex=2 2 ※AtCoderのテストケースより [入力例] 4 13 13 7 11 7 11 2017 2017 [出力例(debug版)] l=13 r=13 lIndex=2 rIndex=3 1 l=7 r=11 lIndex=2 rIndex=2 0 l=7 r=11 lIndex=2 rIndex=2 0 l=2017 r=2017 lIndex=35 rIndex=36 1 ※AtCoderのテストケースより [入力例] 6 1 53 13 91 37 55 19 51 73 91 13 49 [出力例(debug版)] l=1 r=53 lIndex=0 rIndex=4 4 l=13 r=91 lIndex=2 rIndex=6 4 l=37 r=55 lIndex=3 rIndex=4 1 l=19 r=51 lIndex=3 rIndex=4 1 l=73 r=91 lIndex=5 rIndex=6 1 l=13 r=49 lIndex=2 rIndex=4 2 ※AtCoderのテストケースより |
■参照サイト
AtCoder Beginner Contest 084