C++の練習を兼ねて, AtCoder Grand Contest 011 の 問題A (Airport Bus) ～ 問題B (Colorful Creatures) を解いてみた.
■感想.
1. 問題A は, 方針が見えなかったので, 解説を参照して実装したところ, 何とか, AC版となった.
2. 問題B は, 方針は早々に決まったものの, AC版に到達までに, 実装に非常に苦労した.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトAGC 011 解説をご覧下さい.
■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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
// 解き直し. // https://img.atcoder.jp/agc011/editorial.pdf #include <bits/stdc++.h> using namespace std; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) int t[101010]; int main(){ // 1. 入力情報. int N, C, K; scanf("%d %d %d", &N, &C, &K); rep(i, N) scanf("%d", &t[i]); // 2. sort. sort(t, t + N); // 3. バスの台数を計算. int bus = 0, at = 0, idx = 0, top = t[0]; while(idx < N){ // 先頭と同じバスに乗る乗客を検索. at = upper_bound(t, t + N, top + K) - t; // 乗客を振り分ける. if(at - idx >= C) idx += C; else idx = at; // 先頭を更新. top = t[idx]; // バスの台数をカウントアップ bus++; } // 4. 出力. printf("%d\n", bus); 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 |
[入力例] 5 3 5 1 2 3 6 12 [出力例] 3 ※AtCoderテストケースより [入力例] 6 3 3 7 6 2 8 10 6 [出力例] 3 ※AtCoderテストケースより [入力例] 12 5 3 30 7 6 1 15 18 27 23 2 8 10 6 [出力例] 6 [入力例] 15 3 7 55 30 17 77 6 15 65 25 38 27 23 7 15 10 60 [出力例] 8 |
■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 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 |
#include <bits/stdc++.h> using namespace std; using LL = long long; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) LL a[101010], aCum[101010]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld", &a[i]); // 2. sort. sort(a, a + N); // 3. 一次元累積和. rep(i, N) aCum[i + 1] = a[i] + aCum[i]; // 4. 最終的に残ることが出来るか？ int ans = 0; rep(i, N){ // i番目の生き物について調査. LL ua = aCum[i + 1]; int cur = i, bef = i; bool ok = true; while(cur < N && ua < 1010101010){ // 自身の二倍となる箇所のインデックスを検索. cur = upper_bound(a, a + N, ua + ua) - a; // 前回と等しい場合は, 合体出来ないケースに引っ掛かったと見る. // if(cur < N && a[bef + 1] >= aCum[cur]){ // in13.txt で, WA版 のため, ロジック修正. if(cur < N && a[bef] > aCum[cur]){ ok = false; break; } // 合体. ua = aCum[cur]; // 前回分更新. bef = cur; } // カウント. if(ok) ans++; } // 5. 出力. printf("%d\n", ans); 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 |
[入力例] 3 3 1 4 [出力例] 2 ※AtCoderテストケースより [入力例] 5 1 1 1 1 1 [出力例] 5 ※AtCoderテストケースより [入力例] 6 40 1 30 2 7 20 [出力例] 4 ※AtCoderテストケースより [入力例] 12 12345 7654 5432 2100 789 555 321 456 111 11 5 3 [出力例] 8 |
■参照サイト
AtCoder Grand Contest 011