SRM 553 Div II

Single Round Match 553 Round 1

http://community.topcoder.com/stat?c=round_overview&er=5&rd=15175

250に7分。500も54分で提出したが、システムテストで落ちた。写経ミスでチャレンジ1回失敗。合計210.74点。レートは1123から1111へ。緑コーダー。Room 61

Problem Status Points
250 PlatypusDuckAndBeaver System Test Passed 227.00
550 Suminator Failed System Test 0.00
1000 SafeRemoval Unopened
  • 250に7分。235.74点
  • 500に54分。226.44点。システムテストで落ちた
    • メモに残していないが30分ほどで完成し、残りの時間を検証にあてた
  • 写経ミスにより、チャレンジ1回失敗
  • 合計210.74点
    • レートも落ちた
  • 次回の目標
    • 2問通す

PlatypusDuckAndBeaver

http://community.topcoder.com/stat?c=problem_statement&pm=12169&rd=15175

7分。235.74点

  • 連立方程式を立てて解く
    • ヒル、ビーバー、カモノハシの数をそれぞれnD、nB、nPと置く
    • 足、くちばし、しっぽの総数をそれぞれnf、nb、ntと置く

実装は以下(システムテスト済)。

class PlatypusDuckAndBeaver {
public:
  int minimumAnimals(int webbedFeet, int duckBills, int beaverTails) {
    int nd = (webbedFeet - beaverTails * 4) / 2;
    int np = duckBills - nd;
    int nb = beaverTails - np;

    return nd + np + nb;
  };
};
  • 今考えれば、全探索してもよかった

実装は以下(システムテスト済)。

class PlatypusDuckAndBeaver {
public:
  int minimumAnimals(int webbedFeet, int duckBills, int beaverTails) {
    for (int i = 0; i <= 1000; i ++)
      for (int j = 0; j <= 1000; j ++)
        for (int k = 0; k <= 1000; k ++)
          if (i * 4 + j * 2 + k * 4 == webbedFeet &&
              i     + j             == duckBills  &&
              i             + k     == beaverTails)

            return i + j + k;

    return -1;
  };
};
  • なかなか全探索する発想にならない...
  • 解析的に解く場合と、全探索で解く場合の両方を考えた上で選択したい
    • この問題だと計算量が109であるので少し戸惑うが、nD、nB、nPの範囲が[1, 100]であれば、迷わず全探索を選ぶような気がする

Suminator

http://community.topcoder.com/stat?c=problem_statement&pm=11354&rd=15175

30分ほどで実装終了。20分ほど検証に費やしてから提出。54分。226.44点。システムテストで落ちた。

  • まずシミュレータを書いた
    • 初めにintを用いて実装したのはまずかった
  • 二部探索を用いた実装が出来そうに思った
    • しかし、Suminatorが単調増加関数であるかどうか確信が持てなかった
  • シミュレータから標本を抽出し、Gnuplotにて描画した
    • 範囲を[1, 109]とし、テストケース毎に1024個標本抽出した(図は64個標本抽出した例)


  • SRM参戦中にGnuplotを使ったのは初めてだったが、有用であった
  • しかし、シミュレータでの計算がオーバーフローしていることに気付かなかった(!)
    • 単調増加関数であるか否かのみに注目し、見逃してしまった
  • 以下はSRM後にシミュレータを修正し、出力した結果だ


  • 大きく2つのパターンに分けられることが分かった
    • 線形的に大きくなる
    • 定数になる
  • またテストケースを試すことで、0を使った場合は特殊であることに気付いた
    • まず0を使ってテストし、成立しない場合は探索すればよい
  • 二分探索を書いた
    • テストはうまく通っている...
    • この時点で30分ほど
  • コードを見直す
    • シミュレータはlong longを用いたほうがよさそうに思えた
    • 書き直した
  • 提出した
  • システムテストで落ちた
  • 3つ失敗があった
  • シミュレータがlong longに移植しきれていなかった
    • std::stack.top()の戻り値をintで受けていた
  • check関数の戻り値をintで受けていた
    • check関数の戻り値は検証する値との差である
    • 途中から、(何らかの負の値、0、何らかの正の値)を取るもの、
    • さらに(-1, 0, 1)を取るもの、くらいの認識で進めてしまった
      • そのため、ここでオーバーフローとアンダーフローを起こすことは全く予想していなかった
  • 整数を扱うのに適した二部探索ではなかった
    • 実数を扱うように実装してしまった
    • この実装は1,000,000,000を見つけることができない
      • l = 999,999,999、r = 1,000,000,000からl = 1,000,000,000、r = 1,000,000,000に遷移しないのだ
  int l = 1, r = 1000000000;
    
  for (int i = 0; i < 256; i ++) {
    int m = (l + r) / 2;

    int c = check(program, wantedResult, m);
      
    if (c == 0) {
      return m;
    }
    else if (c < 0) {
      r = m;
    }
    else {
      l = m;
    }
  }
  • 今回は整数を扱うのに適した二部探索を考察する
  • 以下の実装はアルゴリズムC 第2巻の14章、「初等的な探索法」からの抜粋だ
int binarysearch(int v)
  {
    int l = 1; int r = N; int x;
    while (r >= l)
      {
        x = (l+r)/2;
        if (v < a[x].key) r = x-1; else l = x+1;
        if (v == a[x].key) return a[x].info;
      }
    return -1;
  }
int binarysearch(DataType t)
{
    int l, u, m;
    l = 0;
    u = n-1;
    while (l <= u) {
        m = (l + u) / 2;
        if (x[m] < t)
            l = m+1;
        else if (x[m] == t)
            return m;
        else /* x[m] > t */
            u = m-1;
    }
    return -1;
}


  • また、上限下限の何れを更新する場合にもmを含まない範囲とする


  • 無限ループを防ぐ副作用もありそうだ
    • 区間に変化を与えれば無限ループが起こり辛い、と覚えるといいかもしれない
    • なんかメトロポリス法っぽい(全然違うが)

では、ここまでの考察を元にリファクタリングする(システムテストをパス)。

class Suminator {
public:
  int findMissing(std::vector<int> program, int wantedResult) {
    if (compute(program, 0) == wantedResult)
      return 0;

    int l = 1, u = 1000000000;

    while (l <= u) {
      int m = (l + u) / 2;
      
      long long x = compute(program, m);

      if (x == wantedResult) {
    	return m;
      }
      else if (wantedResult < x) {
    	u = m - 1;
      }
      else {
    	l = m + 1;
      }
    }
    return -1;
  };

private:
  long long compute(std::vector<int> program, long long m) const {
    std::stack<long long> stack(std::deque<long long>(100, 0));

    *std::find(ALL(program), -1) = m;

    for (int i = 0, size = program.size(); i < size; i ++) {
      if (program[i] == 0) {
	long long a = stack.top(); stack.pop();
	long long b = stack.top(); stack.pop();

	stack.push(a + b);
      }
      else {
	stack.push(program[i]);
      }
    }
    return stack.top();
  };
};
  • check関数からcompute関数に変更した
    • 与えられた数値とシミュレーションの結果の差を返す関数ではなく、シミュレーションの結果の値そのもを返す関数にした
    • 関数の戻り値に曖昧さがなくなった
      • そのため、実装がより明瞭になったように思う
  • 今回は整数の二分探索を考察した
  • もう一度ポイントをまとめる
    • 区間とすること
    • 区間を更新する場合にmを含めないこと
    • 値を渡してチェックする関数を用意するよりも、値をそのまま返す関数を用意したほうが有利な場合もあること
  • 二分探索を考察する際に参考にした書籍は以下だ

アルゴリズムC〈第2巻〉探索・文字列・計算幾何

アルゴリズムC〈第2巻〉探索・文字列・計算幾何

珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造

珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造