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];
  }
};
 |