TopCoder SRM練習 - SRM 511 DIV2 Easy

2011年7月13日水曜日

今日もちょいちょいと。
GameOfLifeDivTwo

・ライフゲームの変形版
・ドットが円形に並んでる
・状態Tでの各ポイントの生存状態は、その前(T-1)で自身プラスマイナス1つの計3つのうち2つ以上が生存していた(=>true)か否か(=>false)で決まる

ということで愚直に端っこをループさせてこういうふうに解いた。計算量的には、-1にあたる場所とNにあたる場所をもうちょい特殊に扱って毎回境界外をつなぐ処理を行わないようにすれば減らせそう。まあ、Top Submission見てもこんな感じ。途中喋りながらやってたというのはあるけど、さらっと書いてから配列のコピーで微妙にハマりprintfデバッグ繰り返した結果159.31。うーん、イマイチ。正答率91%、平均点183。

public class GameOfLifeDivTwo {

 public String theSimulation(String init, int T) {
  int setLen = init.length();
  boolean stateList[] = new boolean[setLen];
  boolean stateTmpList[] = new boolean[setLen];
  for (int i = 0; i < setLen; i++) {
   stateList[i] = init.charAt(i) == '1';
  }
  for (int i = 0; i < T; i++) {
   for (int j = 0; j < setLen; j++) {
    int liveCnt = 0;
    int nextIdx = j + 1;
    if (nextIdx == setLen) {
     nextIdx = 0;
    }
    if (stateList[nextIdx] == true) {
     liveCnt++;
    }
    int prevIdx = j - 1;
    if (prevIdx == -1) {
     prevIdx = setLen - 1;
    }
    if (stateList[prevIdx] == true) {
     liveCnt++;
    }
    if (stateList[j] == true) {
     liveCnt++;
    }
    stateTmpList[j] = 2 <= liveCnt;
   }
   for (int k = 0; k < setLen; k++) {
    stateList[k] = stateTmpList[k];
   }
  }
  String retStr = "";
  for (int i = 0; i < setLen; i++) {
   retStr = retStr.concat(stateList[i] == true ? "1" : "0");
  }
  return retStr;
 }

}

0 件のコメント:

コメントを投稿