Hatena::Grouptopcoder

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

 | 

2012-08-04

Single Round Match 551 03:45 Single Round Match 551 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Single Round Match 551 - nodchipのTopCoder日記 Single Round Match 551 - nodchipのTopCoder日記 のブックマークコメント

Easy 250 Colorful Chocolates

  • どれか一つを基準にして周囲の同じ色の飴を集めてくれば良いのかな?
  • これを全ての飴について行う
  • 実装面倒そう・・・
  • とりあえず書いてみる
  • 書けた
  • 実行・・・
  • 止まらない・・・
  • デバッグ・・・
  • 実行・・・デバッグ・・・実行・・・デバッグ・・・
  • サンプル通った
  • Submit
  • Passed System Test
class ColorfulChocolates {
public:
  int solve(string choco, int maxSwaps, int centerIndex) {
    int n = choco.size();
    while (maxSwaps) {
      // toLeft
      int left;
      for (left = centerIndex; 0 <= left && choco[left] == choco[centerIndex]; --left)
        ;
      int leftFound;
      for (leftFound = left; 0 <= leftFound && choco[leftFound] != choco[centerIndex]; --leftFound)
        ;
      
      int right;
      for (right = centerIndex; right < n && choco[right] == choco[centerIndex]; ++right)
        ;
      int rightFound;
      for (rightFound = right; rightFound < n && choco[rightFound] != choco[centerIndex]; ++rightFound)
        ;

      int swapLeft, swapRight;
      if (0 <= leftFound) {
        if (rightFound < n) {
          if (left - leftFound < rightFound - right) {
            swapLeft = leftFound;
            swapRight = left;
          } else {
            swapLeft = right;
            swapRight = rightFound;
          }
        } else {
          swapLeft = leftFound;
          swapRight = left;
        }
      } else {
        if (rightFound < n) {
          swapLeft = right;
          swapRight = rightFound;
        } else {
          break;
        }
      }

      // Check max swap limit
      if (maxSwaps < swapRight - swapLeft) {
        break;
      }

      maxSwaps -= swapRight - swapLeft;
      swap(choco[swapLeft], choco[swapRight]);
    }

    int maxCont = 0;
    int cont = 0;
    char lastCh = 0;
    REP(i, n) {
      if (lastCh != choco[i]) {
        MAX_UPDATE(maxCont, cont);
        cont = 1;
        lastCh = choco[i];
      } else {
        ++cont;
      }
    }

    MAX_UPDATE(maxCont, cont);
    return maxCont;
  }

  int maximumSpread(string chocolates, int maxSwaps) {
    int result = 0;
    REP(i, chocolates.size()) {
      MAX_UPDATE(result, solve(chocolates, maxSwaps, i));
    }
    return result;
  }
}

Middle 450 Colorful Wolves

  • ん・・・
  • なんぞこれ・・・
  • ・・・
  • 解法わからん・・・
  • ・・・
  • なんかメモ付き探索的な何か・・・?
  • っていうかダイクストラするだけか・・・
  • 枝を取り除くときは若い番号のものから取り除いたほうが良いのだから・・・
  • 隣の枝に映るときに、番号の若い枝から順にコスト0、1、2と付けていけばいいのか
  • submit
  • Passed System Test
class ColorfulWolves {
public:
  int getmin(vector <string> colormap) {
    int n = colormap.size();
    int dp[64];
    fill_n(dp, sizeof(dp) / sizeof(dp[0]), INT_MAX);
    dp[0] = 0;

    // cost, node
    multiset<pair<int, int> > q;
    q.insert(MP(0, 0));
    while (!q.empty()) {
      int currentCost = q.begin()->first;
      int currentNode = q.begin()->second;
      q.erase(q.begin());

      if (currentCost != dp[currentNode]) {
        continue;
      }

      int nextCost = currentCost;
      REP(nextNode, n) {
        if (colormap[currentNode][nextNode] != 'Y') {
          continue;
        }

        if (dp[nextNode] > nextCost) {
          dp[nextNode] = nextCost;
          q.insert(MP(nextCost, nextNode));
        }

        ++nextCost;
      }
    }

    int result = (dp[n - 1] == INT_MAX ? -1 : dp[n - 1]);
    return result;
  }
  • 以下は終了後にワーシャル・フロイド法で書きなおした版です
class ColorfulWolves {
public:
  int getmin(vector <string> colormap) {
    int n = colormap.size(), g[64][64], inf = INT_MAX / 3;
    REP(i, n) {
      int cost = 0;
      REP(j, n) g[i][j] = colormap[i][j] == 'Y' ? cost++ : inf;
    }
    REP(k, n) REP(i, n) REP(j, n)
      MIN_UPDATE(g[i][j], g[i][k] + g[k][j]);
    return g[0][n - 1] == inf ? -1 : g[0][n - 1];

Hard 1000 Sweet Fruits

  • グラフかぁ・・・
  • n<=40と言うことは半分列挙・・・?
  • 何れにしても分からない
  • wataさんとか解くんだろうなぁ・・・
  • Opened

Challenge Phase

  • 250で変なことをしている人を下る
  • なんか変なコードを見つけた
  • 書き写して手元で実行してみる
  • なんかサンプルが通らない
  • 書き写したコードを見なおしてみる
  • 添字間違ってた
  • 修正したらサンプル通った。あぶないあぶない。
  • 危うくサンプル投げるところだった
  • 時間食ってしまった
  • 後は怪しいコードは見つからない・・・
  • 終了

System Test

  • oox 111位

2117->2138 いつもならそろそろガクンと落ちる頃なのですが、何故かだんだんと上がっています。不気味です。

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