| 
総当りで TLE、その後 editorial 見てヒントをもらって書いた(practice system test pass)
辺の数が頂点数-1で連結なので木になる。
残りが remain 個あったとして、どれかの葉に i 個の子ノードを加える操作を（できるなら）したときの最大 score を返す。
（葉だけに加えてよいのは、葉でないノードに加える選択肢は以前のどこかで葉に加える操作に含まれるので）
その際、ルートノードだったら次数 i のノードが１個増え、次数１の子ノードが i 個増える。
ルートじゃないときは、次数１のノード（親への辺の分）が１個減り、次数 i+1 のノードが１個増え、次数１の子ノードが i 個増える。
で最初にルートが置いてあるとして、remain == 頂点数-1 として再帰関数をよびだす。
それをメモ化。
全然DP脳じゃないけどメモ化再帰脳には少しなってきたような気がするｗ
class P8XGraphBuilder { public: VI dp; int f(vector<int>& scores, int remain) { if(remain==0) return 0; if(dp[remain]!=-1) return dp[remain]; int ans = -100; for(int i=1;i<=remain;i++) { //cout<<"remain "<<remain<<" take "<<i<<" "<<scores[i]<<" "<<endl; int a = f(scores, remain-i); //cout<<"remain "<<remain<<" take "<<i<<" "<<scores[i]<<" "<<a<<" -> "<<-scores[0]+scores[i]+i*scores[0]+a<<endl; ans = max(ans, (remain<scores.size()?-scores[0]+scores[i]:scores[i-1])+i*scores[0]+a); } dp[remain] = ans; return ans; } int solve(vector <int> scores) { dp.assign(54, -1); int ans = f(scores, scores.size()); return ans; }
↓最初に書いた総当たりのコード
ルートだけの状態から出発して、既存ノードの次数ごとにノードを追加してヒストグラムを更新。
結構同じ状態があるんじゃないかと思ったけどそうでもなく爆発。
(↓だめな例)
class P8XGraphBuilder { public: int solve(vector <int> scores) { set<VI > se; VI a; a.push_back(2); se.insert(a); int ans = -100; int co=0; while(se.size()) { co++; const VI& a = *se.begin(); //cout<<"pop "<<a<<endl; if(a.size()==scores.size()) { int lans = 0; REP(i, a.size()) lans+=scores[i]*a[i]; ans=max(ans, lans); } else { REP(i, a.size()) { VI b(a); b.push_back(0); if(b[i]>0) { b[i]-=1; b[i+1]+=1; b[0]++; //cout<<b<<endl; se.insert(b); } } } se.erase(se.begin()); } cout<<co<<endl; return ans;
| 
解説とかいろいろ見てからコードだけ書いた。(practice system test pass)
２部マッチング問題の実装練習ということで。
maximumFlow() は spaghetti sourceさんより拝借。
すべての「?」について、まず０として列と列のマッチングに成功したら次へ、失敗したら１にして次へ。
最後に残ったものが辞書順最小かつヒントに矛盾しない答え。
こういう、いくつかのアルゴリズムを組み合わせる系ってすげぇと思う。
なんとかの最大値を求めるために解を仮定して二分探索するやつとか。
#define INF 1000000 typedef int Weight; struct Edge { int src, dst; Weight weight; Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) { } }; bool operator < (const Edge &e, const Edge &f) { return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!! e.src != f.src ? e.src < f.src : e.dst < f.dst; } typedef vector<Edge> Edges; typedef vector<Edges> Graph; typedef vector<Weight> Array; typedef vector<Array> Matrix; #define RESIDUE(s,t) (capacity[s][t]-flow[s][t]) Weight maximumFlow(const Graph &g, int s, int t) { int n = g.size(); Matrix flow(n, Array(n)), capacity(n, Array(n)); REP(u,n) FOR(e,g[u]) capacity[e->src][e->dst] += e->weight; Weight total = 0; while (1) { queue<int> Q; Q.push(s); vector<int> prev(n, -1); prev[s] = s; while (!Q.empty() && prev[t] < 0) { int u = Q.front(); Q.pop(); FOR(e,g[u]) if (prev[e->dst] < 0 && RESIDUE(u, e->dst) > 0) { prev[e->dst] = u; Q.push(e->dst); } } if (prev[t] < 0) return total; // prev[x] == -1 <=> t-side Weight inc = INF; for (int j = t; prev[j] != j; j = prev[j]) inc = min(inc, RESIDUE(prev[j], j)); for (int j = t; prev[j] != j; j = prev[j]) flow[prev[j]][j] += inc, flow[j][prev[j]] -= inc; VI path; for (int j = t; prev[j] != j; j = prev[j]) path.push_back(j); path.push_back(s); reverse(ALL(path)); total += inc; //cout<<"Update "<<path<<" -> total "<<total<<endl; } } void add_edge(Graph& g, int s, int e, int w) { g[s].push_back(Edge(s, e, w)); g[e].push_back(Edge(e, s, 0)); } class P8XMatrixRecovery { public: vector <string> solve(vector <string> rows, vector <string> col) { int R = rows.size(); int C = rows[0].size(); REP(yy, R) { REP(xx, C) { if(rows[yy][xx]!='?') continue; rows[yy][xx] = '0'; int t = C*2+2-1; //cout<<"BEGIN "<<xx<<" "<<yy<<endl; Graph g(C*2+2, Edges()); REP(x, C) add_edge(g, 0, 1+x, 1); REP(x, C) add_edge(g, 1+C+x, t, 1); REP(x, C) REP(x1, C) { int ee = 1; REP(y, R) { if(rows[y][x]=='?' || col[x1][y]=='?' || rows[y][x]==col[x1][y]) { } else ee=0; } if(ee) add_edge(g, 1+x, 1+C+x1, 1); } if(C!=maximumFlow(g, 0, t)) { rows[yy][xx] = '1'; } //cout<<"RESULT "<<rows[yy][xx]<<endl; } } return rows; }
