TopCoder SRM 530 Div1 Medium GogoXMarisaKirisima

こちらもDiv2 Hardの妙な改変問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11267

問題

基本的な問題設定はDiv2 Hardと同じ。
TopCoder SRM 530 Div2 Hard GogoXReimuHakurai - kmjp's blog

ただし、Div2 Hardではステージ番号が戻る遷移はなかったが、Div1 Mediumではステージが戻る遷移もある。

解法

Div2 Hardと違いループがあるので、辞書順探索は使えない。

まずWarshall-Floyd法を実行し、「このパスを通ってしまうと最終ステージにたどり着けない」という遷移を消しておく。

Editorialを見ると分かるが、この時の答えは(残った遷移数)-(移動できるステージ数)+2である。
これは以下のように考えると明らか。

• 0番のステージを除き、初めてあるステージに来た場合、どこか1か所の遷移はそのプレイ中で通らないといけない。
• 逆に2回目以降そのステージに来た場合は、その都度新しい遷移を取ることで新規プレイルートを構築できる。

よって、各ステージにおいて、(可能な遷移-1)の分だけ新規プレイルートを構築できる。
ただし、ステージ0は初回も新規プレイルートを構築できることと、ステージ(N-1)ではそれ以上遷移しないことも１プレイルートとしてカウントできるので(可能な遷移)の分新規プレイルートとカウントできる。

よって、(全遷移数)-((ステージ数)-2)が答えとなる。

以下のコードは(全遷移数)-((ステージ数)-2)の式には直接たどり着いていないが、各ステージにおいて、0番と(N-1)番を除き1引いた遷移数の和をカウントしている。

class GogoXMarisaKirisima {
	public:
	int N;
	int mat[51][51],mat2[51][51];
	
	int solve(vector <string> choices) {
		int x,y,i;
		N=choices.size();
		FOR(x,N) FOR(y,N) mat[x][y]=mat2[x][y]=(choices[x][y]!='Y');
		FOR(x,N) mat[x][x]=mat2[x][x]=0;
		FOR(i,N) FOR(x,N) FOR(y,N) mat2[x][y]=min(mat2[x][y],mat2[x][i]+mat2[i][y]);
		
		if(mat2[0][N-1]) return 0;
		
		int ret=1;
		FOR(x,N) if(mat2[0][x]==0 && mat2[x][N-1]==0) {
			FOR(y,N) if(x!=y && mat[x][y]==0 && mat2[y][N-1]==0) ret++;
			if(x!=N-1) ret--;
		}
		return ret;
	}
}

まとめ

Editorialや他人の解法を見てこの単純な解答に気づいた。
これは本番1発じゃ思い浮かばないな…。