SRM 557 Div2 Medium "IncubatorEasy"
問題
女の子がいっぱいいる。
女の子たちはそれぞれ、好きな女の子がいる。
片思いかもしれないし、両思いかもしれない。
自分自身が好きってこともありうる。
あなたは魔法使いで、普通の女の子を魔法少女にすることが出来る。
ただし、この魔法を使うと、女の子たちは以下のような行動をとってしまう。
1.魔法少女になってしまった子は、好きな子にプロテクトをかける。
2.プロテクトをかけられた子は、好きな子にプロテクトをかける。
上手い具合に魔法をかけて、
プロテクトがかかっていない魔法少女をなるべく多く作るようにしたい。
その最大数を返せ。
制約
1 <= 女の子の数 <= 10
方針
10人ならば全探索!
ソースコード
class IncubatorEasy { static const int MAX_N = 10; int N; vector<string> L; bool isM[MAX_N]; bool chk[MAX_N]; bool out( int i ){ bool res = true; for( int j = 0; j < N; j++ ){ if( L[i][j] == 'Y' && !chk[j] ){ chk[j] = true; res &= !isM[j]; res &= out( j ); } } return res; } bool in( int i ){ bool res = true; for( int j = 0; j < N; j++ ){ if( L[j][i] == 'Y' && !chk[j] ){ chk[j] = true; res &= !isM[j]; res &= in( j ); } } return res; } bool use_ok( int i ){ memset( chk, false, sizeof(chk) ); bool res = out( i ); if ( !res ) return false; memset( chk, false, sizeof(chk) ); return in( i ); } int dfs( int i ){ if( i >= N ) return 0; int use = 0; isM[i] = true; if( use_ok(i) ) use = dfs(i+1) + 1; isM[i] = false; int nouse = dfs(i+1); return max( use, nouse ); } public: int maxMagicalGirls(vector <string> love){ N = love.size(); L = love; memset( isM, false, sizeof(isM) ); return dfs(0); } };