Hatena::Grouptopcoder

cou929のTopCoder日記

2010-06-06

SRM 472 div2 (過去問)

01:07

午前3時という珍しい時間のSRM. つかれていたので本戦には参加していません. なんか難しいなあと思っていたら, writerがrng_58さんでした.

Easy - ColorfulTilesEasy

前から順に見ていき, 同じ色がつづいていた場合, 別の色を配置してカウンタをインクリメントします.

class ColorfulTilesEasy {
public:
  int theMin(string room) {
    int ret = 0;
    int i;
    int n = room.size();

    for (i=1; i<n; i++)
      if (room[i-1] == room[i]) {
        ret++;
        room[i] = 'A';
      }
    
    return ret;
  }
};

Medium - PotatoGame

最大ケースが100000000なので, o(n)のアルゴリズムでも間に合わなそうです. しかしいい解法が思いつかず, とりあえずメモ化探索を書いてみましたが, やはり間に合わず.

他の人のコードを見てみると, 5のmodで場合分けするというシンプルなものでした. たしかにこのようなパターンになっているのですが, 思いつくことはできなかったし, またそれで正しいと言う証明もまだしていません.

class PotatoGame {
public:
  string theWinner(int n) {
    string ret;
    ret = (n%5 == 0 || n%5 == 2) ? "Hanako" : "Taro";

   return ret;
  }
};