| 
N 曲から P 曲のプレイリストを作る。何種類作れるか。ただし N 曲すべて１回は使うこと。かつ、同じ曲を使う場合は間に M 曲以上おかないといけない。
N==P なら N! 通りである。ふむ。
最近の M 回はどれも違う曲だから、その次の曲は N-M 通りだな。ふむ。
じゃあ N! * (N-M)**(P-N) だと思って書いてみたけど、これだと最初の N 回で N 曲使うパターンしか見てないな。だめだ。
DP ぽいけど漸化式が思いつかん。
で、ちょっと考えて hard に行って戻ってきてやっぱりできず。
editorial などによると、dp[プレイリストの曲数][使った曲の種類数] == 可能なプレイリストの数 というきれいな式になるらしい。
dp[i][j] = dp[i-1][j-1] * (N-(j-1)) // 使ってない曲は N-(j-1) 種類 + dp[i-1][j] * max(j-M, 0) // 既に使った j 種類のうち、最近の M 曲は使えない。 // さらにその M 曲は全部異なるので j-M 曲使える
class NoRepeatPlaylist { public: int numPlaylists(int N, int M, int P) { ll mod = 1000000007LL; VVI dp(P+1, VI(N+1)); dp[0][0]=1; for(int i=1;i<=P;i++) for(int j=1;j<=N;j++) { dp[i][j] = (dp[i-1][j-1] * (N-(j-1)) + dp[i-1][j] * max(0, j-M)) % mod; } return dp[P][N]; } };
| 
辺を追加削除するコストが与えられた時、無向グラフを最小コストで木にする問題。
辺の変更コストの小さい順に、重複した（消しても到達性が変わらない）辺を消していく。
その後同じくコストの小さい順に連結に寄与する辺を追加していく。
warshall-floyd でごりごり。冗長なコードになった。
自分への辺を追加していなかったり、隣接行列上で (i, j) を繋いだら (j, i) も繋がないといけないのを忘れていたりしてしばらく苦戦していたが、
ようやく終了 10 秒くらい前に手元のテストが通ったのでアプレットでコンパイルしたところで 糸冬 了 。
↓あとで (practice system test pass)
int dec(char c) { if('A'<=c&&c<='Z') return c-'A'; if('a'<=c&&c<='z') return c-'a'+26; return -1; } class KingdomReorganization { public: int getCost(vector <string> ki, vector <string> build, vector <string> destroy) { int N=ki.size(); vector<pair<int, pair<int, int> > > bu(N*N); vector<pair<int, pair<int, int> > > de(N*N); //VVI bu(N, VI(N, 0)); //VVI de(N, VI(N, 0)); REP(i, N) REP(j, N) bu[i*N+j] = MP(dec(build[i][j]), MP(i, j)); REP(i, N) REP(j, N) de[i*N+j] = MP(dec(destroy[i][j]), MP(i, j)); sort(ALL(de)); sort(ALL(bu)); cout<<bu<<endl; cout<<de<<endl; VVI orig(N, VI(N, 0)); REP(x, N) REP(y, N) if(ki[x][y]=='1') orig[x][y]=1; REP(x, N) orig[x][x]=1; int ans = 0; { VVI orig_r(N, VI(N, 0)); REP(x, N) REP(y, N) orig_r[x][y] = orig[x][y]; REP(k, N) REP(i, N) REP(j, N) orig_r[i][j] |= orig_r[i][k]&orig_r[k][j]; REP(ii, N*N) { int ei = de[ii].second.first; int ej = de[ii].second.second; int co = de[ii].first; VVI w(N, VI(N, 0)); REP(x, N) REP(y, N) w[x][y]=orig[x][y]; if(w[ei][ej]==0) continue; w[ei][ej] = w[ej][ei] = 0; REP(k, N) REP(i, N) REP(j, N) w[i][j] |= w[i][k]&w[k][j]; int ok=1; REP(i, N) REP(j, N) if(orig_r[i][j]==1 && w[i][j]==0) ok=0; if(ok) { ans+=co; orig[ei][ej] = orig[ej][ei] = 0; } } } { VVI orig_r(N, VI(N, 0)); REP(x, N) REP(y, N) orig_r[x][y] = orig[x][y]; REP(k, N) REP(i, N) REP(j, N) orig_r[i][j] |= orig_r[i][k]&orig_r[k][j]; cout<<orig_r<<endl; REP(ii, N*N) { int ei = bu[ii].second.first; int ej = bu[ii].second.second; int co = bu[ii].first; VVI w(N, VI(N, 0)); REP(x, N) REP(y, N) w[x][y]=orig[x][y]; if(w[ei][ej]==1 || w[ej][ei]==1) continue; w[ei][ej] = w[ej][ei] = 1; REP(k, N) REP(i, N) REP(j, N) w[i][j] |= w[i][k]&w[k][j]; cout<<w<<endl; int ok=0; REP(i, N) REP(j, N) if(orig_r[i][j]==0 && w[i][j]==1) ok=1; if(ok) { cout<<ei<<" "<<ej<<endl; ans+=co; orig[ei][ej] = 1; orig[ej][ei] = 1; REP(x, N) REP(y, N) orig_r[x][y] = orig[x][y]; REP(k, N) REP(i, N) REP(j, N) orig_r[i][j] |= orig_r[i][k]&orig_r[k][j]; cout<<"orig_r " <<orig_r<<endl; } } } return ans; } };
さらに後から、一旦すべて消して最小全域木に帰着させたやつを書いた。
最初に全部消すコストを数えておいて、辺の重みとして
を持つグラフの最小全域木を union-find を使った Kruskal で求める。
union-find は spaghetti source さんから。
int dec(char c) { if('A'<=c&&c<='Z') return c-'A'; if('a'<=c&&c<='z') return c-'a'+26; return -1; } struct UnionFind { vector<int> data; UnionFind(int size) : data(size, -1) { } bool unionSet(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool findSet(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } }; class KingdomReorganization { public: int getCost(vector <string> ki, vector <string> build, vector <string> destroy) { int ans = 0; int N=ki.size(); vector<pair<int, pair<int, int> > > bu; REP(i, N) REP(j, N) { if(ki[i][j]=='1') { bu.PB(MP(-dec(destroy[i][j]), MP(i, j))); ans += dec(destroy[i][j]); ki[i][j]=ki[j][i]='0'; } else { bu.PB(MP(dec(build[i][j]), MP(i, j))); } } sort(ALL(bu)); //cout<<bu<<endl; UnionFind uf(N); REP(ii, bu.size()) { int ei = bu[ii].second.first; int ej = bu[ii].second.second; int cost = bu[ii].first; if(uf.unionSet(ei, ej)) ans += cost; } return ans; } };
