C++の練習を兼ねて, AtCoder Grand Contest 002 の 問題B（Box and Ball) を解いてみた.
■感想.
1. 解答方針が, 全く見えなかったので, 解答を確認したところ, なるほどと感心させられた.
本家のサイトAtCoder Grand Contest 002 解説をご覧下さい.
■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 |
// 解き直し. // AtCoder Grand Contest 002 解説. // http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdf #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) struct Box { int x; // 移動元(箱). int y; // 移動先(箱). }; int main() { // 1. 入力情報取得. int N, M; cin >> N >> M; vector<Box> v; FOR(i, 0, M) { Box b; cin >> b.x >> b.y; b.x--; b.y--; v.push_back(b); } // 2. 各箱について, ボールの個数を設定(解説通り.). int balls[N] = {}; FOR(i, 0, N) balls[i]++; bool red[N] = {}; red[0] = true; // 3. 赤いボールの移動を確認(解説通り). FOR(i, 0, M) { Box b = v[i]; if(red[b.x]) red[b.y] = true; balls[b.x]--; balls[b.y]++; if(balls[b.x] == 0) red[b.x] = false; } // 4. 出力. int ans = 0; FOR(i, 0, N) if(red[i]) ans++; cout << ans << endl; return 0; } |
■参照サイト
AtCoder Grand Contest 002