TopCoder SRM 530 Div2 Hard GogoXReimuHakurai

色々迷ったけど、考え方を変えたらあっさり解けた問題。
http://community.topcoder.com/stat?c=problem_statement&pm=10788

問題

0～(N-1)のN個のステージからなるゲームがある。
このゲームでは、途中分岐があり、各ステージからより番号の大きな複数のステージに遷移できる。

このゲームをプレイしてステージ0からステージ(N-1)まで複数回到達したい。
なお、プレイする際に最低１個以上新たな遷移を含むようにしたい。
そのようなプレイは最大何回まで可能か。

解法

辺の数は最大N*(N-1)/2なので、最大遷移回数は1200回位である。
そこで、全遷移を列挙してしまおう。

新規の遷移を１回のプレイで多数使ってしまうともったいないので、１プレイで新たに使用する遷移は少なくしたい。
以下の手順を取ることで、ステージ0からステージ(N-1)に至る経路を辞書順に列挙できる。

• 現在のステージへの到達が初めてなら、番号の小さい順にDFSする。
• DFSの結果、ステージ(N-1)にたどりつく場合、経路を1個足す。
  • なお、DFSを毎回ステージ(N-1)まで行うと時間がかかってしまうが、一度DFS処理を行ったステージは、そこからステージ(N-1)に至る経路があるかどうか判明しており、かつ新規経路をたどる必要がないので、その時点でDFSを中断できる。

DFSで後ろのステージから順に経路を列挙していくので、結果的に辞書順の経路を得ることができる。
また、これらは明らかに新規遷移を含む。

class GogoXReimuHakurai {
	public:
	vector<string> S;
	int did[51];
	int able[51][51];
	int R,N;
	
	int dfs(int cur) {
		int x;
		if(did[cur]==1) R++;
		if(did[cur]==-1) {
			did[cur]=0;
			FOR(x,N) if(S[cur][x]=='Y') did[cur] |= dfs(x);
		}
		return did[cur];
	}
	
	int solve(vector <string> choices) {
		S=choices;
		MINUS(did);
		
		R=0;
		N=choices.size();
		did[N-1]=1;
		dfs(0);
		return R;
	}
};

まとめ

一見ややこしいけど落ち着けば簡単に解ける問題。
SRM530は他にGogoXMarisaKirisimaなんて問題がある…。