C++の練習を兼ねて, AtCoder Beginner Contest 105 の 問題D（Candy Distribution）を解いてみた.
■感想.
① C++ 連想配列クラス(std::map) の 使い方を練習出来て良かったと思う.
② 連想配列クラスから, 値を取り出してくる場合, イテレータを使うのが良いらしい.
③ 余りゼロのケースは, 初めから, カウントアップしておく点に注意が必要.
④ 最大, 48[ms] かかっているテストケースがあったので, 改善の余地が, たくさんありそう.
本家のサイトABC 105 解説をご覧下さい。
■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 |
// 解き直し. // ABC 105 解説. // https://img.atcoder.jp/abc105/editorial.pdf #include <iostream> #include <map> using namespace std; typedef long long LL; #define FOR(i, a, b) for(int i=(a); i<(b); ++i) int main() { // 1. 入力情報取得. LL N, M; cin >> N >> M; // 2. 累積和で保管(但し, mod M で考える). LL A[N + 1] = {}; map<LL, LL> B{}; // 解説通り, mapを使用. FOR(i, 1, N + 1) { cin >> A[i]; A[i] += A[i - 1]; A[i] %= M; B[A[i]]++; } // 3. お菓子の配り方をカウントアップ. // 3-1. 余りゼロのケース(B[0])は, 常に, 加算しておく必要がある. LL aCount = B[0]; // 3-2. B[i]個から, 2個選ぶ選び方の組み合わせを加算. // FOR(i, 0, M) aCount += (B[i] - 1) * B[i] / 2; // -> M が 大きい場合, 終了コード 9 となり, 正しく実行されないことを確認したので, // iterator を 使う形に書き換えた. for(auto itr = B.begin(); itr != B.end(); ++itr) { LL bi = itr->second; aCount += (bi - 1) * bi / 2; } // 4. 出力 ～ 後処理. cout << aCount << endl; return 0; } |