SRM 470 Div2 Hard ActivateGame

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=10750&rd=14153

数字が書かれたvector stringが与えられる。はじめは左上のみがアクチベートされている。毎ターンアクティブなセルとそれに隣接するアクティブでないセルをひとつずつ選んで、そこに書かれている数字の差の絶対値をそのターンの得点とする。選んだアクティブでないセルはアクティブに変わる。すべてのセルがアクティブになるまでこれを行う。このゲームが終わった時の点数を最大化せよ。

やりかた

どんなかんじでアクティブ化がすすんでいくのかなとなんとなく考えていたら、アクティブでないセルは一回しかアクティブ化されないので、それをすべて追って、つなげていくとすべてのセルに行き渡る一つの木になるということに気づいた。点数は隣接するセル間のエッジコストと置けば、これは木になった時のエッジコストを最大化問題なので、Minimum Spanning Treeの変形版ということになる。

以下ソース。

class ActivateGame {
public:
  int point(char c){
    if(isdigit(c)) return c - '0';
    if(islower(c)) return c - 'a' + 10;
    return c - 'A' + 36;
  }
  int findMaxScore(vector <string> grid) {
    int N = grid.size(), M = grid[0].size();

    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};

    Graph g;
    g.resize(N * M);
    for(int i = 0; i < N; i++){
      for(int j = 0; j < M; j++){
	for(int k = 0; k < 4; k++){
	  int ny = i + dy[k], nx = j + dx[k];
	  if(0 <= ny && ny < N && 0 <= nx && nx < M)
	    g[i * M + j].push_back(edge(i * M + j, 
					ny * M + nx, 
					0, 
					abs(field[ny][nx] - field[i][j])));
	}
      }
    }
    pair<int, vector<edge> > MSP = kruskal(g);
    return MSP.first;
  }
};

これはわりとすぐ思いついてできた。20分くらい。やった。
太閤立志伝Vの開墾師事のミニゲームのことをぼんやり考えていて気づいた。