Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-11

SRM446 div2 (過去問)

23:58

Hard - HanoiTower

特別ルールのハノイの塔を解く. 3つのペグABCと三種類のディスクabc(最大10枚)がある. ディスクaはペグAに, ディスクbはペグBに, ディスクcはペグCに移動させるには, 最小でなんステップ必要か.

難しい問題でした. まずディスク数が高々10なので, 全探索できないかと予想. 実際, ディスクの移動方法は現在位置意外の2箇所となるので, 組み合わせ数はある程度までで収まりそうな感じがします. よってbfsで探索すればなんとかなりそうかなと思ったんですが, 具体的な計算量がいまいちわからないことと, すでに探索したノード(state)をどう保存するかに悩み, 一旦保留. 次にgreedyに解けるような法則はないかと手計算でいろいろやってみたんですが, いまいち良い戦略が見つかりません. ここでギブアップしてeditorialを見ました.

Login - TopCoder Wiki

editorialではbfsのアプローチを紹介していました. 計算量は (x+y+z+2)!/(2(x!)(y!)(z!)) (x, y, z はディスクa, b, cの枚数. なぜこうなるかはまだ見ていません) とかなり複雑です. 探索済みノードの保存方法としては, 現在のディスクを表現する文字列をハッシュ化するという, わりかし強引な方法を取っていました. なるほど愚直にやるしかないかということで実装したのが下のコードです. ただこれだと遅くて, テストケース4すらまだ通っていません.

ちなみに, この問題はstate space searchの典型的問題だそうです. 以下のwikipediaのページをざっくり読んだ感じだと, 状態をノードにしたグラフを作り, 探索することのようです.

State space search - Wikipedia

class HanoiTower {
public:
  typedef struct state {
    string a;
    string b;
    string c;
  };

  bool equal(state a, state b) {
    if (a.a == b.a && a.b == b.b && a.c == b.c)
      return true;
    return false;
  }

  bool solved(state a) {
    for (int i=0; i<a.a.size(); i++)
      if (a.a[i] != 'A')
        return false;
    for (int i=0; i<a.b.size(); i++)
      if (a.b[i] != 'B')
        return false;
    for (int i=0; i<a.c.size(); i++)
      if (a.c[i] != 'C')
        return false;
    return true;
  }

  state move(state & _s, int from, int to) {
    state s = _s;
    string f;;
    if (from == 0) {
      f = s.a[s.a.size() - 1];
      s.a.erase(s.a.size() - 1);
    } else if (from == 1) {
      f = s.b[s.b.size() - 1];
      s.b.erase(s.b.size() - 1);
    } else if (from == 2) {
      f = s.c[s.c.size() - 1];
      s.c.erase(s.c.size() - 1);
    }

    if (to == 0)
      s.a += f;
    else if (to == 1)
      s.b += f;
    else if (to == 2)
      s.c += f;

    return s;
  }

  typedef pair <string, pair <string, string> > hash;
  hash makeHash(state s) {
    return make_pair(s.a, make_pair(s.b, s.c));
  }

  vector <hash> visited;

  bool isVisited(state s) {
    hash h = makeHash(s);
    for (int i=0; i<visited.size(); i++)
      if (visited[i] == h)
        return true;
    return false;
  }

  bool isEmpty(state &s, int pos) {
    if (pos == 0 && s.a == "")
      return true;
    if (pos == 1 && s.b == "")
      return true;
    if (pos == 2 && s.c == "")
      return true;
    return false;
  }

  int moves(string pegA, string pegB, string pegC) {
    int ret = 0;
    queue <pair <state, int> > q;
    state start;
    start.a = pegA, start.b = pegB, start.c = pegC;
    
    q.push(make_pair(start, 0));
    visited.push_back(makeHash(start));

    while (!q.empty()) {
      pair <state, int> cur = q.front();
      q.pop();

      if (solved(cur.first)) {
        ret = cur.second;
        break;
      }

      for (int i=0; i<3; i++)
        if (!isEmpty(cur.first, i))
          for (int j=0; j<3; j++)
            if (i != j) {
              state next = move(cur.first, i, j);
              if (!isVisited(next)) {
                q.push(make_pair(next, cur.second + 1));
                visited.push_back(makeHash(next));
              }
            }
    }

    return ret;
  }
};