はまやんはまやんはまやん

hamayanhamayan's blog

Box and Ball [AGC 002 : B]

問題

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;
}