SRM 549 Div2 Hard OrderOfTheHats

問題

http://apps.topcoder.com/wiki/display/tc/SRM+549

あるグラフの隣接行列が与えられる。このグラフに辺を加えるか、すでにある辺を取り除くかしてacyclicにしたい。必要な手順の最小回数を求めよ。

やりかた

Editorialを参考にしました。

bitDP。
acyclicにするという目的上、辺を新たに加えるという操作をする必要はない。とすると、するべき操作は辺を取り除くだけになる。acyclicであればグラフはトポロジカルにソート可能であって、逆もまた然り。そのため頂点がある順列でトポロジカルにソートされているとしたときに、トポロジ順とは逆向きに張っている辺を取り除けばいい。この辺の数がこの順列にたいしての手順数になる。よってすべての順列について試し、この内最小のものを探せばいい。
実際はどうやるかということについては頂点数が20以下であることから、bitDPで解くことができる。
bitDP[mask] := （頂点集合maskに対して、グラフをacyclicにするための最小手順数）

このように定義すると、次に頂点iを追加するとき
dp[mask]は、「maskに頂点iを加えた集合」に対して頂点iから伸びている辺の数（つまり逆辺の数）＋dp[mask | (1 << i)]

という形で更新していくことができる。
以下ソース。

int n, adj[22];
int dp[1 << 20];

class OrderOfTheHats {
public:
  int F(int mask){
    if(mask == (1 << n) - 1) return 0;
    
    int &ret = dp[mask];
    if(ret > -1) return ret;
    ret = INF;
    for(int i = 0; i < n; i++){
      if(!(mask >> i & 1)){
	int next = mask | (1 << i);
	ret = min(ret, __builtin_popcount(next & adj[i]) + F(mask | (1 << i)));
      }
    }
    return ret;
  }
  int minChanged(vector <string> spellChart) {
    n = spellChart.size();
    for(int i = 0; i < n; i++){
      adj[i] = 0;
      for(int j = 0; j < n; j++)
	if(spellChart[i][j] == 'Y')
	  adj[i] |= (1 << j);
    }
    memset(dp, -1, sizeof(dp));
    return F(0);
  }
};

良い問題だった。まだすんなりとできる問題ではない。

11月はサボりすぎた。本来は9月いっぱいで554までやるつもりが2ヶ月もオーバーしてしまった。見積りが甘いのもあったが、11月は想像より忙しく時間も取れなかった。レートも少し下がったし。むむ。