Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-31

SRM379 div2 (過去問)

11:16

Hard - TVGameWinnings

ゲームの最高得点, 最低得点を求める. ゲームのルールはややこしいので省略.

問題文は長かったんですが問題自体は900点なので簡単でした. ボードの大きさが高々6なので, すべてのケースで6!通りとなり, 全探索で大丈夫そうです. 探索には next_permutation を使いました. connected なグループ数のカウントにはつながっているセルにラベルを付けていくという flood fill っぽいアルゴリズムを使いました.

class TVGameWinnings {
public:
  int getVal(char s) {
    if ('A' <= s && s <= 'I')
      return (s - 'A' + 1) * -1;
    return s - '0';
  }

  vector <int> getMinMax(vector <string> board) {
    vector <int> ret(2, 0);
    vector <int> indices(board.size(), 0);
    ret[0] = INT_MAX, ret[1] = INT_MIN;
    for (int i=0; i<indices.size(); i++)
      indices[i] = i;

    do {
      vector <int> labels(board.size(), 0);
      int label = 1, cur_pos = 0;

      // count group number
      while (1) {
        labels[cur_pos] = label;
        int next_pos = indices[cur_pos];
        if (labels[next_pos] == 0) {
          cur_pos = next_pos;
        } else {
          int i;
          for (i=0; i<labels.size(); i++)
            if (labels[i] == 0) {
              cur_pos = i;
              break;
            }
          if (i == labels.size()) break;
          label++;
        }
      }

      // calculate score
      int score = 1;
      for (int i=0; i<indices.size(); i++)
        score *= getVal(board[i][indices[i]]);
      
      if (label % 2 == 0)
        score *= -1;

      ret[0] = min(ret[0], score);
      ret[1] = max(ret[1], score);
    } while (next_permutation(indices.begin(), indices.end()));

    return ret;
  }
};

2009-12-30

SRM379 div2 (過去問)

12:29

ぐだぐだとながら作業でやってしまったため, どの問題もかなり時間がかかってしまいました. 集中してやらないと時間がもったいないですね.

Easy - DownloadingFiles

いくつかのファイルをダウンロードする. スピードと残り時間が与えられる. あるファイルのダウンロードが完了すると, 開いた帯域を残りのファイルに割り振ることができる. すべてのファイルがダウンロード完了する時間を求める.

問題文中で, ファイルのダウンロードする順序や帯域の割り当て方は解に影響しないと保証されていたので, 機械的に処理するだけです. ダウンロードが完了するごとに帯域を残りのファイルに適当に割り当てます.

class DownloadingFiles {
public:
  double actualTime(vector <string> tasks) {
    double ret = 0;
    vector <pair <double, double> > t;

    for (int i=0; i<tasks.size(); i++) {
      int speed = 0, time = 0;
      sscanf(tasks[i].c_str(), "%d %d", &speed, &time);
      t.push_back(make_pair(time, speed));
    }

    for (int i=0; i<t.size(); i++) {
      double free = 0;
      double minus = 0;
      double time = 100000;
      int pos = 0, pos2 = 0;
      
      for (int j=0; j<t.size(); j++)
        if (t[j].first > 0 && t[j].first < time) {
          time = t[j].first;
          pos = j;
        }

      ret += t[pos].first;
      minus = t[pos].first;

      for (int j=0; j<t.size(); j++) {
        t[j].first -= minus;
        if (t[j].first <= 0) {
          free += t[j].second;
          t[j].second = 0;
        }
        if (t[j].first > 0)
          pos2 = j;
      }

      t[pos2].first = t[pos2].first * t[pos2].second / (t[pos2].second + free);
      t[pos2].second = t[pos2].second + free;
    }

    return ret;
  }
};

Medium - SellingProducts

商品の値段を決める. 顧客ごとに値段とコストが与えられる. ある顧客は値段以下の商品なら購入する. 利益は 売値 - コスト. 利益が最大になるよう売値を決定する.

売値よりコストが上回っていたらその顧客には売らないという, greedy っぽい単純なアルゴリズムで大丈夫です. 売値の候補は "price" の各要素の値だけしかありえないので, それらをすべて調べます.

class SellingProducts {
public:
  int optimalPrice(vector <int> price, vector <int> cost) {
    int max_profit = 0;
    int opt_price = INT_MAX;

    for (int i=0; i<price.size(); i++) {
      int profit = 0;
      for (int j=0; j<price.size(); j++)
        if (price[j] >= price[i] && price[i] > cost[j])
          profit += price[i] - cost[j];

      if (profit == max_profit && opt_price > price[i]) {
        opt_price = price[i];
      } else if (profit > max_profit) {
        opt_price = price[i];
        max_profit = profit;
      }
    }

    if (max_profit == 0) opt_price = 0;

    return opt_price;
  }
};

2009-12-29

SRM453.5 div1 (過去問)

16:28

Medium - PlanarGraphShop

top submissionをみて修正. まずグラフのエッジ数はwikipediaのplanar graph(平面グラフ)の項によると (ノード数*3-6) となります.

Planar graph - Wikipedia

平面グラフ - Wikipedia

またコストの計算と同時に最小値の計算も行って, 計算時間を短縮しています.

class PlanarGraphShop {
public:
  int bestCount(int N) {
    int ret = 0;
    vector <int> dp(N+1, INT_MAX);
    dp[0] = 0;
    
    for (int nodes=1; nodes<=36; nodes++) {
      int limit = 3 * nodes - 6;
      if (nodes == 1) limit = 0;
      if (nodes == 2) limit = 1;
      for (int edges=0; edges<=limit; edges++) {
        int cost = (int)pow((double)nodes, 3) + (int)pow((double)edges, 2);
        for (int i=0; i<=N-cost; i++)
          dp[i+cost] = min(dp[i] + 1, dp[i+cost]);
      }
    }

    ret = dp[N];
    return ret;
  }
};

2009-12-28

SRM453.5 div1 (過去問)

19:34

Medium - PlanarGraphShop

交差するエッジの無い無向グラフを planar graph と呼ぶ. planar graph のコストを, ノード数^3 + エッジ数 ^ 2 と定義する. コストが整数 N ぴったりになるには, 最小でいくつの planar graph が必要か.

すべての種類の planar graph のコストを求める問題と, 求まったコストの集合を利用して必要なグラフ数を求める問題に分割しました. まずコストの求め方ですが, Nが高々50000なので, コストが50000以下になるすべてのグラフを探索します. 手計算により, エッジの数の範囲は [0, ノード数+ノード数-3] と求まりました. この結果を items という配列に保存しました. 次に, 2番目のグラフ数を求める問題には, ナップザック問題風の考え方のdpを利用しました. 一次元の配列 dp をつくり, dp[i] には N=i のときに必要なグラフ数が入ります. dp[i] は (j <= i) となるすべてのj二ついて, items[j] + dp[i-j] を求めて, その最小値が値となります.

ローカルでのテストでは, インプットが大きいとだいぶ時間がかかっていたので, TLEがやばいかなと思っていたんですが, サーバでテストしてみると意外と間に合いそうだったので, このまま提出しました. システムテストでは, 今のところ実行時間は大丈夫なんですが, 返り値がふつうに間違っていたところがあったので, どこかにバグが有るようです. 明日デバッグします.

class PlanarGraphShop {
public:
  int bestCount(int N) {
    int ret = 0;
    vector <int> items(50001, 0);
    vector <int> dp(N+1, INT_MAX);
    
    // calculate costs of planar graphs (generate items)
    items[1] = 1;
    for (int nodes=1; nodes<=36; nodes++)
      for (int edges=0; edges<=nodes + nodes - 3; edges++) {
        int cost = (int)pow((double)nodes, 3) + (int)pow((double)edges, 2);
        if (cost > 50000) continue;
        items[cost] = 1;
      }

    // knapsack
    dp[0] = 0;
    for (int i=1; i<=N; i++) {
      for (int j=1; j<=i; j++)
        if (items[j] == 1)
          dp[i] = min(dp[i], items[j] + dp[i-j]);
    }

    ret = dp[N];
    return ret;
  }
};

2009-12-27

SRM453.5 div1 (過去問)

10:09

Easy - MazeMaker

以前やったので問題文は省略. アプローチは単純なbfs. ミスしていた部分が3箇所あり, ひとつはbfsの中のループ内で配列のインデックスを書き間違い. この部分のコードは毎回ほぼ同じなので, テンプレートを作っておこうと思います. 2つ目はループの終了条件の書き間違い. これはマクロで対応かなあ. tcでは使っている人も多い REP というマクロの導入を検討します. 3つ目はbfsの結果から最大のステップ数を探す際に, 'X'となっているセルをスキップし忘れていたこと. これはアルゴリズムのミスなので, 前の2つよりは罪が軽いかな. 対策としては, 2次元グリッド全体を出力する処理をテンプレートかマクロにしておけば, デバッグが早くなってこういうミスに気づきやすくなるんじゃないかと考えています.

class MazeMaker {
public:
  int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol) {
    int ret = 0;
    int steps[maze.size()][maze[0].size()];
    const int INF = 10000;
    queue <int> q;

    for (int i=0; i<maze.size(); i++)
      for (int j=0; j<maze[0].size(); j++)
        steps[i][j] = INF;

    q.push(startRow);
    q.push(startCol);
    steps[startRow][startCol] = 0;

    while (!q.empty()) {
      int cur_row = q.front();
      q.pop();
      int cur_col = q.front();
      q.pop();

      for (int i=0; i<moveRow.size(); i++) {
        int next_row = cur_row + moveRow[i];
        int next_col = cur_col + moveCol[i];
        if (0 <= next_row && next_row < maze.size() && 0 <= next_col && next_col < maze[0].size() &&
            maze[next_row][next_col] != 'X' && steps[next_row][next_col] == INF) {
          steps[next_row][next_col] = steps[cur_row][cur_col] + 1; // miss
          q.push(next_row);
          q.push(next_col);
        }
      }
    }

    for (int i=0; i<maze.size(); i++)
      for (int j=0; j<maze[0].size(); j++) // miss
        if (maze[i][j] != 'X')  // miss
          ret = max(ret, steps[i][j]);

    if (ret == INF) ret = -1;

    return ret;
  }
};

2009-12-26

SRM382 div2 (過去問)

11:47

以前同じ問題を解いていたんですがもう一度.

Easy - ContiguousSubsequences

問題文は省略. ループカウンタ用の変数を間違えないようにiやjでなくべつの名前をつけてやってみたんですが, 変数の名前間違いはおこらなかったものの, やはりループの境界条件を考えるのに手間取って時間がかかってしまいました. また平均が0の場合がありえることを考慮できていなかったので, システムテストに落ちてしまいました. 問題のConstraintsと関数の定義域・値域をちゃんと確認する癖をつける必要がありそうです.

class ContiguousSubsequences {
public:
  vector <int> findMaxAverage(vector <int> a, int K) {
    vector <int> ret(2, 0);
    double avg = -1;

    for (int len=a.size(); len>=K; len--) {
      for (int pos=0; pos<=a.size()-len; pos++) {
        int sum = 0;
        for (int i=pos; i<pos+len; i++)
          sum += a[i];
        if (avg < (double)sum/(double)len) {
          avg = (double)sum/(double)len;
          ret[0] = pos, ret[1] = pos + len - 1;
        }
      }
    }

    return ret;
  }
};

Medium - CollectingRiders

問題文は省略. for文をコピペしたところで, 変数名を書きなおすのを忘れていて, そのバグ取りで時間を使ってしまいました. やはりコードのコピペは危険なので, こういう部分のタイプ量削減には, エディタの補完機能やマクロで対応すべきです. また到達可能・不可能の判定(-1を返すかどうか)を考える際にすこし混乱してしまって, 時間をくってしまいました. 最終的には, -1を返すようなケースでは解がかならず定数INFを超えるようにしました.

class CollectingRiders {
public:
  int minimalMoves(vector <string> board) {
    const int INF = 100000;
    int ret = INF;
    int steps[board.size()][board[0].size()];
    int dirx[8] = {-2, -2, -1, 1, 2, 2, 1, -1};
    int diry[8] = {-1, 1, 2, 2, 1, -1, -2 ,-2};

    for (int row=0; row<board.size(); row++)
      for (int col=0; col<board[0].size(); col++) {
        queue <pair <int, int> > q;
        for (int i=0; i<board.size(); i++)
          for (int j=0; j<board[0].size(); j++)
            steps[i][j] = INF;
        q.push(make_pair(row, col));
        steps[row][col] = 0;

        while (!q.empty()) {
          pair <int, int> cur = q.front();
          q.pop();
          int cur_row = cur.first, cur_col = cur.second;

          for (int i=0; i<8; i++) {
            int next_row = cur_row + dirx[i], next_col = cur_col + diry[i];
            if (0 <= next_row && next_row < board.size() && 0 <= next_col && next_col < board[0].size() && steps[next_row][next_col] == INF) {
              steps[next_row][next_col] = steps[cur_row][cur_col] + 1;
              q.push(make_pair(next_row, next_col));
            }
          }
        }

        int number_of_step = 0;
        for (int i=0; i<board.size(); i++)
          for (int j=0; j<board[0].size(); j++)
            if (board[i][j] != '.')
              number_of_step += (steps[i][j] == INF) ? INF : ceil((double)steps[i][j] / (double)(board[i][j] - '0'));

        ret = min(ret, number_of_step);
      }

    if (ret >= INF) ret = -1;

    return ret;
  }
};

2009-12-25

SRM454 div1 (過去問)

09:11

Easy - DoubleXor

^^ 演算子を定義する. 例えば c = a ^^ b の場合, (cのn桁目) = ( (aのn桁目) ^ (bのn桁目) ) % 10 となる. 整数Nが与えられるので, N ^^ N-1 ^^ N-2 ^^ ... ^^ 1 を求めよ.

とくにひねりなく, ストレートに実装するだけでした.

class DoubleXor {
public:
  int dxor(const int _a, const int _b) {
    int ret = 0;
    int a = _a, b = _b;
    int counter = 0;
    
    while (a > 0 || b > 0) {
      ret += (((a%10) ^ (b%10)) % 10) * (int)pow((double)10, counter++);
      a /= 10, b /= 10;
    }

    return ret;
  }

  int calculate(int N) {
    int ret = N;

    while (N > 0)
      ret = dxor(ret, --N);

    return ret;
  }
};

2009-12-24

SRM456 div2 (再チャレンジ)

13:45

Medium - CutSticks

hardに再挑戦です. 多くの人がバイナリサーチを使って解いていたのですが, なぜなのかがわかりませんでした. chokudaiさんのblogをみたところ,

「K番目に長い」=「その長さより長い棒がK本ある」

とあって納得. この発想ができるかどうかが鍵ですね.

まず, 0 - 0e09 の間をバイナリサーチで探索します. sticksを切っていって, 候補の解nよりも長いstickがK本以上作れれば右へ, そうでなければ左へ探索範囲を狭めていきます. ある長さnよりも長いstickの本数を調べる方法は, sticksの各要素についてnで割っていくことで求まります. その際切る回数は最大C回なので, それ以下になるように制限をつけます.

また, バイナリサーチの繰り返し回数は定数にすべきという注意点も今回学べました. 例えば while (n - m < 1e09) などとすると, インプットによっては無限ループになってしまいます. 定番のチャレンジポイントらしいです.

今回chokudaiさんの記事のほかには, ellerさんのblog, nitoyonさんのblogも参考にさせていただきました. ありがとうございました.

class CutSticks {
public:
  double maxKth(vector <int> sticks, int C, int K) {
    double ret = 0;
    double left = 0, right = 1e09, mid = 0;

    for (int i=0; i<1000; i++) {
      mid = (right + left) / 2;

      int number_of_large_stick = 0, number_of_cut = 0;
      int c = C;
      for (int j=0; j<sticks.size(); j++) {
        if (sticks[j] < mid) continue;
        number_of_cut = (int)(max(sticks[j] / mid - 1.0, 0.0));
        number_of_cut = min(number_of_cut, c);
        c -= number_of_cut;
        number_of_large_stick += number_of_cut + 1;
      }

      if (number_of_large_stick >= K)
        left = mid;
      else
        right = mid;
    }

    ret = mid;

    return ret;
  }
};

2009-12-23

SRM456 div2

13:58

div1になることができました!

writerは rng_58 さん. easy, medium が解けて チャレンジに二回成功. ルーム1位, div2全体で18位. raging は 1138 -> 1240 (+102) でついに blue coder になることができました. 今年の目標がぎりぎり達成できてよかったです. ブログの背景もブルーに変えてみました. 次回からはまず250をしっかり解くことを目標にやっていきます.

Easy - AppleWord

正規表現 /^ap+le$/i にマッチするような文字列をapple wordという. 与えられた文字列に対して, ある文字を別の文字に入れ替えることができる. 与えられた文字列をapple wordにするには何回文字を入れ替えればよいか. 不可能な場合は-1.

return が -1になるのは文字長が5未満のとき. あとは最初の文字が"a", 最後の二文字が"el"になっているかを調べ, その間を"p"になるようにします.

class AppleWord {
public:
  int minRep(string word) {
    int ret = 0;

    if (word.size() < 5)
      return -1;

    if (word[0] != 'a' && word[0] != 'A')
      ret += 1;

    for (int i=1; i<word.size()-2; i++)
      if (word[i] != 'p' && word[i] != 'P')
        ret++;

    if (word[word.size()-2] != 'l' && word[word.size()-2] != 'L')
      ret += 1;

    if (word[word.size()-1] != 'e' && word[word.size()-1] != 'E')
      ret += 1;

    return ret;
  }
};

Medium - SilverDistance

将棋の銀将が無限大の盤上に置かれている. スタート, ゴールの座標が与えられるので, 最短何手でゴールまで行けるかを求める.

あまりスマートではないのですが, スタートからゴールまでgreedyに一手ずつ進んでいく方針で組みました. 行けるところまでは斜めに進み, syとgyの差が0になるような左右に進む場合は 右下, 右上, 右下, ... のようにジグザグに進みます. またgx - sx == 0 で gy - sy > 0 のような真下に進まなければいけない場合は, 右下, 左下, 右下, ... のようにジグザグに進みます.

最初bfsで探索するコードを書いてしまって, 時間をロスしました. そういう探索だとTLEします. もっと早く解きたかったです.

class SilverDistance {
public:
  int minSteps(int sx, int sy, int gx, int gy) {
    int ret = 0;
    int curx = sx, cury = sy;
   
    while (!(curx == gx && cury == gy)) {
      int dirx = 0;
      int diry = 0;

      if (gx - curx > 0)
        dirx = 1;
      else if (gx - curx < 0)
        dirx = -1;

      if (gy - cury > 0)
        diry = 1;
      else
        diry = -1;

      if (dirx == 0 && diry == -1)
        dirx = 1;

      curx += dirx;
      cury += diry;
      ret++;
    }

    return ret;
  }
};

Hard - CutSticks

棒が何本か与えられる. 棒を一本取り出して任意の長さで折って2つに分けることができる. 棒を最大C回折って, 降順に並べ, K番目にくる棒の長さを最長にする.

これは解けませんでした. 最も素朴な解法は,

  1. 棒をソート
  2. 最長のものをちょうど半分に折る

これを棒がK本になるまで繰り返すという方法です. ただKはワーストで 1,000,000,050 と大きいので, とてもじゃないけど間に合いません. 別の方法を考える必要があります. 棒の長さの変遷には規則性がありそうなので, それを見つける必要がありそうです.

Challenge phase

500 で真下に進むケースを考えていない人がいたので撃墜しました.

2009-12-22

SRM380 div2 (過去問)

02:37

Easy - LuckyTicketSubstring

数列の前半と後半の数字の和が等しいものをlucky ticketと呼ぶ. ある数列が与えられるので, そのサブ数列のうちlucky ticketとなるものの最大長を求める.

ふつうに全探索です. lucky ticketの中心を左から右へスライドさせて行き, nをひとつずつ増やして調べています.

class LuckyTicketSubstring {
public:
  int maxLength(string s) {
    int ret = 0;

    for (int i=1; i<s.size(); i++) {
      int left_sum = 0, right_sum = 0;
      for (int j=1; i-j >= 0 && i+j-1 < s.size(); j++) {
        left_sum += s[i-j] - '0';
        right_sum += s[i+j-1] - '0';
        if (left_sum == right_sum)
          ret = max(ret, j*2);
      }
    }

    return ret;
  }
};

Medium - LameKnight

右にしか進めないナイトが, 盤上の左下に置かれている. 盤の縦横の大きさが与えられるので, このナイトは最大何セル訪れることが出来るか. ただし最初の4手以上の場合は4種類の動き(上2右1, 下2右1,上1右2, 下1右2)のそれぞれを少なくとも一回は行わないといけない.

すごく汚らしいコードになっちゃうんですが, すべての場合をifで分岐して求めています. 縦が3マス以上, 横が7マス以上あれば, 最初に横へ2つ動く動きをして, あとはすべて横に1つ動く動きをするのが最適解になるので, そのように計算しています. それ以外の場合は, パターン数が少ないので, すべて列挙しました. こういう解法は考慮漏れをしがちなので慎重に行うべきです. 今回もシステムテストにおちちゃいました.

class LameKnight {
public:
  int maxCells(int height, int width) {
    int ret = 1;

    if (height >= 3 && width >= 7) {
      ret += 4 + width - 7;
    } else {
      if (height > 1 && width > 1 && height * width != 4) {
        if (height == 2) {
          if (width < 5)
            ret += 1;
          else if (width < 7)
            ret += 2;
          else
            ret += 3;
        } else {
          if (width == 2)
            ret += 1;
          else if (width == 3)
            ret += 2;
          else if (width < 7)
            ret += 3;
        }
      }
    }

    return ret;
  }
};

2009-12-21

SRM382 div2 (過去問)

01:50

Medium - CollectingRiders

k-ridersはk回連続で動けるナイト. 板状にいくつかのk-ridersが置かれているので, ひとつのセルに複数のk-ridersが乗れるとすると, 最短何手ですべてのk-ridersがひとつのセルに集まるか.

板状のすべてのセルについて, そのセルがk-ridersの集合地点と仮定して何手で集まれるかを調べ, その最小値を返すというアプローチです. 手数のカウントは, そのセルをスタートしたbfsで各セルへの最短距離を求め, あとはk-ridersの置かれているセルとスタート地点との最短距離の総和をとることで求まります. kの処理は, まず1-ridersと仮定して手数を求め, 最後にそれをkで割ればokです.

mediumにしては難しい問題だった気がします.

class CollectingRiders {
public:
  int minimalMoves(vector <string> board) {
    int ret = -1;
    int dirx[8] = {-2, -2, -1, 1, 2, 2, 1, -1};
    int diry[8] = {-1, 1, 2, 2, 1, -1, -2, -2};
    int visited[board.size()][board[0].size()];
    const int INF = 100000;

    for (int i=0; i<board.size(); i++)
      for (int j=0; j<board[0].size(); j++) {
        for (int k=0; k<board.size(); k++)
          for (int l=0; l<board[0].size(); l++)
            visited[k][l] = INF;
        queue <pair <int, int> > q;
        q.push(make_pair(i, j));
        visited[i][j] = 0;

        while (!q.empty()) {
          pair <int, int> cur = q.front();
          q.pop();
          int cur_x = cur.first;
          int cur_y = cur.second;

          for (int k=0; k<8; k++) {
            int next_x = cur_x + dirx[k];
            int next_y = cur_y + diry[k];
            if (0 <= next_x && next_x < board.size() && 0 <= next_y && next_y < board[0].size() && visited[next_x][next_y] == INF) {
              visited[next_x][next_y] = min(visited[next_x][next_y], visited[cur_x][cur_y] + 1);
              q.push(make_pair(next_x, next_y));
            }
          }
        }

        int sum = 0;
        bool valid = true;
        for (int k=0; k<board.size(); k++)
          for (int l=0; l<board[0].size(); l++)
            if (board[k][l] != '.') {
              if (visited[k][l] == INF) {
                valid = false;
                break;
              } else {
                sum += ceil((double)visited[k][l] / (board[k][l] - '0'));
              }
            }

        if (valid && sum >= 0 && (ret == -1 || ret > sum))
          ret = sum;
      }

    return ret;
  }
};

2009-12-20

SRM381 div2 (過去問)

01:17

Easy - TheBestName

stringの集合をある方法でソートする問題.

struct を作り, 要件を満たすように operator< をオーバーロードし, ソートしました. ただ回答のメソッド名が"sort"だったため, std::sort と名前が衝突していて, ネームスペースを指定してあげないと std の方の sort() が呼べません. このことに気付かず20分くらいはまってしまいました. topcoder では時間節約のために using namespace std しているので発見に時間がかかってしまいました. これにはかなりがっくりきました.

typedef struct node {
  int weight;
  string name;
};

bool operator< (const node &a, const node &b) {
  if (a.weight == b.weight)
    return a.name < b.name;
  else
    return a.weight > b.weight;
}

class TheBestName {
public:
  vector <string> sort(vector <string> names) {
    vector <string> ret;
    vector <node> nodes;
    int number_of_john = 0;

    for (unsigned int i=0; i<names.size(); i++) {
      if (names[i] == "JOHN") {
        number_of_john++;
        continue;
      }
      node a;
      a.weight = 0;
      a.name = names[i];
      for (unsigned int j=0; j<names[i].size(); j++)
        a.weight += names[i][j] - 'A' + 1;
      nodes.push_back(a);
    }

    std::sort(nodes.begin(), nodes.end());

    for (int i=0; i<number_of_john; i++)
      ret.push_back("JOHN");

    for (unsigned int i=0; i<nodes.size(); i++)
      ret.push_back(nodes[i].name);

    return ret;
  }
};

2009-12-19

SRM382 div2 (過去問)

01:01

Easy - ContiguousSubsequences

与えられた数列aのサブセットのうち, 要素の値の平均が最大のものをさがす. ただしサブセットの要素数は最小Kとする.

ふつうに全パターンを調べます. タイの場合の優先度とループの境界に注意します.

class ContiguousSubsequences {
public:
  vector <int> findMaxAverage(vector <int> a, int K) {
    vector <int> ret(2, 0);
    double maxi = 0;

    for (int i=K; i<=a.size(); i++) {
      for (int j=a.size()-i; j>=0; j--) {
        double sum = 0;
        for (int k=j; k<j+i; k++)
          sum += a[k];
        sum /= (double)i;
        if (maxi <= sum) {
          maxi = sum;
          ret[0] = j;
          ret[1] = j+i-1;
        }
      }
    }

    return ret;
  }
};

2009-12-18

Member SRM455 div2 Medium のループと計算量の証明

17:26

Member SRM455 div2 - cou929のTopCoder日記 - TopCoder部 の続き. 数列Aにかならずループが存在することを証明し, かつその計算量を求めます.

A[i]はそれより前のN個の要素(A[i-N] - A[i-1])に依存しています. このN個の並びが全く同じものが, 数列全体の中で二度出てくるとしたら, Aがループしていることになります. 今回Aの各要素は10でmodをとっているので, [0, 9]の10種類のみです. よってAのN個の要素ととりうる値の種類は10^N通り. このことから, 次のような要素の組を考えた場合, 少なくともA[10^N]の組までには必ず一回は, 全く同じ要素からなる組が存在することになります.

(A[1], A[2], ..., A[N]), (A[2], A[3], ..., A[N+1]), ..., (A[10^N], ..., A[10^N+N])

言い方を変えると, すべてのパターンが 10^N 通りである数列を 10^N+1 個作ったとき, かならず1つは全く同じ数列ができるということです. 今回はNが高々7なので, 10^7 = 10000000 通りとなり, ワーストケースでも時間に間に合うと考えることができます.

ここでは "n個のアイテムをm個の箱に入れる際に, もし n > m だと, 少なくとも一箱は2つ以上のアイテムが入っている箱がある" という事実を使っているんですが, これには Pigeonhole principle という名前がついています.

Pigeonhole principle - Wikipedia

鳩の巣原理 - Wikipedia

上の例だと一見自明な現象にわざわざたいそうな名前を付けているように感じるんですが, ものによってはこの定理を使うことで直感に反する結論が導けることがあって面白いです. wikipediaから引用します.

たとえば「ロンドンには、同じ本数の髪の毛を持った少なくとも2人の人間が存在する」。証明してみよう。ふつう、髪の毛の本数は15万本ほどであるから、100万本の髪の毛を持っている人間はいないと考えることができる。ロンドンの人口は100万以上である。もし、髪の毛の本数ごとに鳩の巣を割り当て、巣にロンドンの人々を割り当てれば、(約15万に100万以上を割り当てるのだから)少なくとも同じ髪の毛の本数を持った2人の人間が必ず存在する。

もう1つのきわめて有名な例は、世界中からランダムに6人を集めてくると、その6人から、互いに全員知り合いであるか、あるいは互いに全く知り合いでない3人組を必ず1組は作ることができる、というものである。詳細は、ラムゼーの定理および組合せ数学のラムゼー理論の項を参照。


以上はこちらのforumのスレッドを参考にしました.

Logic to DivII Medium


Member SRM455 div2

06:45

寝坊して参加できませんでした.

Easy - SpidersOnTheGrid

グリッドが与えられ, それぞれのセルには東西南北のいずれかが割り当てられている. freeなセルの個数をカウントせよ.

問題の意味がいまだにつかめません. まず"free cells"の意味がわかりません. また東西南北の方向もあいまいさがあります. 特に南北が2通りの意味にとれてしまうので, きちんとインデックスの数字で示すべきです.

以下は他の人のコードを参考に書いたものです. このコードだと, "free cells" は"そのセルをスタート地点にしない限りは絶対に訪れることができないセル"という解釈になるんですが, これであってるんでしょうか. 本番だと解ける自信がないです.

class SpidersOnTheGrid {
public:
  int find(vector <string> A) {
    int ret = 0;
    bool ok[A.size()][A[0].size()];
    memset(ok, false, sizeof(ok));
    int dirx[4] = {-1, 1, 0, 0}; // NSEW
    int diry[4] = {0, 0, 1, -1};
    string dir = "NSEW";

    for (int i=0; i<A.size(); i++)
      for (int j=0; j<A[0].size(); j++) {
        int k = 0;
        for (k=0; k<4; k++)
          if (A[i][j] == dir[k])
            break;
        int nextx = i + dirx[k], nexty = j + diry[k];
        if (0 <= nextx && nextx < A.size() && 0 <= nexty && nexty < A[0].size())
          ok[nextx][nexty] = true;
      }

    for (int i=0; i<A.size(); i++)
      for (int j=0; j<A[0].size(); j++)
        if (!ok[i][j])
          ret++;

    return ret;
  }
};

Medium - EasySequence

問題文は省略.

ちょっと難しかったです. まずはループが検出されるまで, 数列Aを作っていきます. ループの検出はAの長さが2の倍数の時に, Aの前半と後半を比べることで実現します. その後はAにBが含まれているかをチェックします. このチェックで境界条件を間違えて, 一度システムテストで落ちてしまいました. またこのアルゴリズムは1. Aに必ずループが出現すること, 2. ループが時間内に求まることを前提としていますが, これらは証明していなくて, ほかにアプローチが思いつかなかったので決め打ちで実装しました. そのせいでなんだかまだすっきりしていません.

class EasySequence {
public:
  int find(vector <int> A, vector <int> B) {
    int ret = -1;
    int n = A.size();

    for (int i=0; ; i++) {
      int tmp = 0;
      for (int j=0; j<n; j++)
        tmp += A[i+j];
      A.push_back(tmp%10);

      // loop detection
      if (A.size() % 2 == 0) {
        vector <int> first_half, second_half;
        for (int j=0; j<A.size(); j++)
          if (j < A.size()/2)
            first_half.push_back(A[j]);
          else
            second_half.push_back(A[j]);

        if (first_half == second_half)
          break;
      }
    }

    while (A.size() < B.size())
      A.insert(A.begin() + A.size(), A.begin(), A.end());

    for (int i=0; i<A.size() - B.size() + 1; i++) {
      bool ok = true;
      for (int j=0; j<B.size(); j++)
        if (A[i+j] != B[j]) {
          ok = false;
          break;
        }

      if (ok) {
        ret = i;
        break;
      }
    }

    return ret;
  }
};

通りすがり通りすがり2009/12/21 22:32「蜘蛛は指定された方向に毎秒1セルづつ進みます。1秒後に蜘蛛のいないセルの数は?」

cou929cou9292009/12/21 22:45ありがとうございます.
そうですね. 最初はすべてのセルに蜘蛛がいて, 一秒後にフリーになってるセルですね.

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;
  }
};

2009-12-16

SRM384 div2 (過去問)

22:32

Easy - Prank

整数 apparentGain が与えられるので, a^2 - b^2 = apparentGain となるような整数aを求める.

アルゴリズムは1から順に二乗を計算し, apparentGainを足し, そのルートを取り, その結果が整数ならば (小数点以下がなければ) 解に追加するというもので, これはすぐに思いついたのですが, 探索範囲を1からどこまでにすべきなのかに悩みました. とりあえず勘で[1, 100000]にしたらシステムテストまで通ったんですが, 確証がないままです.

探索範囲の上限についてはeditorialをみて納得できました. ある整数xとそれより小さい整数x-kとの間で上記の計算をすると仮定します. x^2 - (x-k)^2 が一番小さくなるのはk=1のときです. よって x^2 - (x-1)^2 が100000を超えた時のxの値を上限とすれば良いことになります. x^2 - (x-1)^2 = 2*x - 1 となるので 2*x - 1 <= 100000, x <= 50000. よって上限は50000となります.

class Prank {
   public:
   vector <int> realWeight(int apparentGain) {
      vector <int> ret;

      for (int i=1; i<=100000; i++) {
        long long ll = (long long)i * i;
        ll += apparentGain;
        double sqrt_ll = sqrt(ll);
        if (sqrt_ll == (int)sqrt_ll)
          ret.push_back((int)sqrt_ll);
      }

      return ret;
  }
};

Medium - Library

図書館にはいくつかの部屋があり, それぞれの部屋に書類がある. 部屋ごと, 書類ごとにアクセス権限が設定されている. 各ドキュメントにアクセスできる権限の情報と, ある人物の権限が与えられるので, この人物がどの書類にアクセスできるかを求める.

これはただやるだけの問題でした. 250より簡単でした.

class Library {
public:
  vector <string> split(const string _s, const string del) {
    vector <string> ret;
    string s = _s;

    while (!s.empty())
      {
        size_t pos = s.find(del);
        string sub = "";
        sub = s.substr(0, pos);
        ret.push_back(sub);
        if (pos != string::npos)
          pos += del.size();
        s.erase(0, pos);
      }

    return ret;
  }

  int documentAccess(vector <string> records, vector <string> userGroups, vector <string> roomRights) {
    int ret = 0;
    set <string> docs;

    for (int i=0; i<records.size(); i++) {
      vector <string> tmp = split(records[i], " ");
      if (find(userGroups.begin(), userGroups.end(), tmp[2]) != userGroups.end() &&
          find(roomRights.begin(), roomRights.end(), tmp[1]) != roomRights.end())
        docs.insert(tmp[0]);
    }

    ret = docs.size();

    return ret;
  }
};

2009-12-15

SRM386 div2 (過去問)

23:21

Hard - LittleTree

グラフの高さを height 以下にするときの, 最小コストを求める問題.

集中力が切れてしまったので途中で一旦やめました. 一応考えたのはgreedyな方法で, ルートから下へ探索していき, height以上になった際にそのノードをaugmentするというものです. 当然ですがテストケース0など, height以下のノードをaugmentした方が最適なケースもあるので, うまくいきません.

class LittleTree {
public:
  int toInt(string s) {int r = 0; istringstream ss(s); ss >> r; return r;}

  vector <string> split(const string _s, const string del) {
    vector <string> ret;
    string s = _s;

    while (!s.empty())
      {
        size_t pos = s.find(del);
        string sub = "";
        sub = s.substr(0, pos);
        ret.push_back(sub);
        if (pos != string::npos)
          pos += del.size();
        s.erase(0, pos);
      }

    return ret;
  }

  int minCost(int N, vector <string> e, int height) {
    int ret = 0;
    string edge_string;
    int graph[100][100];
    bool fixed[100];
    memset(graph, 0, sizeof(graph));
    memset(fixed, false, sizeof(fixed));

    for (int i=0; i<e.size(); i++)
      edge_string += e[i];

    vector <string> tmp = split(edge_string, " ");
    for (int i=0; i<tmp.size(); i++) {
      vector <string> t = split(tmp[i], ",");
      graph[toInt(t[0])][toInt(t[1])] = 1;
    }

    queue <pair <int, int> > q;
    q.push(make_pair(0, 0));
    fixed[0] = true;

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

      int cur_node = cur.first;
      int cur_level = cur.second;

      if (cur_level > height) {
        int parent = 0;
        int grandparent = 0;
        for (int i=0; i<100; i++)
          if (graph[i][cur_node] == 1) {
            parent = i;
            break;
          }
        for (int i=0; i<100; i++)
          if (graph[i][parent] == 1) {
            grandparent = i;
            break;
          }

        graph[parent][cur_node] = 0;
        graph[grandparent][cur_node] = 1;
        ret++;
        q.push(make_pair(cur_node, cur_level-1));
      } else {
        for (int i=0; i<100; i++)
          if (graph[cur_node][i] == 1 && !fixed[i])
            q.push(make_pair(i, cur_level+1));
        fixed[cur_node] = true;
      }
    }

    return ret;
  }
};

2009-12-14

SRM385 div2 再チャレンジ

21:15

Medium - UnderscoreJustification

wordのセットと文字数wが渡されるので, ちょうどw文字になるようにwordwordの間に空白を挿入して一文をつくる. ただし各word間の空白の数はプラスマイナス1以内でないといけない. 複数の候補があるので, 辞書順に若いものを返す. ちなみに辞書順だと "アルファベット大文字" < "空白(の代わりにこの問題では"_"を用いる)" < "アルファベット小文字" の順になる.

問題はどのword間の空白を一文字ふやすかを求めることです. 実はword数が高々10という制約があるので, 全組み合わせも最大で3桁ほどになるはず(例えばwordが10で5か所選ぶとしても, 9C5 程度)なので全探索しても良いんですが, 今回はgreedyな方法で実装してみました. 方法は, 1.小文字で始まるwordの前には優先して空白を入れる. 2.まだ空白が余っている場合は後ろから空白を挿入していく. というものです.

コードはスマートじゃないし, 変数名がなんか適当ですが, 一応できました.

class UnderscoreJustification {
public:
  string justifyLine(vector <string> words, int width) {
    string ret = words[0];
    int word_length = 0;
    int spaces = words.size() - 1;
    int underscores = 0;
    int rest_underscores = 0;

    for (int i=0; i<words.size(); i++)
      word_length += words[i].size();

    underscores = (width - word_length) / spaces;
    rest_underscores = (width - word_length) % spaces;

    vector <int> space_nums(spaces, underscores);

    for (int i=1; i<words.size(); i++)
      if (rest_underscores > 0 && 'a' <= words[i][0] && words[i][0] <= 'z') {
        space_nums[i-1]++;
        rest_underscores--;
      }

    for (int i=space_nums.size()-1; i>=0; i--)
      if (rest_underscores > 0 && space_nums[i] == underscores) {
        space_nums[i]++;
        rest_underscores--;
      }

    for (int i=1; i<words.size(); i++) {
      string space(space_nums[i-1], '_');
      ret += space;
      ret += words[i];
    }

    return ret;
  }
};

Hard - SummingArithmeticProgressions

x, x+1*d, x+2*d ... x+(k-1)*d という数列がある. 正の整数left, rightとkが与えられるので, 数列の各要素の総和が[left, right]の範囲に収まるものの個数を求めよ.

これは, もしかしたら何か数学的な理論を使ったり漸化式を作ってdpしたりなどを想定した問題だったのかもしれませんが, kが2-5という非常に小さい範囲であることと, 手計算でもすぐに規則性が見つかってしまうという理由で簡単でした. 手で計算してみるとわかるのですが, それぞれのkについて, 求まる数列の総和は以下のようになっています.

  • k=2のときは3以上の整数
  • k=3のときは{6, 9, 12, 15, ...}
  • k=4のときは{10, 14, 16, 18, ...}
  • k=5のときは{15, 20, 25, ...}

よってleftとrightの間に該当する数字がいくつあるかをカウントするだけです. こちらもやはりコードがなんか汚いですが, 解けました.

class SummingArithmeticProgressions {
public:
  int howMany(int left, int right, int k) {
    int ret = 0;
    if (k == 2) {
      if (right >= 3)
        ret = right - max(left, 3) + 1;
    } else if (k == 3) {
      for (int i=6; i<=right; i+=3)
        if (left <= i)
          ret++;
    } else if (k == 4) {
      for (int i=14; i<=right; i+=2)
        if (left <= i)
          ret++;
      if (left <= 10 && right >= 10)
        ret++;
    } else if (k == 5) {
      for (int i=15; i<=right; i+=5)
        if (left <= i)
          ret++;
    }

    return ret;
  }
};

2009-12-13

SRM385 div2 (過去問)

02:14

Easy - RussianSpeedLimits

ドライブ中にいろいろなスピード制限の標識が出てくる. 制限速度に従った場合, 現在時速何キロで走っているか.

やるだけの問題でした.

class RussianSpeedLimits {
public:
  int toInt(string s) {int r = 0; istringstream ss(s); ss >> r; return r;}
  int getCurrentLimit(vector <string> signs) {
    int ret = 0;
    bool in_city = true;

    for (int i=0; i<signs.size(); i++) {
      if (signs[i][0] == 'd') {
        ret = (in_city) ? 60 : 90;
      } else if (signs[i][0] == 'c') {
        ret = (in_city) ? 90 : 60;
        in_city = (in_city) ? false : true;
      } else {
        ret = toInt(signs[i]);
      }
    }

    return ret;
  }
};

2009-12-12

SRM386 div2 (過去問)

01:24

Easy - TrophyShelf

トロフィーが一例に並べられている. 一例を前から見た場合, あるトロフィーはその前にあるトロフィーより高さが高くなければ, 見えない. トロフィーを前から, 後ろから見た場合, 何本見えるかを返す.

これはやるだけの問題です.

class TrophyShelf {
public:
  vector <int> countVisible(vector <int> trophies) {
    vector <int> ret(2, 1);
    int maxl = trophies[0], maxr = trophies[trophies.size()-1];

    for (int i=1; i<trophies.size(); i++)
      if (trophies[i] > maxl) {
        ret[0]++;
        maxl = trophies[i];
      }

    reverse(trophies.begin(), trophies.end());

    for (int i=1; i<trophies.size(); i++)
      if (trophies[i] > maxr) {
        ret[1]++;
        maxr = trophies[i];
      }

    return ret;
  }
};

Medium - CandidateKeys

ちょっと問題文の意味が読み取れませんでした. 行数が高々10なので, いろいろな列の組み合わせで全探索をすれば良さそうなのですが, どのような条件の時にカウントすればいいのかがいまいちわかりません. 眠くなったので今日はもう無理と判断. 後日再チャレンジします.

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;
  }
};

2009-12-10

SRM445 div2 (過去問)

15:42

Easy - TheEncryptionDivTwo

文字列を暗号化する. 方法はアルファベットごとに, 別のアルファベットにマップする. 暗号化後の文字列のうち, 辞書順でもっとも早いものを返す.

引数を頭からみていき, 新しいアルファベットが出たら新しい暗号化後のアルファベットを割り振ります.

class TheEncryptionDivTwo {
public:
  string encrypt(string message) {
    string ret;
    map <char, char> m;
    int counter = 0;

    for (int i=0; i<message.size(); i++)
      if (m.find(message[i]) != m.end()) {
        ret += m[message[i]];
      } else {
        m[message[i]] = 'a' + counter++;
        ret += m[message[i]];
      }

    return ret;
  }
};

Medium - TheNewHouseDivTwo

2次元座標形上の点がいくつか与えられる. 上下左右に最低一つの点が存在するような位置はいくつあるか.

これもそのままやるだけです. 途中うっかりインデックスを間違えて10分位つまってしまいました.

class TheNewHouseDivTwo {
public:
  int count(vector <int> x, vector <int> y) {
    int ret = 0;

    for (int i=-100; i<=100; i++)
      for (int j=-100; j<=100; j++) {
        bool flg[4] = {false, false, false, false}; 
        for (int k=0; k<x.size(); k++) {
          if (x[k] == i && y[k] > j)
            flg[0] = true;
          if (x[k] == i && y[k] < j)
            flg[1] = true;
          if (x[k] > i && y[k] == j)   // ここを if (x[k] > j && y[k] == j) としてしまっていた
            flg[2] = true;
          if (x[k] < i && y[k] == j)
            flg[3] = true;
        }
        if (flg[0] && flg[1] && flg[2] && flg[3])
          ret++;
      }

    return ret;
  }
};

Hard - TheLockDivTwo

次のビット列の変換ルールが与えられる. 変換できるのは任意個の0または1のどちらかのみで, 辞書順にはやいほうから並ぶ. 例えば4桁のビット列の場合は, "0000", "0001", "0011", "0010", "0110", "0100" となる. このルールでn桁のビット列を生成したとき, k番目の値を返す.

nが高々10なので, うまくやれば0-kまで順に調べ, k番目の値を返すだけで良さそうです. ビット列の生成は使用済みの値を保存しておいて, あとは 0 - (1 << n)までループし, それがルールにのっとっているかを調べるようにしました. 値のチェックは, はじめビットの値の変化は必ず1つずつという勘違いをしてしまっていたので, XORをとってたっているビット数が1ならばokとしていたのですが, 変化するビット数は1とは限らないためダメです. ほかのひとのコードを見てみると, "(a & b) == a || (a & b) == b" というふうにチェックしていました. たしかにこれだと, 片方の値のみを変化させるという条件をチェックできますが, 思いつきませんでした.

class TheLockDivTwo {
public:
  int N;

  string toStr(int n) {
    string ret;
    for (int i=0; i<N; i++)
      if (n & (1 << i))
        ret += '1';
      else
        ret += '0';
    reverse(ret.begin(), ret.end());
    return ret;
  }

  bool ok(int a, int b) {
    if ((a & b) == a || (a & b) == b) // はじめは if (__builtin_popcount(a ^ b) == 1) としていた
      return true;
    return false;
  }

  string password(int n, int k) {
    bool used[(1 << n)];
    int pre = 0;
    N = n;
    memset(used, false, sizeof(used));
    used[0] = true;

    for (int i=1; i<k; i++)
      for (int j=0; j<(1 << n); j++)
        if (!used[j] && ok(pre, j)) {
          pre = j;
          used[j] = true;
          break;
        }

    return toStr(pre);
  }
};

2009-12-09

SRM447 div2 (過去問)

22:54

Hard - ImportsList

いくつかのスクリプトがあり, それぞれ別のスクリプトをインポートしなければいけない. 各スクリプトについて, インポートする数を最小化する.

この問題には感動しました. いまいち良い解が見つからなかったので, レッドコーダーの方々のコードを見ていたのですが, だいたいの人はfloyd-warshallアルゴリズムをうまく応用して, 非常にスマートに解いていました. アイデアは, 例えばスクリプトiからスクリプトjをインポートする必要がある場合を考えると, もし別のスクリプトk(iはkもインポートする必要があるとする)がjをインポートしていた場合, iからjを直接インポートするよりも, kを経由してインポートした方がインポート数を節約できます. この操作を, 三重ループによってすべての組み合わせに適用します. floyd-warshallはグラフ上のノードのすべての組み合わせについて最短経路を求めるアルゴリズムです. それをこんな風に応用するアイデアは自分には思いつきませんでした.

class ImportsList {
public:
  vector <int> importsCount(vector <string> requires) {
    vector <int> ret(requires.size(), 0);
    vector <string> result = requires;
    int n = requires.size();

    for (int i=0; i<n; i++)
      for (int j=0; j<n; j++)
        for (int k=0; k<n; k++)
          if (requires[i][k] == 'Y' && requires[k][j] == 'Y')
            result[i][j] = 'N';

    for (int i=0; i<n; i++)
      for (int j=0; j<n; j++)
        if (result[i][j] == 'Y')
          ret[i]++;

    return ret;
  }
};

2009-12-08

SRM451 div2 (過去問)

23:35

Hard - PizzaDelivery

地図と, ピザ屋の位置と, ピザの配達先が与えられる. ピザ屋には二人の配達員がいる. すべてのピザを配り終える最短時間を計算する.

アルゴリズムは大きく2つのフェーズに分かれます. ひとつは各配達先への最短経路の計算, もうひとつは二人の配達員への配達先の割り振りの決定です. まず最短経路について, 各配達先について, ダイクストラ法で最短距離を計算しています. 次に割り振りについて, 配達先が高々20, その配達先それぞれを2人の配達員どちらかに割り振るので, すべての割り振り方は2^20=1048576通りです. 全探索で間に合いそうです. ある割り振り方の際の時間の計算方法は, 配達員Aの配達先までの時間をT1, T2 ... Tm (T1 <= T2 <= ... <= Tm) とすると, T1*2 + T2*2 + ... + Tm となります. 両方の配達員についてこれを計算し, 大きい方がこの割り振り方の時間です.

以下のコードですが, システムテストが通りませんでした. どうも最短経路を計算している部分にバグがあるようです.

class PizzaDelivery {
public:
  vector <string> terrain;
  int startx, starty;

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

  bool canMove(int fromx, int fromy, int tox, int toy) {
    if (0 <= fromx && fromx < terrain.size() && 0 <= fromy && fromy < terrain[0].size() &&
        0 <= tox && tox < terrain.size() && 0 <= toy && toy < terrain[0].size())
      if ((terrain[fromx][fromy] == 'X' || terrain[fromx][fromy] == '$' || terrain[tox][toy] == 'X' || terrain[tox][toy] == '$') ||
          (abs(terrain[fromx][fromy] - terrain[tox][toy]) < 2))
        return true;
    return false;
  }

  int findRoute(int x, int y) {
    int ret = -1;
    priority_queue <vector <int>, vector <vector <int> >, greater <vector <int> > > q;
    int visited[terrain.size()][terrain[0].size()];
    int dirx[4] = {0, 1, 0, -1};
    int diry[4] = {1, 0, -1, 0};

    for (int i=0; i<terrain.size(); i++)
      for (int j=0; j<terrain[0].size(); j++)
        visited[i][j] = INT_MAX;
    visited[startx][starty] = 0;
    q.push(make_node(0, startx, starty));

    while (!q.empty()) {
      vector <int> cur = q.top();
      q.pop();

      if (cur[1] == x && cur[2] == y) {
        ret = cur[0];
        break;
      }

      for (int i=0; i<4; i++) {
        int nextx = cur[1] + dirx[i];
        int nexty = cur[2] + diry[i];
        int next_cost = 0;

        if (canMove(cur[1], cur[2], nextx, nexty)) {
          if (terrain[cur[1]][cur[2]] == 'X' || terrain[cur[1]][cur[2]] == '$' || terrain[nextx][nexty] == 'X' || terrain[nextx][nexty] == '$')
            next_cost = cur[0] + 2;
          else if (abs(terrain[cur[1]][cur[2]] - terrain[nextx][nexty]) == 0)
            next_cost = cur[0] + 1;
          else if (abs(terrain[cur[1]][cur[2]] - terrain[nextx][nexty]) == 1)
            next_cost = cur[0] + 3;
          else
            continue;

          if (visited[nextx][nexty] == INT_MAX)
            q.push(make_node(next_cost, nextx, nexty));
        
          visited[nextx][nexty] = min(visited[nextx][nexty], next_cost);
        }
      }
    }

    return ret;
  }

  int deliverAll(vector <string> _terrain) {
    terrain = _terrain;
    vector <vector <int> > buildings;
    vector <int> costs;
    int ret = INT_MAX;

    for (int i=0; i<terrain.size(); i++)
      for (int j=0; j<terrain[0].size(); j++)
        if (terrain[i][j] == 'X') {
          startx = i, starty = j;
        } else if (terrain[i][j] == '$') {
          vector <int> tmp(2, 0);
          tmp[0] = i, tmp[1] = j;
          buildings.push_back(tmp);
        }

    for (int i=0; i<buildings.size(); i++) {
      int res = findRoute(buildings[i][0], buildings[i][1]);
      if (res == -1) return -1;
      costs.push_back(res);
    }

    for (int i=0; i<(1 << buildings.size()); i++) {
      int cost_1 = 0, cost_2 = 0;
      int max_1 = 0, max_2 = 0;
      for (int j=0; j<buildings.size(); j++)
        if (i & (1 << j)) {
          cost_1 += costs[j] * 2;
          max_1 = max(max_1, costs[j]);
        } else {
          cost_2 += costs[j] * 2;
          max_2 = max(max_2, costs[j]);
        }

      cost_1 -= max_1, cost_2 -= max_2;

      ret = min(ret, max(cost_1, cost_2));
    }

    return ret;
  }
};

2009-12-07

SRM454 div2 (再チャレンジ)

23:41

Hard - NumbersAndMatches

dpで解きます. 3次元配列を用意し, [何文字目の数字を処理しているか(最大18)][加えたマッチの本数][取り除いたマッチの本数]の場合の組み合わせの数をそれぞれ保存します. Nを最初から一文字ずつループさせ, 現在みているNの一文字に対して, 0-9まで, 何本のマッチを加える/除く必要があるかを計算します. これらの値について, 先述の配列に保存します. 最後に配列の, [Nの桁数][i][i]となる要素の値を総和して, 解とします. [i][i]としているのは, 加えたマッチの数と除いたマッチの数が同じ, つまりきちんと移動が完結しているということになります.

数字は7桁のビット(実際には"1"と"0"からなるstring)に保存します. こうすれば, 単に各桁ごとに差をとるだけで, 加えた/除いたマッチの数を求めることができます.

div1と同じ問題だと, topcoder部の諸先輩方の考え方やコードがブログで読めて, とても参考になります.

class NumbersAndMatches {
public:
  long long differentNumbers(long long N, int K) {
    char  match_nums[10][8] = {"1110111", "0010011", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
    const int MAX_ADD = 200;
    const int MAX_REM = MAX_ADD;
    long long dp[19][MAX_ADD][MAX_REM];
    int digit_num = 0;

    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;

    while (N > 0) {
      int cur_num = N % 10;
      N /= 10;
      digit_num++;

      for (int i=0; i<10; i++) {
        int add_num = 0;
        int remove_num = 0;
        for (int j=0; j<7; j++)
          if (match_nums[cur_num][j] - match_nums[i][j] > 0)
            remove_num++;
          else if (match_nums[cur_num][j] - match_nums[i][j] < 0)
            add_num++;

        for (int j=add_num; j<=K; j++)
          for (int k=remove_num; k<=K; k++)
            dp[digit_num][j][k] += dp[digit_num-1][j-add_num][k-remove_num];
      }
    }

    long long ret = 0;
    for (int i=0; i<=K; i++)
      ret += dp[digit_num][i][i];

    return ret;
  }
};

2009-12-06

SRM454 div2

04:56

250通過, 500がシステムテストで落ち, 部屋で5位, div2で298位, ratingは1152 -> 1139 (-13). また足踏みです.

Easy - MinimalDifference

digit sum を, 整数の各数字の総和と定義する. 例えば, 1234の場合は 1+2+3+4 = 10 となる. A, B, Cの三つの整数が与えられる. A - B の範囲の整数Xのうち, Xのdigit sumとCのdigit sumの差の絶対値が最小となるXを返す. 複数の候補がある場合は, Xの値の小さいものを返す.

A - B の範囲が高々100000なので, 全探索しました.

class MinimalDifference {
public:
  int getDigitSum(int n) {
    int ret = 0;

    while (n > 0) {
      ret += n%10;
      n /= 10;
    }

    return ret;
  }

  int findNumber(int A, int B, int C) {
    int digit_sum_c = getDigitSum(C);
    int mini = INT_MAX;
    int ret = 0;
    
    for (int i=A; i<=B; i++) {
      int ds = getDigitSum(i);
      if (mini > abs(ds-digit_sum_c)) {
        mini = abs(ds-digit_sum_c);
        ret = i;
      }
      if (mini == 0)
        break;
    }

    return ret;
  }
};


Medium - WordsGame

各要素がアルファベット, 大きさnxnの二次元配列が与えられる. この配列に対して, 行/列のスワップを行うことができる. 長さnの文字列(word)が与えられるので, この文字列が行列の行方向, 列方向いずれかに一直線に並ぶようにするには, 最小で何回スワップする必要があるか.

何度スワップしても, ある行/列の要素そのものが変化することはないので(変化するのは要素の行/列内での位置のみ), wordを作ることができる行/列は, すでにwordと同じ文字を含んでいる行/列のみとなります. よって, まずそのような行/列を探し, それぞれについて何度スワップが必要かを調べ, その最小値を返します. スワップの回数は挿入ソートっぽい方法で求めました. 候補の文字列を前から順に見ていき, その文字がwordと異なっていたら正しい文字とスワップします.

と思っていたらシステムテストで落ちました. 原因は行や列, wordの中に同じアルファベットが複数回出現することを考慮していなかったことでした(なぜか勝手にword内のすべての文字は別々と思い込んでいました). スワップ回数を調べる候補の文字列を探す際に, 単にある行/列のある文字が, wordに含まれているかどうかだけで判定していたので, 同じ文字が複数ある場合は, invalidな文字列も候補に含まれてしまっていました. 対策として, 候補の文字列をソートしたものと, wordをソートしたものを比べ, 同じだった場合のみ候補に加えることにしました. 悔いがのこる失敗です.

class WordsGame {
public:
  int minimumSwaps(vector <string> grid, string word) {
    vector <string> candidates;
    int ret = INT_MAX;

    string sorted_word = word;
    sort(sorted_word.begin(), sorted_word.end());
    for (int i=0; i<grid.size(); i++) {
      string s1, s2, sorted_s1, sorted_s2;
      for (int j=0; j<grid.size(); j++) {
        s1 += grid[i][j];
        s2 += grid[j][i];
      }

      sorted_s1 = s1;
      sorted_s2 = s2;
      sort(sorted_s1.begin(), sorted_s1.end());
      sort(sorted_s2.begin(), sorted_s2.end());

      if (sorted_s1 == sorted_word)
        candidates.push_back(s1);
      if (sorted_s2 == sorted_word)
        candidates.push_back(s2);
    }

    for (int i=0; i<candidates.size(); i++) {
      int swap_count = 0;

      for (int j=0; j<word.size(); j++) {
        if (word[j] != candidates[i][j]) {
          int pos = 0;
          for (int k=j+1; k<word.size(); k++)
            if (candidates[i][k] == word[j])
              pos = k;
          char tmp = candidates[i][j];
          candidates[i][j] = word[j];
          candidates[i][pos] = tmp;
          swap_count++;
        }
      }

      if (candidates[i] == word)
        ret = min(ret, swap_count);
    }

    if (ret == INT_MAX)
      ret = -1;

    return ret;
  }
};

Hard - NumbersAndMatches

マッチ棒を並べた数字が与えられる. マッチ棒をk回移動させて, 別の数字をつくる. 出来る数字はなんパターンあるか.

マッチ棒でつくられた数字は最大18個, kが最大127と, データが大きいので, 普通の探索では解けなさそうです. たぶんdpを使うんじゃないかなあと思いつつ, 良い解法が思いつきませんでした.

2009-12-05

SRM448 div2 (過去問)

22:13

Hard - TheCardLineDivTwo

最大16枚のトランプが与えられるので, 数字か色が同じものどおしを隣り合わせながら並べる. 並べ方は何通りあるか. 答えは mod 1234567891 を返す.

一枚のカードをノード, 隣り合うことのできるカード同士をエッジとしたグラフを探索すればいいなじゃないかと考え実装しましたが, 大きいケースでTLEになります. 確かに最悪のケースは, 16枚すべてが隣り合うことが出来る場合で, 16! = 20922789888000 通りの並べ方ができてしまうので, とても間に合いません. 基本である計算量の見積ができていない証拠です.

Forumをみてみると, 自分の実装にあとメモ化を追加すれば間に合いそうだということが分かりました. そこで, 探索はqueueとwhileで行っていたのでこれを再起関数で行うよう変更し, メモを追加, 無事に高速化に成功しました.

また, Editorialでdpでの解が紹介されていました. あとで目を通しておこうと思います.

TopCoder - Error


class TheCardLineDivTwo {
public:
  int size;
  long long memo[16][1<<16];
  int graph[16][16];

  long long r(int pos, int flg) {
    long long ret = 0;
    if (memo[pos][flg] != -1)
      return memo[pos][flg];

    if (flg == (1 << size)-1)
      return 1;

    for (int i=0; i<size; i++)
      if (graph[pos][i] == 1 && !(flg & (1 << i))) {
        int next_flg = (flg | (1 << i));
        ret += r(i, next_flg);
      }

    return memo[pos][flg] = ret % 1234567891;
  }

  int count(vector <string> cards) {
    int ret = 0;
    size = cards.size();
    memset(memo, -1, sizeof(memo));
    memset(graph, 0, sizeof(graph));

    for (int i=0; i<cards.size(); i++)
      if (cards[i][1] == 'S' || cards[i][1] == 'C')
        cards[i][1] = 'B';
      else
        cards[i][1] = 'R';

    for (int i=0; i<cards.size(); i++)
      for (int j=0; j<cards.size(); j++)
        if (i != j && (cards[i][0] == cards[j][0] || cards[i][1] == cards[j][1]))
          graph[i][j] = 1;

    for (int i=0; i<cards.size(); i++)
      ret = (ret + r(i, (1 << i))) % 1234567891;

    return ret;
  }
};

2009-12-04

SRM429 div2 (過去問)

18:51

Hard - IngredientProportions

カクテルのレシピが与えられる. まぜあわせるカクテルの種類ごとの割合が与えられる. 最終的に全体で何対何でまぜあわせればよいか求める.

アルゴリズムはストレートで, 実装をどうするか悩むたぐいの問題でした. まず, アルゴリズムは以下のようなシンプルなものです.

  1. スケールを無視して, すべてのカクテルの割合を求める
    • 例えばテストケース0だと{6, 4}, テストケース3だと{360, 120, 378, 504}
    • カクテルの割合のつながりを木で表現して, それを順にたどっていけばok
  2. 上記の数列の全要素に対する最大公約数を求め, それで割る

実装ですが, まず木は二次元配列で表現することにしました. 要素i, jに, iとjをまぜあわせるときのiの割合を格納します. これで木のつながりと混ぜる割合の両方を保存できます.

この木のすべてのノードを探索します. ここで探索の始点に注意が必要です. 僕は今回BFSで探索を実装したのですが, 木のルートか葉から出発しないとすべてのノードを探索してくれません. 木を表現する配列の行に有効な(0でない)値がひとつしかない場合, そのノードは葉となります. このようにして葉をみつけ, 探索の始点としています.

だらだらと書いていたので, コードが長くなってしまいました. もっと綺麗に書きたいです.

class IngredientProportions {
public:
  int gcd(const int _a, const int _b) {
    int a = max(_a, _b);
    int b = min(_a, _b);

    while (b) {
      int tmp = a % b;
      a = b;
      b = tmp;
    }

    return a;
  }

  vector <int> getMasses(vector <string> proportions) {
    vector <int> ret(proportions.size()+1, 0);
    int graph[proportions.size()+1][proportions.size()+1];
    memset(graph, 0, sizeof(graph));

    // 木の作成
    for (int i=0; i<proportions.size(); i++) {
      int num1 = proportions[i][1] - '0';
      int num2 = proportions[i][8] - '0';
      int ratio1 = proportions[i][13] - '0';
      int ratio2 = proportions[i][15] - '0';
      graph[num1][num2] = ratio1;
      graph[num2][num1] = ratio2;
    }

    //     for (int i=0; i<=proportions.size(); i++) {
    //       for (int j=0; j<=proportions.size(); j++)
    //         cout << graph[i][j] << " ";
    //       cout << endl;
    //     }

    queue <pair <int, int> > q;

    // 始点の探索
    for (int i=0; i<=proportions.size(); i++) {
      int counter = 0;
      int index = 0;
      for (int j=0; j<=proportions.size(); j++)
        if (graph[i][j] != 0) {
          counter++;
          index = j;
        }
      if (counter == 1) {
        q.push(make_pair(i, index));
        break;
      }
    }

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

      int ratio1 = graph[cur.first][cur.second];
      int ratio2 = graph[cur.second][cur.first];
      graph[cur.second][cur.first] = 0;

      for (int i=0; i<=proportions.size(); i++)
        if (graph[cur.second][i] != 0)
          q.push(make_pair(cur.second, i));

      if (ret[cur.first] == 0 && ret[cur.second] == 0) {
        ret[cur.first] = ratio1;
        ret[cur.second] = ratio2;
      } else {
        int mul_for_cur = 0;
        int mul_for_exist = 0;
        int index = 0;
        if (ret[cur.first] != 0) {
          mul_for_cur = ret[cur.first] * ratio2;
          mul_for_exist = ratio1;
          index = cur.second;
        } else {
          mul_for_cur = ret[cur.second] * ratio1;
          mul_for_exist = ratio2;
          index = cur.first;
        }

        for (int i=0; i<ret.size(); i++)
          ret[i] *= mul_for_exist;

        ret[index] = mul_for_cur;
      }
    }

    // 最大公約数を求めて割る
    int divisor = ret[0];
    for (int i=1; i<ret.size(); i++)
      divisor = gcd(divisor, ret[i]);

    for (int i=0; i<ret.size(); i++)
      ret[i] /= divisor;

    return ret;
  }
};

2009-12-03

SRM429 div2 (過去問)

15:24

Easy - LinearPolyominoCovering

"..XXXX..XX...XXXXXX.."このような文字列が与えられるので,"X"の部分を,"AAAA"か"BB"で置き換えて返す.その際,辞書順で早いものを返す.不可能なら"impossible"を返す.先の例だと答えは"..AAAA..BB...AAAABB.."となる.

つながっているXの数が奇数なら"impossible"そうでないなら,できるだけ"AAAA"を優先して挿入する.という方法で書いたのですが,非常に時間がかかってしまいました.スコアも180点台です.

class LinearPolyominoCovering {
public:
  string findCovering(string region) {
    string ret;
    
    for (int i=0; i<region.size(); i++) {
      if (region[i] == 'X') {
        int counter = 0;

        for (int j=i; j<region.size(); j++) 
          if (region[j] == 'X')
            counter++;
          else
            break;

        if (counter % 2 != 0)
          return "impossible";

        int anum = counter / 4;
        int bnum = counter % 4;

        for (int j=0; j<anum; j++)
          ret += "AAAA";
        for (int j=0; j<bnum; j++)
          ret += "B";

        i += counter-1;
      } else if (region[i] == '.') {
        ret += ".";
      }
  
    }
    return ret;
  }
};

Medium - SubrectanglesOfTable

問題文は省略.非常に時間がかかりました.たぶん一時間以上.

"全ての矩形をカウントした場合,tableの各位置は何回出現するか"を考えます.例えば,2x2のtableを考えます.文字は仮に以下のようになっているとします.(問題の条件からはありえません)

AB
CD

この場合,全ての矩形は,

AB AB .. A. .B A. .B .. ..
CD .. CD C. .D .. .. C. .D

ここで,各数字の出現頻度は,以下のようにすべて4回です.

4 4
4 4

この値には,次のような法則があります.

MxNの大きさのtalbeのi, j要素の値は,(大きさMx1のtableのi番目の要素の値) * (大きさNx1のtalbeのj番目の要素の値)

図で表すとこんな感じです.

f:id:cou929:20091203151620j:image

この法則に従って,各位置のアルファベットの出現回数をカウントすれば,答えが出ます.

次にNx1のtableの値の求め方です.次のような法則があります.例えばN=5の場合,

1番目: 5 = 1 + 1 + 1 + 1 + 1
2番目: 8 = 1 + 2 + 2 + 2 + 1
3番目: 9 = 1 + 2 + 3 + 2 + 1
4番目: 8 = 1 + 2 + 2 + 2 + 1
5番目: 5 = 1 + 1 + 1 + 1 + 1

以上を実装したのが以下のコードです.デバッグに非常に時間がかかりました.他の人のコードはもっと全然短かったので,もっとスマートな方法があるはずです.

class SubrectanglesOfTable {
public:
  vector<long long> getQuantity(vector <string> t) {
    vector <long long> ret(26, 0);
    vector <int> row;
    vector <int> col;

    // talbeを作る
    vector <string> table;
    for (int i=0; i<t.size()*2; i++)
      if (i < t.size()) {
        string line = t[i];
        line += t[i];
        table.push_back(line);
      } else {
        table.push_back(table[i - t.size()]);
      }

    // 縦方向(talbe.size() x 1 の大きさ)のtableの数列を作る
    int center = table.size() / 2;
    if (table.size() % 2 == 1)
      center++;
    for (int i=0; i<table.size(); i++) {
      if (i < center) {
        vector <int> nums;
        for (int j=0; j<table.size(); j++)
          if (j < center)
            nums.push_back(min(i, j) + 1);
          else
            nums.push_back(nums[table.size() - 1 - j]);

        int num = 0;
        for (int j=0; j<nums.size(); j++)
          num += nums[j];
        col.push_back(num);
      } else {
        col.push_back(col[table.size() -1 - i]);
      }
    }

    // 横方向(talbe[0].size() x 1 の大きさ)のtableの数列を作る
    center = table[0].size() / 2;
    if (table[0].size() % 2 == 1)
      center++;
    for (int i=0; i<table[0].size(); i++) {
      if (i < center) {
        vector <int> nums;
        for (int j=0; j<table[0].size(); j++) {
          if (j < center)
            nums.push_back(min(i, j) + 1);
          else
            nums.push_back(nums[table[0].size() - 1 - j]);
        }

        int num = 0;
        for (int j=0; j<nums.size(); j++)
          num += nums[j];
        row.push_back(num);
      } else {
        row.push_back(row[table[0].size() -1 - i]);
      }
    }

    // 頻度のカウント
    for (int i=0; i<table.size(); i++)
      for (int j=0; j<table[0].size(); j++) {
        ret[table[i][j] - 'A'] += (long long)col[i] * (long long)row[j];
      }

    return ret;
  }
};

2009-12-02

SRM449 div2 (過去問)

01:59

Hard - HexagonalBattlefieldEasy

各マスが正六角形のフィールドがある.いくつかの入れないマスが与えられる.プレイヤーは大きさが2マス分の駒をもっている.フィールドをこの駒でしきつめる方法は何通りあるか.

greedyに駒を置いていくアルゴリズムを用いました.計算量は,Nが高々4(マス数は37)なので,まあたぶん大丈夫だろうと,半分勘で判断しました.

六角形のフィールドは,ふつうの二次元配列で表現する事にしました.例えばN=3の場合,こんな風になります.

**...
*....
.....
....*
...**

一番左下の"."が座標(0, 0),"*"は範囲外のマスです.

また,六角形のフィールドなので,あるマス(x, y)を起点としたとき,このマスを含んだ駒の置き方は6通り(上,右,左,下,右上,左下)になります.このルールのもとで,とにかく置ける全ての置き方で駒を一つずつ置いていくという,グリーディなアプローチをとっています.

時間はかかったけど,一発でsystem testに通って満足です.

class HexagonalBattlefieldEasy {
public:
  vector <string> splits(const string _s, const string del) {
    vector <string> ret;
    string s = _s;

    while (!s.empty()) {
      size_t pos = s.find(del);
      string sub = "";
      sub = s.substr(0, pos);
      ret.push_back(sub);
      if (pos != string::npos)
        pos += del.size();
      s.erase(0, pos);
    }

    return ret;
  }

  int table[7][7];
  int N;
  int ret;

  pair <int, int> searchStart() {
    int len = N*2-1;
    for (int i=0; i<len; i++)
      for (int j=0; j<len; j++)
        if (table[i][j] == 0)
          return make_pair(i, j);
    return make_pair(-1, -1);
  }

  bool isInRange(int x, int y) {
    if (0 <= x && x < N*2-1 && 0 <= y && y < N*2-1)
      return true;
    return false;
  }

  int r(pair <int, int> pos) {
    int curx = pos.first, cury = pos.second;
    int dirx[6] = {1, 0, -1, -1, 0, 1};
    int diry[6] = {0, -1, -1, 0, 1, 1};

    for (int i=0; i<6; i++) {
      int nextx = curx + dirx[i], nexty = cury + diry[i];
      if (isInRange(nextx, nexty) && table[nextx][nexty] == 0) {
        table[curx][cury] = table[nextx][nexty] = 1;

        pair <int, int> tmp = searchStart();
        if (tmp.first != -1)
          r(tmp);
        else
          ret++;

        table[curx][cury] = table[nextx][nexty] = 0;
      }
    }

    return 0;
  }

  int countArrangements(vector <int> X, vector <int> Y, int _N) {
    ret = 0;
    N = _N;
    memset(table, 0, sizeof(table));
    vector <string> black_list;
    black_list.push_back("");
    black_list.push_back("20");
    black_list.push_back("30 40 41");
    black_list.push_back("40 50 60 51 61 62");

    vector <string> tmp = splits(black_list[N-1], " ");
    for (int i=0; i<tmp.size(); i++) {
      int a = tmp[i][0] - '0', b = tmp[i][1] - '0';
      table[a][b] = 1, table[b][a] = 1;
    }

    for (int i=0; i<X.size(); i++)
      table[X[i] + N-1][Y[i] + N-1] = 1;

    pair <int, int> t = searchStart();
    if (t.first != -1)
      r(t);
    else
      ret++;

    return ret;
  }
   

};