SRM 568 Div I

SRM 568 Div I

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

250に30分。141.45点。前回に続き点数は低かったが、レートは1271から1312に上がった。Room 20

Problem Status Points
250 TheSimilarNumbers System Test Passed 141.45
500 EqualSums Opened 0.00
1000 ShuffleSort Unopened
  • 250を素直にグリーディーで実装したが、答えが合わなかった
  • 20分ほどして何が悪いかに気付き、メモ化再帰で再実装を行った
  • 10分ほどで実装を終え、提出。システムテストをパス
  • 500は全く分からなかった
  • 250のチャレンジネタを考えたりもしたが、思いつかなかった
  • 「Div I Easyを奇麗な実装で提出する」という目標はまあ達成した
  • 次回の目標も「Div I Easyを奇麗な実装で提出する」とします!

TheSimilarNumbers

http://community.topcoder.com/stat?c=problem_statement&pm=10553&rd=15488

30分。141.45点。

  • 何の疑問も持たずにグリーディーな実装を行った
    • 答えが合わない...
  • 開始から20分ほどでやっと題意に気付いた。以下はサンプル0と同様の図だ


  • 以下のように赤の箱、緑の箱、青の箱に *集めて* みよう。このとき玉の移動回数は2 × 2 × 3 = 12回


  • Div I Easyにしては簡単すぎやしないか? と思いつつも素直にグリーディーな実装を行う
    • 結果が合わない
  • 10分ほど悩んだ後に、同じ色の玉を一つの箱に集めなくてもよいことに気付く
  • それぞれの玉は少なくとも1つあるという制約より箱の数が4つ以上あるときにこれが起こることが分かる


  • 同じ色の玉を一つの箱に集めた場合の移動回数は2 × 4 × 3 = 24回


  • 同じ色の玉を一つの箱に集めなければ、移動回数は4 × 5の20回で済む


  • 上の図では箱0、1、2に赤、緑、青の玉を集めているが、そうする必要は必ずしもない。例えば以下の例の移動回数も20回であるし、


  • 以下の場合の移動回数も20回だ


  • つまるところ、箱に格納する玉の色を決めたら、他の色の玉を別の箱に *追い出して* しまえばよい
    • 他の色の玉がどの箱に格納されることになるかは気にしなくてもよい
  • かといって何も考えず単純に移動を行ってしまうとある色の玉の行き先がなかった、ということになりかねない。そのため、それぞれの色の玉が格納される先が必ず一つ必要


  • 何かが見えてきた
    • メモ化再帰で考えることが出来そうだ
  • それぞれの箱でそれぞれの色を選んだ場合を試して、移動回数が最小のものを返せばよい
  • 次の箱を試すときはどの色の箱がすでにあるかを教えてやる。これはビットで渡してやることにする
  • 全ての箱に対する処理を終えたときに何れかの色の箱が用意されていなかった場合、箱に格納されていない迷子の色の玉があるはずだ。この場合は無効であるので、無効を意味する無限大を返してやる
  • 計算量は以下となる。Cは色の数、Nは箱の数


  • この問題の場合、扱う色の数は決まっているのでO(N)であると言える


  • この件に関してはSRM後、@evima0さんにもご教授いただいた

  • @evima0さん、どうもありがとうございます

提出した実装は以下(システムテストをパス)。

const int INF = 1 << 30;


class BallsSeparating {
public:
  int minOperations(std::vector<int> red, std::vector<int> green, std::vector<int> blue) {
    red_   = red;
    green_ = green;
    blue_  = blue;

    size_ = red.size();

    if (size_ < 3)
      return -1;

    memo_.clear();

    return dfs(0, 0);
  };

private:
  int dfs(int i, int j) {
    std::pair<int, int> key(i, j);

    if (memo_.count(key))
      return memo_[key];

    if (i == size_)
      if (j == 7) {
        return 0;
      }
      else {
        return INF;
      }
    
    int c = INF;

    c = std::min(dfs(i + 1, j | 1)           + green_[i] + blue_[i], c);
    c = std::min(dfs(i + 1, j | 2) + red_[i]             + blue_[i], c);
    c = std::min(dfs(i + 1, j | 4) + red_[i] + green_[i],            c);

    return memo_[key] = c;
  };

private:
  std::vector<int> red_;
  std::vector<int> green_;
  std::vector<int> blue_;

  int size_;

  std::map<std::pair<int, int>, int> memo_;
};
  • よかったよかった
  • チャレンジ中のコードリーディングやSRM後のTLを見るにグリーディー解が大半を占めていた
  • 全く思いつかなかったため、考えてみた
  • 赤、緑、青、それぞれの箱をまず決めてしまう。すると迷子になる玉はなくなる。その上で玉の移動回数を計算すればよい
  • ある色の玉専用の箱からは他の色の玉を追い出してしまおう
  • どの色の玉専用、と決めていない箱からは一番玉の移動回数が少ない方法を選ぼう。その数は以下の式で計算できる


  • 問題はどの箱を赤の箱とし、どの箱を緑の箱...、と決めることだ。これは予め決められない
  • 決められないのであれば全ての組み合わせを試してしまえばよい
  • ざっと考えるとO(N4)となる。細かく言えば、


  • 制約によりN ∈ [1, 50]であるので、十分間に合う

以下はグリーディー解の実装(システムテスト済)。

class BallsSeparating {
public:
  int minOperations(std::vector<int> red, std::vector<int> green, std::vector<int> blue) {
    int size = red.size();

    if (size < 3)
      return -1;

    int cp = 2.0e+9;

    for (int i = 0; i < size; i ++)
      for (int j = 0; j < size; j ++)
        for (int k = 0; k < size; k ++)
          if (i != j && j != k && k != i) {
            int c = 0;

            for (int l = 0; l < size; l ++)
              if (i == l) {
                c += green[l] + blue[l];
              }
              else if (j == l) {
                c += red[l] + blue[l];
              }
              else if (k == l) {
                c += red[l] + green[l];
              }
              else {
                c += red[l] + green[l] + blue[l] - std::max(red[l], std::max(green[l], blue[l]));
              }

            cp = std::min(cp, c);
          }

    return cp;
  };
};
  • うーん、計算量は確かに多いがグリーディー解のほうが間違え辛そうだ
    • しかし、思いつかなかった
  • どちらかというと、今はグリーディーよりもメモ化再帰を含む動的計画法で解きたいので、今回はよしとする
  • 「Div I Easyを奇麗な実装で提出する」という目標もまあ達成できたとしよう
  • 次回もこの目標を達成できるように頑張る