naoya_t@topcoder

SRM420 Div1 Medium: RedIsGood

過去問, 練習 | 18:14 |

昨日DIV1 500points問題を時間オーバーしながら解きつつもTest Case#5の計算が合わない辺りで中断していたところから、試行錯誤の末System Testに通るコードが書けるまでの記。

問題文はこちら。（要TopCoderアカウント）

Scheme脳の恐怖

• 気がつけば、そこまでに引いた赤と黒の差を再帰関数に渡すやり方で書いている。別に間違ってはいないのだけれど、なんとなく末尾再帰脳。（ちなみにこの例では末尾再帰になるわけではない）
• Test Case #5が通らなかったのは、eRかeBが負の場合に枝切りしていた（コメントアウト部分）ため。引いた場合の期待値が引かない場合より良ければ引く、のであればこれは不適切。

class RedIsGood {
private:
  double expected(int curr, int R, int B) {
    if (R + B == 0) return curr;   // (R≧0, B≧0 が分かっているので R = B = 0 の場合)

    double eR = -1.0, eB = -1.0, rR = 0.0, rB = 0.0, eTotal = 0.0;
    if (R > 0) {
      eR = expected(curr+1, R-1, B);
      // if (eR < 0) return curr;
      rR = 1.0 * R / (R + B);
      eTotal += eR * rR;
    }
    if (B > 0) {
      eB = expected(curr-1, R, B-1);
      // if (eB < 0) return curr;
      rB = 1.0 * B / (R + B);
      eTotal += eB * rB;
    }

    return (eTotal > curr) ? eTotal : static_cast<double>( curr );
  }
public:
  double getProfit(int R, int B) {
    return max(expected(0, R, B), 0.0);
  }
};

赤黒それぞれ最大5000枚まで

• 赤、黒それぞれ少ない枚数であればこれで十分解けるのだが、問題文では赤黒各0枚〜5000枚ということになっている。getProfit(5000,5000)は呼んだきりなかなか帰ってこない。TopCoderは制限時間２秒らしい。駄目すぎる。
• とりあえずメモ化してみますか。

その１。

class RedIsGood {
  map<pair<int,int>,double> m;

public:
  double getProfit(int R, int B) {
    if (R == 0) { return 0.0; }
    if (B == 0) { return static_cast<double>(R); }

    if (m.find( make_pair(R,B) ) != m.end()) return m[ make_pair(R,B) ];

    double eR = getProfit(R-1, B) + 1;
    double eB = getProfit(R, B-1) - 1;

    double expected = max((eR*R + eB*B)/(R + B), 0.0);
    
    m[ make_pair(R,B) ] = expected;
    return expected;
  }

• map遅いです。赤黒各5000枚では全然帰ってきません。
• mapだとO(n*log(n))だし、0〜5000までまんべんなく入ると思うのでベタな配列（またはvector）でよいような気が。

というわけでその２。

class RedIsGood {
  double m[5001*5001];

public:
  RedIsGood() {
    for (int i=0;i<=5000;i++)
      for (int j=0;j<=5000;j++)
        m[i*5001 + j] = -1;
  }
  double getProfit(int R, int B) {
    if (R == 0) { return 0.0; }
    if (B == 0) { return static_cast<double>(R); }
    if (m[R*5001+B] >= 0) return m[R*5001+B];

    double eR = getProfit(R-1, B) + 1;
    double eB = getProfit(R, B-1) - 1;
    double expected = max((eR*R + eB*B)/(R + B), 0.0);
    
    m[R*5001+B] = expected;
    return expected;
  }

• segmentation fault で動かない
• double m[5001*5001]が駄目っぽい。

その２（改）。動的確保。

class RedIsGood {
  double *m;
  int m_base;

public:
  double expected(int R, int B) {
    if (R == 0) { return 0.0; }
    if (B == 0) { return static_cast<double>(R); }
    if (m[R*m_base+B] >= 0) return m[R*m_base+B];

    double eR = expected(R-1, B) + 1;
    double eB = expected(R, B-1) - 1;
    double expected = max((eR*R + eB*B)/(R + B), 0.0);
    
    m[R*m_base+B] = expected;
    return expected;
  }
  double getProfit(int R, int B) {
    m = new double[(R+1)*(B+1)];
    m_base = B + 1;
    for (int r=0; r<=R; r++)
      for (int b=0; b<=B; b++)
        m[r*m_base + b] = -1;

    double e = expected(R, B);
    delete[] m;
    return e;
  }

• これでgetProfit(5000,5000)も２秒前後で帰ってくるようになった。
• しかし・・・これを TopCoder で Save - Compile - SystemTest してみると通らない。なんでだろう・・・

メモリは 64MB まで

要はそういうことらしい。作戦変更。

• expected(r,b) は expected(r-1,b) と expected(r,b-1) のみに依存する
• expected(r,0) = r
• expected(0,b) = 0

なので、(R+1) x (B+1) のマトリックスのうち、処理中の行と１つ上の行のみを記憶しておく作戦。これならdoubleを高々10002個持っておくだけで足りる。

その３。

class RedIsGood {
public:
  double getProfit(int R, int B) {
    if (B == 0) return static_cast<double>(R);
    if (R == 0) return 0.0;

    double *last_line = new double[B+1]; // 1つ上 (r-1) の行
    double *curr_line = new double[B+1]; // 処理中の行
    double expected = 0.0;

    for (int b=0; b<=B; b++) last_line[b] = 0;  // r=0 の行。すべて 0

    for (int r=1; r<=R; r++) {
      curr_line[0] = static_cast<double>(r); // expected(r,0) = r

      for (int b=1; b<=B; b++) {
        double eR = last_line[b]   + 1;  // eR = expected(r-1,b  ) + 1
        double eB = curr_line[b-1] - 1;  // eB = expected(r,  b-1) - 1
        curr_line[b] = max((eR*r + eB*b)/(r + b), 0.0);
      }
      if (r == R) { expected = curr_line[B]; break; }

      swap( last_line, curr_line );
    }

    delete[] last_line;
    delete[] curr_line;
    return expected;
  }

• これでようやくSystem Testも通った。
• getProfit(5000,5000)でも所要時間777ms。

一件落着。□

ps

ゲーム慣れした某氏のにっきには

MEDIUM (500pt)

典型的なDP．

2次元配列でドカンとメモリとっちゃうとMLE食らうので1次元で頑張るだけ．

SRM420 DIV1 - ゲームにっき(仮)

とのみ記されていました。

今日の試行錯誤がこんな１、２行のメモに収まる日が来ることを期待。

その他の鉄人たち：

• [TopCoder][SRM]TopCoder SRM 420 Div1 - chokudaiの日記（仮）
• TopCoder SRM 420 Div1 Medium - 西尾泰和のはてなダイアリー
• [contest]TopCoder SRM 420 DIV1 - 総合的な学習のお時間