Single Round Match 408 Div1 500pt

TopCoder

難しい。なんとかsubmitしたけど190点。そしてシステムテストに落ちるな。あー、例のごとく処理時間超過だ。


問題の内容とかは後で書くことにして家に帰ろうかなぁ。


追記{
http://www.topcoder.com/stat?c=problem_statement&pm=8462&rd=12180
おおざっぱに説明すると「ループのない無向グラフのゲーム盤があって、おのおののマスにいくつかの玉をおくことができる。二つ以上の玉があるマスがあれば、そこから2つの玉を取って、隣接するマスに1個の玉をおくことができる。自分は最初に玉を配置する役。なるべくたくさん玉をおきたいが、targetで示された特定のマスに玉をおかれると負け。負けない最大限における玉の個数を求めよ」という感じ。

例えば 0-1-2 というゲーム盤でtargetが1の場合、おける玉の個数は{1, 0, 1}で合計2個となる。なぜかというと、例えば0の所にもう一個玉をおくと「2個以上」になるので、プレイヤーがそれを取って1に玉をおくことができてしまうから。targetが2の時は{3, 0, 0}の3個になる。0から2個とって1に1個おかれるけど、2に置かれることはないから。

おなかがすいたので「an acyclic, undirected graph」の意味と、この問題ではtargetを根とするツリーを考えればいいってあたりの説明はご飯を食べて気が向いたら書く。
}

  vector<int> dist;
  int N;
  vector<string> *gr; // graph
  vector<vector<int> > tree;

  void spawn(int t){
    int next = dist[t] + 1;
    string line((*gr)[t]);
    for(int i=0; i<N; i++){
      if(line[i] == 'N') continue;
      if(dist[i] == 0 || dist[i] > next){
	dist[i] = next;
	tree[t] += i;
	spawn(i);
      }
    }
  }

  int calc_max(int pos, int ulimit){
    vector<int> xs(tree[pos]); // children
    if(tree[pos].empty()){
      return ulimit;
    }
    int max = 0;
    size_t M = xs.size();
    
    for(size_t i=0; i<M; i++){
      int max_ = 0;
      for(size_t j=0; j<M; j++){
	if(i == j){
	  max_ += calc_max(xs[j], ulimit * 2 + 1);
	}else{
	  max_ += calc_max(xs[j], 1);
	}
      }
      if(max_ > max) max = max_;
    }
    //cout << "max:" << pos << ", " << ulimit << " = " << max << endl;
    return max;
  }

public:
  int maximumCandy(vector <string> graph, int target) {
    N = graph.size();
    gr = &graph;
    dist.clear();
    dist.resize(N);
    tree.clear();
    tree.resize(N);
    dist[target] = 1;
    spawn(target); // calc distance from target (plus 1, to use 0 as 'not calc.d yet')
    // fail if the graph has two or more components
    // fail if dist > 31, 2 ** (32 - 1) is greater than 2,000,000,000
    for(int i=0; i<N; i++){
      if(dist[i] == 0) return -1;
      if(dist[i] > 31) return -1;
      dist[i]--;
    }

    //for(int i=0; i<N; i++){
    //  cout << "tree[i]: "; iter_print(tree[i].begin(), tree[i].end());
    //}
    
    return calc_max(target, 0);
  }

時間はかった。20.8秒掛かってた。これを2秒におさめないと行けないんだな。

とりあえずcalc_maxの中で面倒なのでコピーしているxsのところをコピーしないようにポインタにしてみた。6.8秒に縮んだ。さて、次はどこをどうするか。。。

calc_maxのなかの二重ループをつぶすか。

// before
    for(size_t i=0; i<M; i++){
      int max_ = 0;
      for(size_t j=0; j<M; j++){
	if(i == j){
	  max_ += calc_max((*xs)[j], ulimit * 2 + 1);
	}else{
	  max_ += calc_max((*xs)[j], 1);
	}
      }
      if(max_ > max) max = max_;
    }
//after
    vector<int> children_max(M);
    for(size_t i=0; i<M; i++){
      children_max[i] = calc_max((*xs)[i], 1);
    }
    for(size_t i=0; i<M; i++){
      int max_ = 0;
      max_ = calc_max((*xs)[i], ulimit * 2 + 1) - children_max[i];
      if(max_ > max) max = max_;
    }
    return accumulate(children_max.begin(), children_max.end(), max);

ok, 0.50秒になった。submit & test。うー、今度は別のテストに引っかかった。グラフを見てみると、、細長い１本道。ああ、候補が1個しかないときでも上のコードだと2回呼んでいるから2 ** 30くらい計算するはめになるのか。

    if(xs->size() == 1){
      return calc_max((*xs)[0], ulimit * 2 + 1);
    }

これを補ったらやっと全部のテストが通った。ふう、今の実力じゃ一軍に行っても250点問題を解けるか解けないかってところだなぁ。


今回の教訓：再起呼び出しされる関数は、可能な限り複数回自分を呼ばないようにする。