Hatena::Grouptopcoder

kohei0418の練習帳

|

2012-04-15

TCO12 Round1C

19:50

xox 300.53

1293 -> 1306

Easy250 PasswordXGuessing, Failed System Test

  • なんか本番中は難しく考えすぎていた
  • 単純に,guesses[0]の各桁を0-9まで動かして解候補を作り,guessesのすべての文字列と整合性が取れるかチェックするだけでよかった
  • 解候補の数 50 * 10 × チェックにかかる時間 50 * 50 なので計算時間も余裕
bool check(string fixed, VS &g) {
  REP(i, g.size()) {
    int error = 0;
    REP(j, fixed.size()) {
      if(fixed[j] != g[i][j]) error++;
    }
    if(error != 1) return false;
  }
  return true;
}

class PasswordXGuessing {
public:
  long long howMany( vector <string> guesses ) {
    guesses.erase(unique(ALL(guesses)), guesses.end());
    
    int n = guesses.size();
    int m = guesses[0].size();

    ll res = 0;
    REP(j, m) {
      string fixed = guesses[0];
      REP(x, 10) {
        fixed[j] = x + '0';
        if(check(fixed, guesses)) res++;
      }
    }

    return res;
  }
};

Mid500 PasswordXGrid, Accepted

  • 最長パスの重みが答えになるんじゃないかと直感,なんか合ってたらしい
int n, m;
int dp[44][44]; // dp[x][y]

class PasswordXGrid {
public:
  int minSum( vector <string> h, vector <string> v ) {
    n = h.size()-1;
    m = v[0].size()-1;
    //dump(n); dump(m);

    dp[0][0] = 0;
    FORE(x, 1, m) dp[x][0] = dp[x-1][0] + h[0][x-1] - '0';
    FORE(y, 1, n) dp[0][y] = dp[0][y-1] + v[y-1][0] - '0';
    
    FORE(x, 1, m) {
      FORE(y, 1, n) {
        dp[x][y] = max(dp[x-1][y] + h[y][x-1] - '0', dp[x][y-1] + v[y-1][x] - '0');
      }
    }
    
    return dp[m][n];
  }
};

2012-02-24

SRM534 div1

00:10

oxx 133.28

1268 -> 1281

Easy250 EllysCheckers, Accepted

  • cellを特定のルールに従って動かすゲームで,先手が勝てるかどうかを判定する問題.
  • 場のサイズは最大20なので,状態をintで表せばdp/メモ化再帰できそう
  • 現在の状態から各cellを動かした状態を考え,負けとなる状態が1つでもあれば現在は勝ちの状態となる
  • メモ化再帰で実装
  • 右端に到達したcellを消す処理を加えていなくて,答えが合わず少し時間を食ってしまった
反省
  • 負けの状態なら現在は勝ち
  • なんか賢いやり方があったらしいが,本番中には思いつかなかった
  • でもまぁ苦手なdp系問題が解けたからいいかー

2012-02-19

SRM533 div1

15:51

xxx 0.0

1293 -> 1268

3回連続で一問も解けていない…精進せねば!

Easy250 CasketOfStar, Challenged

  • 得られる利益が最大なもののうち,最小のweightを持つstarを選択するGreedyアルゴリズムで解いた
    • テストケースは全部通ったし,反例も見つからなかったのでsubmit
  • すぐにchallengeされてしまった…
反省
  • 実は簡単なdpで解ける問題だったらしい

Mid500 MagicBoard

  • オイラーグラフの理論と,グラフが連結かどうかの判定で解ける?
  • turn数の偶奇で縦横移動の制限される,ということをどう組み込めばよいのかわからなかった

2012-02-10

SRM532 div1

19:13

xxx 0.0

1305 -> 1293

Easy300 DengklekMakingChains, Failed System Test

  • 連続するchainの整数値を最大化するので,chainの順序は関係ない
  • "xxx"な形のchainはいくらでもつなげることができる.問題は両端がどうなるか.
  • 左端候補は"ddx"; dのどちらか一方は"."
  • 右端候補は"xdd"; dのどちらか一方は"."
  • 左端と右端の全組み合わせを試して,この最大値と"xxx"はchainの値の和を加算
  • ただし,".x."などの場合を考慮していないので,最後にどっちが大きいか比較
反省
  • chainが1つしか与えられなかったときの処理が微妙で,System Testで落とされてしまった
  • ミニマルなケースに関してしっかりテストすべき,という教訓が得られた

Mid450 DengklekBuildingRoads

  • 各ノードの次数の偶奇と,使ったエッジ数を状態とすればdpできそう,と妄想
  • でもノード数が最大30ということは偶奇の状態数は2^30になる.時間もメモリも足りない
  • やっぱりdp力たりてない.

2012-02-01

SRM531 div1

22:21

xxx 0.0

1320 -> 1305

0点なのにあんま下がらなくて良かった^^;

Easy300 NoRepeatPlaylist

  • 300!?
  • DP臭.でもどうやってDPを組み立てればいいかわからん!
  • しかたないので,2つのルールを満たすようなplaylistをベタに数え上げるプログラムを書いてみる
  • 答えは合ってるっぽいが,テストケース5が終わらない.当たり前か.
反省
  • DP力つけよう!
|