Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-17

SRM383 div2 (過去問)

17:01

Easy - FloorLayout

"-"か"|"から構成される二次元配列が与えられる. 縦横につながっている"-", "|"をカウントする.

そのままストレートに解いたんですが, 途中添字をまちがえて時間をロスしました.

class FloorLayout {
   public:
   int countBoards(vector <string> layout) {
      int ret = 0;
      bool visited[layout.size()][layout[0].size()];
      memset(visited, false, sizeof(visited));

      for (int i=0; i<layout.size(); i++)
        for (int j=0; j<layout[0].size(); j++)
          if (!visited[i][j]) {
            ret++;
            char cur = layout[i][j];
            int dir1 = 0;
            int dir2 = 1;
            if (layout[i][j] == '|')
              dir1 = 1, dir2 = 0;

            int x = i, y = j;
            while (0 <= x && x < layout.size() && 0 <= y && y < layout[0].size() && 
                   layout[x][y] == cur) {
              visited[x][y] = true;     // ここの添字をi, j にしていた
              x += dir1, y += dir2;
            }
          }

      return ret;
  }
};

Medium - Planks

いろいろな長さの板が与えられる. 板を全部同じ長さに切って, できるだけ高く売りたい. 板を切るのには一回あたり costPerCut のコストがかかる. また板の切れ端は捨てる. 利益の最大値を求めよ.

板の長さが最大10000なので, 基本的には1から10000までのすべての切り方をしらべて, 利益の最大値を返します. ここまでで最後のテストケース意外は通ると思います. 最後のテストケースは, 板を全く切らないで捨てるという場合を考慮しなくちゃいけません. よって各板について切るコストと売って得られる利益を比べ, 利益が出ていなければスルーします.

あとeditorialを見て感心したのが, 切った回数の求め方です. 例えば長さ10の板を長さ5の部分に切り分けるとき, 10 / 5 - 1 = 1 で, 一回だけ切ります. また12の板を5で切り分けるときは, floor(12 / 5) = 2 で, 二回切ります. このようにもし板の長さが切り分ける長さで割り切れた場合は回数を-1するという方法を最初は取っていたんですが, これは (板の長さ-1) / (切り分ける長さ) とすればできます. これはスマートだし, 他の場面でも使えそうです.

class Planks {
public:
  int makeSimilar(vector <int> lengths, int costPerCut, int woodValue) {
    int ret = 0;

    for (int i=1; i<=10000; i++) {
      int profit = 0;
      for (int j=0; j<lengths.size(); j++) {
        int number_of_plank = lengths[j] / i;
        int number_of_cut = (lengths[j] - 1) / i;
        if (number_of_plank * i * woodValue > number_of_cut * costPerCut)
          profit +=number_of_plank * i * woodValue - number_of_cut * costPerCut;
      }
      ret = max(ret, profit);
    }

    return ret;
  }
};

Hard - HillWalker

グリッド状のマップ(各セルはその場所の標高)とセル間の移動時間の計算式が与えられる. スタート地点(0, 0)から出発し, 最終的にはまたスタート地点に戻ってこないといけない. 制限時間が与えられるので, それ以内に最も高いところまで行きたい. 最大標高いくつまでいけるか.

経路の計算を行きと帰りで分割して考えました. まずスタート地点から他のすべてのセルへの最短経路を求めます. 次にすべてのセルからスタート地点への最短経路を求めます. 最後に行き帰り両方の経過時間が制限時間以内で, かつ標高が最も高いものを返します. 最短経路の計算にはdijkstara法を用います.

まだバグが残っているんですが, 時間切れのため一旦やめました. あとでデバッグするつもりです. editorialを少しだけ見たところ, 方針はあっているようなので良かったです.

今まで div2 hard の問題を解いてきて思ったのが, 大体の問題はdpかグラフのいずれかだということです. 感覚的にはdpが出る割合がすこし多いかなと感じています. グラフの問題は少しずつですが, アルゴリズムの方針が立てられるようになってきました. ただ実装するスピードが遅く, 本番ではまだ間に合いそうにありません. もっと手を動かして問題に慣れる, あるいは探索などの定型的なコードをライブラリ化・テンプレートを作るなどの工夫が必要かもしれません. dpの問題はまだまだ回答の方針をたてるのも難しい状況です. 特に集中力が落ちてる時にはまったく歯が立ちません. 午前中の脳が冴えている時間帯に練習したり, 本で典型的なパターンを集めるなどが必要かもしれません.

class HillWalker {
public:
  vector <string> land;
  int th;
  long long times[25][25][2];
  typedef vector <int> node;
  map <char, int> alphabet;

  node make_node(int cost, int x, int y) {
    vector <int> tmp(3, 0);
    tmp[0] = cost, tmp[1] = x, tmp[2] = y;
    return tmp;
  }

  bool isInRange(int x, int y) {
    if (0 <= x && x < land.size() && 0 <= y && y < land[0].size())
      return true;
    return false;
  }

  long long calcTime(int startx, int starty, int goalx, int goaly) {
    if (isInRange(startx, starty) && isInRange(goalx, goaly) &&
        abs(startx - starty) + abs(goalx - goaly) == 1) {
      long long diff = alphabet[land[goalx][goaly]] - alphabet[land[startx][starty]];

      if (abs(diff) > th)
        return INT_MAX;
      if (diff < 1)
        return 1;
      else
        return diff*diff;
    }
    return INT_MAX;
  }

  int dijk(int startx, int starty, int goalx, int goaly, int flg) {
    bool visited[land.size()][land[0].size()];
    priority_queue <node> q;
    int dirx[4] = {1, 0, -1, 0};
    int diry[4] = {0, 1, 0, -1};
    long long paths[land.size()][land[0].size()];
    memset(visited, false, sizeof(visited));
    memset(paths, 1000000, sizeof(paths));

    q.push(make_node(0, startx, starty));

    while (!q.empty()) {
      int cur_cost = 0, cur_x = 0, cur_y = 0;
      node cur = q.top();
      q.pop();
      cur_cost = cur[0], cur_x = cur[1], cur_y = cur[2];
      visited[cur_x][cur_y] = true;

      if (cur_x == goalx && cur_y == goaly)
        break;

      for (int i=0; i<4; i++) {
        int next_x = cur_x + dirx[i];
        int next_y = cur_y + diry[i];
        if (isInRange(next_x, next_y) && !visited[next_x][next_y]) {
          int time = calcTime(cur_x, cur_y, next_x, next_y);
          if (time == INT_MAX) continue;
          if (paths[next_x][next_y] > cur_cost + time) {
            paths[next_x][next_y] = cur_cost + time;
            q.push(make_node(cur_cost + time, next_x, next_y));
          }
        }
      }
    }

    if (flg == 1)
      times[startx][starty][flg] = paths[goalx][goaly];
    else
      for (int i=0; i<land.size(); i++) 
        for (int j=0; j<land[0].size(); j++)
          times[i][j][flg] = paths[i][j];

    return 0;
  }

  int highestPoint(vector <string> landscape, int threshold, int timeToDark) {
    int ret = 0;
    land = landscape;
    th = threshold;
    memset(times, 1000000, sizeof(times));

    alphabet['A'] = 0, alphabet['B'] = 1, alphabet['C'] = 2, alphabet['D'] = 3, alphabet['E'] = 4, alphabet['F'] = 5, alphabet['G'] = 6, alphabet['H'] = 7, alphabet['I'] = 8, alphabet['J'] = 9, alphabet['K'] = 10, alphabet['L'] = 11, alphabet['M'] = 12, alphabet['N'] = 13, alphabet['O'] = 14, alphabet['P'] = 15, alphabet['Q'] = 16, alphabet['R'] = 17, alphabet['S'] = 18, alphabet['T'] = 19, alphabet['U'] = 20, alphabet['V'] = 21, alphabet['W'] = 22, alphabet['X'] = 23, alphabet['Y'] = 24, alphabet['Z'] = 25, alphabet['a'] = 26, alphabet['b'] = 27, alphabet['c'] = 28, alphabet['d'] = 29, alphabet['e'] = 30, alphabet['f'] = 31, alphabet['g'] = 32, alphabet['h'] = 33, alphabet['i'] = 34, alphabet['j'] = 35, alphabet['k'] = 36, alphabet['l'] = 37, alphabet['m'] = 38, alphabet['n'] = 39, alphabet['o'] = 40, alphabet['p'] = 41, alphabet['q'] = 42, alphabet['r'] = 43, alphabet['s'] = 44, alphabet['t'] = 45, alphabet['u'] = 46, alphabet['v'] = 47, alphabet['w'] = 48, alphabet['x'] = 49, alphabet['y'] = 50, alphabet['z'] = 51;

    dijk(0, 0, -1, -1, 0);
    for (int i=0; i<land.size(); i++)
      for (int j=0; j<land[0].size(); j++)
        dijk(i, j, 0, 0, 1);

    for (int i=0; i<land.size(); i++)
      for (int j=0; j<land[0].size(); j++)
        if (times[i][j][0] + times[i][j][1] < timeToDark)
          ret = max(ret, alphabet[land[i][j]]);

    return ret;
  }
};