蒼くなった日〜SRM 472 DIV2〜 - div1に上がりたいkeitanxkeitanの日記

久々のTopCoder

最近疎遠になっていたTopCoder。約２ヶ月ぶり。
心機一転のため、気まぐれアカウントkxkから、いつもの
keitanxkeitanに移行した。
そんな節目のTopCoder SRM 472。
レーティングは1000からスタート！

ColorfulTilesEasy



DIV1の簡易版。

R,G,B,Yの４色で塗りわけられた部屋を隣接するセルが

同じ色にならないように塗り替えるために最低何回の塗り替えが必要かどうか

２色続けて同じ色だったら塗り替えが必要。３色続いてる場合は、
前２色のことは忘れてしまってよい。

e.g "RRR" → "RGR" となって３色目のRは分断されるから

これはさっさと提出したかったけど、CodeProcessorでJavaのコードを生成してしまって、結局いつものC++テンプレートでクラスを１から書き出して遅くなってしまった。テストも手元でできなかったし…。

人のブログ読んで設定しただけで、ちゃんと仕組みがわかってなかったから対応出来なかった。反省。

class ColorfulTilesEasy {
public:
  int theMin(string room) {
    char prev = 'X';
    int count = 0;
    for (int i = 0; i < room.size(); ++i) {
      if (room[i] == prev) {
	  ++count;
	  prev = 'X';
      } else {
	prev = room[i];
      }
    }
    return count;
  }
};

チャレンジフェイズでfor文をi+=2でやってる人に気付かずに凸して
減点食らった。

PotatoGame

ポテト大好き太郎と花子がブラックボックスの中から

順番にポテトを取り出して食べていく。太郎が先行で

一度に食べられるポテトの数は4^i(0<=i)個。

先に食べられなくなった方が負け。初期値nに対して

両者が最適な戦法を取った場合のWinnerを出力する。

ポテトって日本語的な意味でフライドポテト？
それなら納得行くけど、直訳でじゃがいもだったら
気味が悪い２人だと思う。

これは太郎のhotspotとcoldspotを小さいケースから埋めていって
法則性を見つけた。見つからなかったらfor n in 1..1,000,000,000で
bool isHotspot[1,000,000,000]を埋めていくつもりだった。これは間に合うのだろうか？

まずn=0はcoldspot。n=1は１個食べると花子にcoldspotで回せるからhotspot。n=2は１個食べると花子にhotspotで回してしまうからcoldspot。n=3は…というように表を書いてみたら以下のようになった。



n    1  2  3  4  5  6  7  8  9 10 11 12 13 14 ...

H/C  H  C  H  H  C  H  C  H  H  C  H  C  H  H ...

n % 5 == 0 or n % 5 == 2でcoldspotになっている
16個食べられる状況になってもこの規則性は確認できたので、
これで提出した。チャレンジフェイズでは不安になったけど
生き残って、システムテストも無事通過した。

class PotatoGame {
public:
  string theWinner(int n) {
    string result;
    if (n % 5 == 0 || n % 5 == 2) result = "Hanako";
    else result = "Taro";
    return result;
  }
};

RectangularIsland

長方形の島の大きさと初期位置、ステップ数が与えられたとき、

最後まで海に落ちない確率。四方に同確率で移動できる。

書いたコードがテストケース５つ目でTLEで引っかかって出せなかった。

メモ化したつもりだったけど。

#define Inf 1<<29

double cache[1000][1000][5001];

int dx[4] = { 0,  1,  0, -1};
int dy[4] = { 1,  0, -1,  0};

int W, H;

class RectangularIsland {
public:
  bool valid(int x, int y) {
    return x >= 0 && x < W && y >= 0 && y < H;
  }

  double rec(int x, int y, int steps) {
    if (steps == 0) return 1.0;
    if (cache[x][y][steps] != Inf) return cache[x][y][steps];
    double ret = 0.0;
    for (int i = 0; i < 4; ++i) {
      int nx = x + dx[i], ny = y + dy[i];
      if (valid(nx, ny)) {
	ret += 0.25 * rec(nx, ny, steps-1);
      }
    }
    return cache[x][y][steps] = ret;
  }
  double theProbablity(int width, int height, int x, int y, int steps) {
    W = width, H = height;
    double result;
    for (int i = 0; i < W; ++i)
      for (int j = 0; j < H; ++j)
	for (int k = 0; k <= steps; ++k)
	  cache[i][j][k] = Inf;
    result = rec(x, y, steps);
    return result;
  }
};

何はともあれ1000→1424で蒼くなった！
維持費用を払えるように頑張りたい（＾ｐ＾）