Single Round Match 407 - 西尾泰和のはてなダイアリー

かなり久しぶりなのでC++忘れたorz
あれどう書くんだっけな、と思いつつ調べる時間が惜しくて愚直にfor文で書いたり。

さてさて、TopCoderに参加した後は、問題文の解説を書きつつ、試合で書いたコードをさらけ出しつつ、満足のいくまできれいに直すのが勉強です(僕にとっては)

今回最初に解いたのは500点問題。「部下のいない社員の給料は１、部下がいる社員の給料は部下の給料の合計、誰が誰の部下かの情報を与えるので全社員の給料の合計を求めよ」という問題。社員数の規模が十分小さいので、再起呼び出しで「Aさんの給料は部下の給料の合計」をそのまんま計算してもOKだろうと思った。

class CorporationSalary {
public:
  vector<string> gxs;
  vector<long long> salary;
  long long totalSalary(vector <string> xs) {
    size_t N = xs.size();
    gxs = xs;
    salary = vector<long long>(N);
    long long total = 0LL;
    for(size_t i=0; i<N; i++){
      total += calc(i);
    }
    return total;
  }

  long long calc(size_t i){
    if(salary[i] != 0) return salary[i];
    size_t N = gxs.size();
    long long sum = 0LL;
    bool has_child = false;
    for(size_t j=0; j<N; j++){
      if(gxs[i][j] == 'Y'){
	sum += calc(j);
	has_child = true;
      }
    }
    if(has_child){
      salary[i] = sum;
      return sum;
    }else{
      salary[i] = 1;
      return 1;
    }
  }
}

すこし書き直してみる。

typedef long long LL;
class CorporationSalary {
public:
  LL totalSalary(vector <string> relations) {
    N = relations.size();
    relations_ = relations;
    salary = vector<LL>(N);
    LL total = 0LL;
    for(size_t i=0; i<N; i++){
      total += calc(i);
    }
    return total;
  }
private:
  size_t N;
  vector<string> relations_;
  vector<LL> salary;
  LL calc(size_t i){
    // already calc'ed
    if(salary[i] != 0) return salary[i];

    LL sum = 0LL;
    bool has_child = false;
    for(size_t j=0; j<N; j++){
      if(relations_[i][j] == 'Y'){
	sum += calc(j);
	has_child = true;
      }
    }
    if(has_child){
      salary[i] = sum;
      return sum;
    }else{
      salary[i] = 1;
      return 1;
    }
  }
}

当初気に入らなかった点は、「社員の関係」を表す引数をパブリックなフィールドにコピーしてしまったところ。最初「shared_ptrだ！」と思い、調べていると時間がなくなるのでリファレンスで渡そうとし、どっちも文法がよくわからなかったのだ。

例えば下のコードだとコピーコンストラクタが2回呼ばれる。

class MyValue {
public:
  MyValue(){
    cout << "cstr" << endl;
  }
  MyValue(const MyValue &x){
    cout << "copy" << endl;
  }
  ~MyValue(){
    cout << "dstr" << endl;
  }
};

class MyClass {
public:
  void foo(MyValue x){
    bar(x);
  }
private:
  void bar(MyValue x){
    
  }
};

int main(){
  MyValue v;
  MyClass c;
  c.foo(v);
}

１回はゲームのルールとして「vectorを値渡しします」と言われている以上仕方がないけど、その後再起呼び出しで何度も呼ぶのに毎回コピーするなんてのはあほっぽいので避けたい。

 private:
-   void bar(MyValue x){
+   void bar(MyValue &x){
     
   }

これでコピーされなくなった。めでたしめでたし。

 private:
-   void bar(MyValue &x){
+   void bar(const MyValue &x){
     
   }

今回は変更されないことがわかっているのでconstをつける。実際のコードを書くときはこうした方がいいんだと思う。間違えて変更しようとしたらコンパイラに怒られるようになる。怒られるのはありがたいことである、怒られるのを不満に思うならもったいないから怒ってやらない、と松下幸之助は言ったとか。

さて、ここまでは前までに勉強したことの復習。ここからが新しいことの勉強。boost::shared_ptrを使いたい。使うとよりよいコードになると思う。http://www.kmonos.net/alang/boost/classes/shared_ptr.html

typedef boost::shared_ptr<MyValue> MyValuePtr;
class MyClass {
public:
  void foo(MyValue x){
    p = MyValuePtr(&x);
    bar();
  }
private:
  MyValuePtr p;
  void bar(){
    
  }
};
-----
実行結果
cstr
copy
dstr
dstr
a.out(5453) malloc: *** error for object 0xbffff9df: Non-aligned pointer being freed
*** set a breakpoint in malloc_error_break to debug
dstr

おっと、ダメだ。そうかー、こういう書き方じゃfooのスコープを抜けた時点でfreeされて、mainのスコープを抜けてcがfreeされる時点でまたfreeされてしまうのか。っていうかスマートなポインタでなくていいということは普通のポインタを使えばいいんじゃないか。

class MyValue {
public:
  MyValue():v(42){
    cout << "cstr" << endl;
  }
  MyValue(const MyValue &x):v(x.v){
    cout << "copy" << endl;
  }
  ~MyValue(){
    cout << "dstr" << endl;
  }
  int v;
};


class MyClass {
public:
  void foo(MyValue x){
    p = &x;
    bar();
  }
private:
  MyValue *p;
  void bar(){
    cout << (*p).v << endl;
  }
};
-----
出力結果
cstr
copy
42
dstr
dstr

なんだ、これでよかったんだ。これがすんなり出てこないあたりいかにポインタを理解していないかがまるわかりだ。

システムテスト終わった。

結局誰一人解けていないとはいえ、1000点問題を誰かに撃墜されてしまったのは悔しい。

さて、500点問題の回答をポインタで書き直すのはおいといて、次は1000点問題。
「細長い廊下状の升目の連なりがあり、通るのに２つのルールでお金を取られる。片方の端からもう片方まで、最も安く行ける方法のうち最も手数のすくないものを調べ、最小コストと最小手数の対を答えよ。回答がない場合もある。ルール１：それぞれの升目には『升目の値段』がある。人は一つ先の升目に代金を払って進むことができる。ただし升目の値段が-1の場合は進入禁止。ルール２：マップにはいくつかのワープゲートがある。人はワープゲートの入り口がある升目にいる場合は出口へワープすることができる。そのときにはワープ代を支払う。ワープ代はワープをするたびに1ずつ上がる。この場合も-1のますには入れない。」
厳密さをのぞいて簡潔に説明しようとしたけどそれでもこんな感じ。

まずは投稿したそのままのコード

class CheapestRoute {
public:
  vector <int> routePrice(vector <int> cellPrice, vector <int> enterCell, vector <int> exitCell, int teleportPrice) {
    vector<int> position;
    position.push_back(0);
    vector<int> cost;
    cost.push_back(0);
    vector<int> num_warp;
    num_warp.push_back(0);

    vector<int> candidate_step;
    vector<int> candidate_cost;
    vector<int> next_pos;
    vector<int> next_cost;
    vector<int> next_warp;
    int min_cost = 1 << 30;
    cout << min_cost << endl;

    size_t N = cellPrice.size();
    size_t GOAL = N - 1;
    cout << "GOAL:" << GOAL  << endl;
    int step = 0;
    while(!position.empty()){
      //cout << "---------------" << endl;
      for(size_t i=0; i < position.size(); i++){
	int p = position[i];
	int c = cost[i];
	//	cout << "p:" << p << "c:" << c  << endl;
	if(p == GOAL){
	  candidate_cost.push_back(c);
	  candidate_step.push_back(step);
	  if(c < min_cost){
	    min_cost = c;
	  }
	  continue;
	}
	if(c >= min_cost) continue;

	// if next cell is not -1, you can walk into it
	if(cellPrice[p + 1] != -1){
	  next_pos.push_back(p + 1);
	  next_cost.push_back(c + cellPrice[p + 1]);
	  next_warp.push_back(num_warp[i]);
	}
	
	// if you can enter
	int exit = 0;
	for(size_t j=0; j < enterCell.size(); j++){
	  if(enterCell[j] == p){
	    exit = exitCell[j];
	    if(cellPrice[exit] == -1) continue;
	    int w = num_warp[i];
	    next_pos.push_back(exit);
	    next_cost.push_back(c + teleportPrice + w);
	    next_warp.push_back(w + 1);
	  }
	}

      }
      position = next_pos;
      cost = next_cost;
      num_warp = next_warp;
      next_pos.clear();
      next_cost.clear();
      next_warp.clear();
      step++;
    }

    cout << "hoge" << endl;
    vector<int> result;
    if(candidate_step.empty()) return result;
    cout << candidate_step[0] << endl;
    int min_step = 1 << 30;
    for(size_t i=0; i<candidate_step.size(); i++){
      int c = candidate_cost[i];
      int s = candidate_step[i];
      //cout << c << ", ";
      //cout << s << endl;
      if(c == min_cost){
	if(s < min_step){
	  min_step = s;
	}
      }
    }
    result.push_back(min_cost);
    result.push_back(min_step);
    return result;
  }
}

あ、安西先生、タプルが使いたいです... RubyのstructでもOK。というわけでとりあえずstruct... というかclassを使ってみる。

class State {
public:
  State():position(0),cost(0),warp(0){}
  size_t position;
  int cost;
  int warp;
};

class Candidate {
public:
  int step;
  int cost;
};

class CheapestRoute {
public:
  vector <int> routePrice(vector <int> cellPrice, vector <int> enterCell, vector <int> exitCell, int teleportPrice) {
    State start;
    vector<State> states;
    states.push_back(start);
    vector<State> next_states;
    vector<Candidate> candidates;

    int min_cost = 1 << 30;
    size_t N = cellPrice.size();
    size_t GOAL = N - 1;

    int step = 0;
    while(!states.empty()){
      for(size_t i=0; i < states.size(); i++){
	State cur(states[i]);
	size_t p = cur.position;
	int c = cur.cost;
	if(p == GOAL){
	  Candidate cand;
	  cand.cost = c;
	  cand.step = step;
	  if(c < min_cost){
	    min_cost = c;
	  }
	  candidates.push_back(cand);
	  continue;
	}
	if(c >= min_cost) continue;

	// if next cell is not -1, you can walk into it
	if(cellPrice[p + 1] != -1){
	  State next(cur);
	  next.position++;
	  next.cost += cellPrice[p + 1];
	  next_states.push_back(next);
	}
	
	// if you can enter
	int exit = 0;
	for(size_t j=0; j < enterCell.size(); j++){
	  if(enterCell[j] == p){
	    exit = exitCell[j];
	    if(cellPrice[exit] == -1) continue;
	    State next(cur);
	    next.position = exit;
	    next.cost += teleportPrice + cur.warp;
	    next.warp++;
	    next_states.push_back(next);
	  }
	}

      }
      states = next_states;
      next_states.clear();
      step++;
    }

    vector<int> result;
    if(candidates.empty()) return result;
    int min_step = 1 << 30;
    for(size_t i=0; i<candidates.size(); i++){
      int c = candidates[i].cost;
      int s = candidates[i].step;
      if(c == min_cost){
	if(s < min_step){
	  min_step = s;
	}
      }
    }
    result.push_back(min_cost);
    result.push_back(min_step);
    return result;
  }
}

だいぶ読みやすくなったね。全部publicなのならclassである意味がないのではないか、と思わなくもないけど。

あとは 1 << 30 がださいと思うので

#define __STDC_LIMIT_MACROS
#include<iostream>
using namespace std;

#include<boost/cstdint.hpp>
(中略)
using namespace boost;


(中略)
    int32_t min_cost = INT32_MAX;

INT32_MAXを使うには#define __STDC_LIMIT_MACROSが必要だってのは知らなかった。

それから、boost/assignも使う。

-    result.push_back(min_cost);
-    result.push_back(min_step);
+    result += min_cost, min_step;

代入したらコピーされてもったいないのでswapにしてみる。

-      states = next_states;
+      states.swap(next_states);

これも無駄なコピーだよね。どうしよう。

for(size_t i=0; i < states.size(); i++){
  State cur(states[i]);

こう？

for(vector<State>::iterator cur = states.begin(), end = states.end(); cur != end; ++i){

ダメだ、後でワープの計算をするときにiが必要になるからイテレータには変えられない。

for(size_t i=0; i < states.size(); i++){
  State *cur = &(states[i]);
  size_t p = cur->position;
  int c = cur->cost;

こうかなぁ。なんか &(states[i]) が野暮ったい気がする。

お、レーティングが更新された。1問しか解けていないけど上がった。

- - - -

さて、1000点問題がなぜfailしたか。
まずこんな入力：{0, 0, -1}, {0, 1}, {1, 0}、ゴールしたらそのスコアで足切りをするようにはしてあるけど、この例みたいにゴールできない問題の場合はワープし続けて無限ループ。あるセルにコストnで到達できるなら、コストがnより大きい方法でたどり着いても先を探索する必要はない。だって最小コストになり得ないから。本当にそうか？違うな。ワープの回数によってワープのコストがかわるから一概にはそういえないな。例えば最後の一歩がワープでしか無理な道で、ワープのコストが0で、歩いてくると4、ワープだと3回飛んで3のコストで残り1歩まで近づけるとしよう。これ正解は歩いてきてコスト0で飛ぶ方法であって、4回飛ぶ方法ではない。うーん、難しいぞ。

とりあえず、コストとワープ回数の両方が今まで以上の場合はcontinueするようにしてみてテストを通るかどうか試してみよう。

だめだ、それでも1個落ちる。しかも答えた最小コストが間違っているというトラップ。上の枝刈りをしたときに刈りすぎるケースだなぁ、きっと。うーん、何が間違っているだろう。