Atcoder解いてみた AtCoder Beginner Contest E - Transition Game

AtCoder Beginner Contest E - Transition Game

問題はこちら

回答

問題文の理解に少し苦しむ
N回ゲームを行う

1. 青木が操作回数を指定する
2. 高橋は、1~Nの整数を選び、黒板に書く
3. 1で指定された回数以下の走査を繰り返す
   黒板にxが書かれている時、それを消し、Axを新しく書く

i回目のゲームにおいて、最終的に黒板に書かれている数値がiなら高橋の勝ち

上記で、ポイントなのが、「黒板にxがかかれている時、それを消し、Axを新しく書く」
書かれている数値をインデックスに、入力データであるAにアクセスすることと解釈できる
これをみると、最初、1~Nの中の数値xが与えられ、それをインデックスにAxにアクセスし、さらにそれをインデックスにAにアクセスして行った結果、i番目のゲームにおいて、数値iに多取り付けばいいことが分かる
そのため、素直にやるとしたら、グラフを用意して、毎回のゲームで経路をたどっていけばいいが、そうするとO(N^2)でTLE

その後、どうすればいいか解説をみた
解説ではグラフのループを検出し、そのループ内の点数を数え上げればそれが答えになると述べられていた
以下、点の番号が0始まりだが、実際に手順を実行すると、0,1にはどうしてもたどりつけないことが分かる
高橋は上記の手順2において、グラフの開始位置を指定しているだけなため、その点を最適に設定すれば、ループ内の点であればどこでも到達できる
そのため、グラフ内のループ内の点数を数え上げればいい

0 → 1 → 2 → 3
        ↑    ↓
        └────┘

解説の方法でもいいがトポロジカルソートで実装した
トポロジカルソートを用いて、入次数0の点を削除していき、最終的に入次数が0でない点の総数を求めればいい
計算量はO(N)

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>

int N;
std::vector<int> A; // 各点から伸びる辺は一つ
std::vector<int> inDeg;


int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> N;
	
	A.resize(N);
	inDeg.resize(N);
	
	for (int i = 0; i < N; i++) {
		int a;
		std::cin >> a;
		a--;

		// i番目の点はa番目の点につながる
		A[i] = a;

		// A[i]番の点につながるため、入次数を更新
		inDeg[A[i]]++;
	}

	// 入次数が0の点を消していく
	std::queue<int> q;

	// 入次数0の点を入れる
	for (int i = 0; i < N; i++) {
		if (inDeg[i] == 0) {
			q.push(i);
		}
	}

	while (!q.empty()) {
		int s = q.front();
		q.pop();

		int t = A[s];
		// pが取り出されたため、pがつながっている点の入次数を減らす
		inDeg[t]--;

		// tの入次数が0になったらqueueに入れる
		if (inDeg[t] == 0) {
			q.push(t);
		}
	}

	int ans = 0;
	for (int i = 0; i < inDeg.size(); i++) {
		if (inDeg[i] != 0) {
			ans++;
		}
	}
	std::cout << ans << std::endl;

	return 0;
}