問題
http://agc002.contest.atcoder.jp/tasks/agc002_b
N個の箱がある。
1番目の箱には赤ボール1つ、他の箱には白ボール1つがそれぞれ入っている。
M回、xi番目からyi番目に適当にボールを1つ移す。
全ての操作を終えた後、赤いボールが入っている可能性がある箱は何個?
2 <= N <= 10^5
1 <= M <= 10^5
考察
1. 色々実験して考えてみる
2. たくさんする
3. 予想「xi番目に赤ボールが入っている可能性があるならyi番目に赤ボールが入る可能性も出てくる」
4. 自明っぽいですが
5. 以下のように考えてみる
dp[i] = i番目に赤ボールが入る可能性 true or false
dp[1] = true
dp[xi] == true -> dp[yi] = false
6. これだとダメ
7. 例1のように「ボール移動後に箱の個数が0になる場合があれば、赤ボールが入っている可能性が消える」
8. なので、個数を数えるdp2も用意し、dp2[xi] == 0ならばdp[xi] = false とする
9. あとはdpを数えるだけ
実装
http://agc002.contest.atcoder.jp/submissions/824903
int N, M; bool dp[101010]; int dp2[101010]; //----------------------------------------------------------------- int main() { cin >> N >> M; dp[1] = true; rep(i, 0, N) dp2[i + 1] = 1; rep(i, 0, M) { int x, y; scanf("%d %d", &x, &y); if (dp[x]) dp[y] = true; dp2[x]--; dp2[y]++; if (!dp2[x]) dp[x] = false; } int ans = 0; rep(i, 0, N) if (dp[i + 1]) ans++; cout << ans << endl; }