C++の練習を兼ねて, AtCoder Grand Contest 003 の 問題A (Wanna go back home) ～ 問題C (BBuBBBlesort!) を解いてみた.
■感想.
1. 問題A, C は, 解答を見る前に, 何とか解答まで辿り着いたので良かったと思う.
2. 問題B は, 一見とっつきやすそうに見えたが, 知識不足で解けなかったため, 解答を見直して, 解きなおした.
本家のサイトAtCoderGrandContest003解説をご覧下さい.
■C++版プログラム(問題A／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 |
#include <bits/stdc++.h> using namespace std; int main() { // 1. 入力情報取得. string S; cin >> S; // 2. 各方角の出現数をカウント. int n = 0, w = 0, s = 0, e = 0; for(int i = 0; i < S.size(); i++){ char c = S[i]; if(c == 'N') n++; if(c == 'W') w++; if(c == 'S') s++; if(c == 'E') e++; } // 3. 出力. string ans = "Yes"; if(n + s > 0 && n * s == 0) ans = "No"; if(w + e > 0 && w * e == 0) ans = "No"; cout << ans << endl; return 0; } |
■C++版プログラム(問題B／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 |
// 解き直し. // AtCoderGrandContest003解説. // http://agc003.contest.atcoder.jp/data/agc/003/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; int main() { // 1. 入力情報取得. LL N; cin >> N; LL A[N + 1]; for(int i = 0; i < N; i++) cin >> A[i]; // 番兵設定. A[N] = 0; // 2. 解説通り. // A[i] = 0 の タイミングで, 区切って計算. LL ans = 0, counter = 0; for(int i = 0; i < N + 1; i++){ if(A[i] != 0) counter += A[i]; else ans += counter / 2, counter = 0; } // 3. 出力. cout << ans << 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 43 44 45 46 47 |
#include <bits/stdc++.h> using namespace std; using LL = long long; int main() { // 1. 入力情報取得. LL N; cin >> N; LL A[N], B[N]; for(int i = 0; i < N; i++){ LL a; cin >> a; A[i] = a; B[i] = a; // 後で, 比較するための配列, sortしない. } // 2. 昇順sort. sort(A, A + N); // 3. sort済み数列の偶奇情報を保存. // mo: i が 奇数で保存. me: i が 偶数で保存. map<LL, int> mo, me; for(int i = 0; i < N; i++){ if(i % 2 == 1) mo[A[i]]++; else me[A[i]]++; } // 4. 操作２で, 昇順 sort 出来るパターンが, 限定されているように見える. // ex. // 1 2 3 5 4 -> 操作２を何回使っても, 1 2 3 4 5 とならない. // 3 4 5 2 1 -> 3 2 5 4 1 -> 3 2 1 4 5 -> 1 2 3 4 5 // -> 操作２だけ使って, 1 2 3 4 5 と出来る. // 数列 の 偶数番目, 奇数番目 について, // 昇順 sort 前後 で, 同じ内容になっている必要があるように見える. LL counter = 0; for(int i = 0; i < N; i++){ if(i % 2 == 0 && mo[B[i]] > 0) counter++; if(i % 2 == 1 && me[B[i]] > 0) counter++; } // 5. 出力. LL ans = counter / 2; cout << ans << 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 51 52 53 54 55 56 57 58 59 60 61 62 63 |
[入力例] 4 2 4 3 1 [出力例] 1 ※AtCoderテストケースより [入力例] 5 10 8 5 3 2 [出力例] 0 ※AtCoderテストケースより [入力例] 6 1 2 3 4 6 5 [出力例] 1 [入力例] 10 1 2 4 3 5 6 10 9 8 7 [出力例] 3 ※操作例(操作１は, 3回と分かる) 1 2 4 3 5 6 10 9 8 7 ↓操作１(4 3 -> 3 4) 1 2 3 4 5 6 10 9 8 7 ↓操作１(10 9 -> 9 10) 1 2 3 4 5 6 9 10 8 7 ↓操作１(8 7 -> 7 8) 1 2 3 4 5 6 9 10 7 8 ↓操作２(9 10 7 -> 7 10 9) 1 2 3 4 5 6 7 10 9 8 ↓操作２(10 9 8 -> 8 9 10) 1 2 3 4 5 6 7 8 9 10 |
■参照サイト
AtCoder Grand Contest 003