Div2 hard GogoXReimuHakurai

2012-01-20

00:42 |

40分ほど考えたができず。

その後、解の構造は「スタート→→未使用の辺→→ゴール」となってるんじゃないかと思って、

floyd-warshal して i < j && reach[0][i] && choices[i][j]=='Y' && reach[j][N-1] なら ans++ としてみたけど sample0 でなんか大きめの値がでてきてあきらめる。

（追記）

さらに他の人のコードとか editorial 見て以下のコードで system test 通った。

未使用の辺が (0, k) または (k, N-1) の場合(0 < k < N-1)、どちらの経路も 0→k→N-1 となり重複してカウントされるので、

reach[0][k] && reach[k][N-1] の個数だけ後から引くと正しい答えが求まるようだ。

納得したようなしないような。少なくとも本番中に思いつく気がしない。。

class GogoXReimuHakurai {
	public:
	int solve(vector<string> ch){
		int N=ch.size();
		VVI w(N, VI(N, 0)); // w[i][j] ... can reach from i to j
		REP(i, N) REP(j, N) w[i][j]=ch[i][j]=='Y';
		REP(i, N) w[i][i]=1;
		REP(k, N) REP(i, N) REP(j, N) w[i][j] |= w[i][k]&w[k][j]; // floyd-warshall
		if(!w[0][N-1]) return 0;
		//cout<<w<<endl;
		
		int ans=0;
		REP(i, N) REP(j, N) if(w[0][i] && ch[i][j]=='Y' && w[j][N-1]) ans++;
		ans+=2;
		REP(i, N) if(w[0][i] && w[i][N-1]) ans--;
		return ans;
	}