Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-07

SRM454 div2 (再チャレンジ)

23:41

Hard - NumbersAndMatches

dpで解きます. 3次元配列を用意し, [何文字目の数字を処理しているか(最大18)][加えたマッチの本数][取り除いたマッチの本数]の場合の組み合わせの数をそれぞれ保存します. Nを最初から一文字ずつループさせ, 現在みているNの一文字に対して, 0-9まで, 何本のマッチを加える/除く必要があるかを計算します. これらの値について, 先述の配列に保存します. 最後に配列の, [Nの桁数][i][i]となる要素の値を総和して, 解とします. [i][i]としているのは, 加えたマッチの数と除いたマッチの数が同じ, つまりきちんと移動が完結しているということになります.

数字は7桁のビット(実際には"1"と"0"からなるstring)に保存します. こうすれば, 単に各桁ごとに差をとるだけで, 加えた/除いたマッチの数を求めることができます.

div1と同じ問題だと, topcoder部の諸先輩方の考え方やコードがブログで読めて, とても参考になります.

class NumbersAndMatches {
public:
  long long differentNumbers(long long N, int K) {
    char  match_nums[10][8] = {"1110111", "0010011", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
    const int MAX_ADD = 200;
    const int MAX_REM = MAX_ADD;
    long long dp[19][MAX_ADD][MAX_REM];
    int digit_num = 0;

    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;

    while (N > 0) {
      int cur_num = N % 10;
      N /= 10;
      digit_num++;

      for (int i=0; i<10; i++) {
        int add_num = 0;
        int remove_num = 0;
        for (int j=0; j<7; j++)
          if (match_nums[cur_num][j] - match_nums[i][j] > 0)
            remove_num++;
          else if (match_nums[cur_num][j] - match_nums[i][j] < 0)
            add_num++;

        for (int j=add_num; j<=K; j++)
          for (int k=remove_num; k<=K; k++)
            dp[digit_num][j][k] += dp[digit_num-1][j-add_num][k-remove_num];
      }
    }

    long long ret = 0;
    for (int i=0; i<=K; i++)
      ret += dp[digit_num][i][i];

    return ret;
  }
};