SRM524では大苦戦と思ったら、こちらはあっさり。
http://community.topcoder.com/stat?c=problem_statement&pm=11664
問題
N人の人がおり、そのうち何人かは2種類の噂を知っており、残りはどちらの噂も知らない。
時間1を掛け、各人はどちらかの噂を友人に展開出来る。
友人関係は有向辺で与えられる。
全員が全部の噂を知るのにかかる最短時間を求めよ。
解法
N<=16とかなり小さめ。
「各人、知ってる噂をどちらから展開するか」をbitmaskで持って総当たりし、あとは噂の展開をシミュレートするだけ。
1回のシミュレートは普通に書くとO(N^3)だけど、友人関係を32bit intで表現すればO(N^2)に落とせる。
全体でO(2^N*N^2)なので余裕。
class Rumor { public: string K; vector<string> G; int spm[16]; int N; int dodo(int mask) { int i,j,k,x,y; int sp1,sp2; int kn1,kn2,nkn1,nkn2; sp1=sp2=0; kn1=kn2=0; FOR(i,N) kn1|=(K[i]=='Y')<<i; FOR(i,N) kn2|=(K[i]=='Y')<<i; nkn1=kn1; nkn2=kn2; FOR(i,20) { if(nkn1==(1<<N)-1 && nkn2==(1<<N)-1) break; FOR(j,N) { int sp=0; if((sp1&(1<<j))==0 && (sp2&(1<<j))==0) { if(mask&(1<<j)) { if(kn2&(1<<j)) sp=2; else if(kn1&(1<<j)) sp=1; } else { if(kn1&(1<<j)) sp=1; else if(kn2&(1<<j)) sp=2; } } else if((sp1&(1<<j))==0 && (kn1&(1<<j))) sp=1; else if((sp2&(1<<j))==0 && (kn2&(1<<j))) sp=2; if(sp==1) nkn1 |= spm[j],sp1 |= 1<<j; if(sp==2) nkn2 |= spm[j],sp2 |= 1<<j; } kn1=nkn1; kn2=nkn2; } return i; } int getMinimum(string knowledge, vector <string> graph) { K=knowledge; G=graph; N=K.size(); int mi=20; int i,j; ZERO(spm); FOR(i,N) FOR(j,N) spm[i] |= (graph[i][j]=='Y')<<j; for(int mask=0;mask<1<<N;mask++) mi=min(mi,dodo(mask)); if(mi>=20) return -1; return mi; } };
まとめ
Div1 Mediumも結構難易度差激しいな。