Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2009-11-26

Single Round Match 453.5 @ TopCoder 16:00 Single Round Match 453.5 @ TopCoder - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Single Round Match 453.5 @ TopCoder - nodchipのTopCoder日記 Single Round Match 453.5 @ TopCoder - nodchipのTopCoder日記 のブックマークコメント

Single Round Match 453.5 @ TopCoderの参加記録です。

Easy 250 MazeMaker

二次元迷路が与えられる。主人公は自分のいるセルから入力で与えられる方向に移動することが出来る。何回か移動してそれぞれのセルに移動するとき、最大で何回移動するか求めよ。全てのセルに到達できない場合は-1を出力せよ。

幅優先探索ですね。Easyで幅優先探索が出るのは珍しいと思います。

class MazeMaker {
public:
  int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol) {
    const int height = maze.size();
    const int width = maze[0].size();
    int dp[64][64];
    fill_n((int*)dp, 64 * 64, INT_MAX / 2);

    deque<pair<int, int> > q;
    q.push_back(make_pair(startRow, startCol));
    dp[startRow][startCol] = 0;
    while (!q.empty()) {
      const int row = q.front().first;
      const int column = q.front().second;
      q.pop_front();
      const int currentCost = dp[row][column];
      for (int dir = 0; dir < moveRow.size(); ++dir) {
        const int nextRow = row + moveRow[dir];
        const int nextColmn = column + moveCol[dir];
        if (nextRow < 0 || height <= nextRow || nextColmn < 0 || width <= nextColmn) {
          continue;
        }

        if (maze[nextRow][nextColmn] == 'X') {
          continue;
        }

        if (dp[nextRow][nextColmn] <= currentCost + 1) {
          continue;
        }

        dp[nextRow][nextColmn] = currentCost + 1;
        q.push_back(make_pair(nextRow, nextColmn));
      }
    }

    int result = 0;
    for (int row = 0; row < height; ++row) {
      for (int column = 0; column < width; ++column) {
        if (maze[row][column] == '.' && dp[row][column] == INT_MAX / 2) {
          result = INT_MAX / 2;
          continue;
        }

        if (dp[row][column] == INT_MAX / 2) {
          continue;
        }

        result = max(result, dp[row][column]);
      }
    }

    if (result == 0 || result == INT_MAX / 2) {
      result = -1;
    }

    return result;
  }
};

Middle 450 PlanarGraphShop

平面グラフを売ってくれるお店がある。G=(V,E)としたとき、Gのコストは|V|^3+|E|^2である。丁度Nのコストを支払わせたいとき、最低何個の平面グラフを売ればよいか求めよ。N<=50000とする。

Planer Graphという単語を久々に聞いた気がします。日本語訳は平面グラフだったかなぁなどと思い出しながらGoogle先生に御伺いを立てたところ、ヒットしてくれました。ヒット先のWikipedia先生によると|E|<3|V|-6 (|V|>=3)という定理があるそうです。N<=50000なので、売ることが出来るグラフの値段を全て列挙して幅優先探索をしました。

class PlanarGraphShop {
public:
  int bestCount(int N) {
    set<int> items;
    items.insert(1);
    items.insert(2 * 2 * 2);
    items.insert(2 * 2 * 2 + 1 * 1);
    for (int v = 3; v * v * v <= 50000; ++v) {
      for (int e = 0; e <= 3 * v - 6 && v * v * v + e * e <= 50000; ++e) {
        items.insert(v * v * v + e * e);
      }
    }

    vector<int> items2(items.begin(), items.end());

    static int dp[64 * 1024];
    fill_n(dp, 64 * 1024, INT_MAX / 2);
    dp[0] = 0;
    deque<int> q;
    q.push_back(0);
    while (!q.empty()) {
      const int current = q.front();
      const int cost = dp[current];
      q.pop_front();

      for (vector<int>::iterator it = items2.begin(); it != items2.end(); ++it) {
        const int next = current + *it;
        if (next > 50000) {
          break;
        }
        if (dp[next] > cost + 1) {
          dp[next] = cost + 1;
          q.push_back(next);
        }
      }
    }

    int result = dp[N];
    return result;
  }
};

Hard 1000 TheAlmostLuckyNumbers

4と7のみからなる数字をラッキーナンバーと呼ぶ。ラッキーナンバーの倍数を多分ラッキーナンバーなんじゃないかなと思うことにする。欄キーナンバー自体も多分ラッキーナンバーなんじゃないかなと思うことにする。a以上b以下の多分ラッキーナンバーなんじゃないかな的な数の個数を求めよ。

倍数をカウントしたり引いたりすればいいんじゃねと思ってそれっぽい探索コードを書いたのですが、ぜんぜん違ってました。ラッキーナンバーはしばらく解けそうにありません。

撃墜フェーズ

Easyで(0, 0)でバグる人いないかなぁと期待していたのですが、いませんでした。

システムテスト

o x x 132位 1754->1822 全うな順位だったように思います。

総評

普通だったように思います。450の早解き勝負についていけなかったのは実力不足ということでしょう。

Single Round Match 453.5 @ TopCoder 16:00 Single Round Match 453.5 @ TopCoder - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Single Round Match 453.5 @ TopCoder - nodchipのTopCoder日記 Single Round Match 453.5 @ TopCoder - nodchipのTopCoder日記 のブックマークコメント

Single Round Match 453.5 @ TopCoderの参加記録です。

Easy 250 MazeMaker

二次元迷路が与えられる。主人公は自分のいるセルから入力で与えられる方向に移動することが出来る。何回か移動してそれぞれのセルに移動するとき、最大で何回移動するか求めよ。全てのセルに到達できない場合は-1を出力せよ。

幅優先探索ですね。Easyで幅優先探索が出るのは珍しいと思います。

class MazeMaker {
public:
  int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol) {
    const int height = maze.size();
    const int width = maze[0].size();
    int dp[64][64];
    fill_n((int*)dp, 64 * 64, INT_MAX / 2);

    deque<pair<int, int> > q;
    q.push_back(make_pair(startRow, startCol));
    dp[startRow][startCol] = 0;
    while (!q.empty()) {
      const int row = q.front().first;
      const int column = q.front().second;
      q.pop_front();
      const int currentCost = dp[row][column];
      for (int dir = 0; dir < moveRow.size(); ++dir) {
        const int nextRow = row + moveRow[dir];
        const int nextColmn = column + moveCol[dir];
        if (nextRow < 0 || height <= nextRow || nextColmn < 0 || width <= nextColmn) {
          continue;
        }

        if (maze[nextRow][nextColmn] == 'X') {
          continue;
        }

        if (dp[nextRow][nextColmn] <= currentCost + 1) {
          continue;
        }

        dp[nextRow][nextColmn] = currentCost + 1;
        q.push_back(make_pair(nextRow, nextColmn));
      }
    }

    int result = 0;
    for (int row = 0; row < height; ++row) {
      for (int column = 0; column < width; ++column) {
        if (maze[row][column] == '.' && dp[row][column] == INT_MAX / 2) {
          result = INT_MAX / 2;
          continue;
        }

        if (dp[row][column] == INT_MAX / 2) {
          continue;
        }

        result = max(result, dp[row][column]);
      }
    }

    if (result == 0 || result == INT_MAX / 2) {
      result = -1;
    }

    return result;
  }
};

Middle 450 PlanarGraphShop

平面グラフを売ってくれるお店がある。G=(V,E)としたとき、Gのコストは|V|^3+|E|^2である。丁度Nのコストを支払わせたいとき、最低何個の平面グラフを売ればよいか求めよ。N<=50000とする。

Planer Graphという単語を久々に聞いた気がします。日本語訳は平面グラフだったかなぁなどと思い出しながらGoogle先生に御伺いを立てたところ、ヒットしてくれました。ヒット先のWikipedia先生によると|E|<3|V|-6 (|V|>=3)という定理があるそうです。N<=50000なので、売ることが出来るグラフの値段を全て列挙して幅優先探索をしました。

class PlanarGraphShop {
public:
  int bestCount(int N) {
    set<int> items;
    items.insert(1);
    items.insert(2 * 2 * 2);
    items.insert(2 * 2 * 2 + 1 * 1);
    for (int v = 3; v * v * v <= 50000; ++v) {
      for (int e = 0; e <= 3 * v - 6 && v * v * v + e * e <= 50000; ++e) {
        items.insert(v * v * v + e * e);
      }
    }

    vector<int> items2(items.begin(), items.end());

    static int dp[64 * 1024];
    fill_n(dp, 64 * 1024, INT_MAX / 2);
    dp[0] = 0;
    deque<int> q;
    q.push_back(0);
    while (!q.empty()) {
      const int current = q.front();
      const int cost = dp[current];
      q.pop_front();

      for (vector<int>::iterator it = items2.begin(); it != items2.end(); ++it) {
        const int next = current + *it;
        if (next > 50000) {
          break;
        }
        if (dp[next] > cost + 1) {
          dp[next] = cost + 1;
          q.push_back(next);
        }
      }
    }

    int result = dp[N];
    return result;
  }
};

Hard 1000 TheAlmostLuckyNumbers

4と7のみからなる数字をラッキーナンバーと呼ぶ。ラッキーナンバーの倍数を多分ラッキーナンバーなんじゃないかなと思うことにする。欄キーナンバー自体も多分ラッキーナンバーなんじゃないかなと思うことにする。a以上b以下の多分ラッキーナンバーなんじゃないかな的な数の個数を求めよ。

倍数をカウントしたり引いたりすればいいんじゃねと思ってそれっぽい探索コードを書いたのですが、ぜんぜん違ってました。ラッキーナンバーはしばらく解けそうにありません。

撃墜フェーズ

Easyで(0, 0)でバグる人いないかなぁと期待していたのですが、いませんでした。

システムテスト

o x x 132位 1754->1822 全うな順位だったように思います。

総評

普通だったように思います。450の早解き勝負についていけなかったのは実力不足ということでしょう。

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20091126
 |