Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2009-12-06

NumbersAndMatches (SRM454 DIV1Comments Medium)

| 18:06 | NumbersAndMatches (SRM454 DIV1Comments Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - NumbersAndMatches (SRM454 DIV1Comments Medium) - TopCoder煮ブログ

答えを見ても全く分からずに一日悩んだ。いろいろ探す過程で「今回の500は簡単」という発言をみて萎える。

今回は、桁の数を増やしながら計算するのが一番外側のループ。表に記憶するのは、1つ前の桁の過不足を含んだ数の個数。

DP

追加数と減少数の表をまず作る

del\add01234
010000
100000
200000
300000

最初に処理する桁が「2」のときは、それぞれの数に移動したときの数を記録する。

del\add01234
010100
101300
200100
301200

(0,0)は2から2に遷移するとき(つまり移動は発生しない)。(1,1)が2から1に遷移するとき(1個減らして1個追加、つまり1回の移動)。

(2,1)は2から0,6,9に遷移するとき。たとえば、2から0に遷移するには2個追加して1個減ったらいける。このままだと過不足が発生しているが、この次の桁で1個減らす遷移が発生すると、過不足は解消される。

さて、次の桁。

たとえば次の桁が「2」のときは、2から10通りの数に移る場合の移動を計算する。この移動方法を(0,0)からだけじゃなく、その他の数字がある場所全てに適用して、2桁目を変えた全パターンについて移動先の数を求める。

こんな感じで全ての桁について DP 表を更新したら、最後に K 個の対角線の数を足し合わせる。対角線というのは、マッチの移動が過不足なく行えた場所。

ソース

cafelier 先生のソースを解読してコメントつけてみた。


#include <string>
#include <vector>
#include <numeric>
#include <iostream>
using namespace std;

//   0
// 1   2
//   3
// 4   5
//   6
char* NUMBERS[] = {
    "1110111", //0
    "0010011", //1
    "1011101", //2
    "1011011", //3
    "0111010", //4
    "1101011", //5
    "1101111", //6
    "1010010", //7
    "1111111", //8
    "1111011", //9
};
int DP[18][200][200];

class NumbersAndMatches {

public:
    // a から b へ遷移するときに追加、削除するマッチの数を取得する
    void diff(int a, int b, int* add, int* del){
        for(int i = 0; i < 7; i++){
            if(NUMBERS[a][i] < NUMBERS[b][i]) *add += 1;
            else if(NUMBERS[a][i] > NUMBERS[b][i]) *del += 1;
        }
    }

    long long differentNumbers(long long N, int K) {
        // DP の領域を初期化する
        memset(DP, 0, sizeof(DP));
        DP[0][0][0] = 1;

        // 一桁ずつ処理していく
        int cnt = 0;
        while(N){
            // 処理する桁の数字を取得する
            int n = N % 10;
            N /= 10;
            cnt++;
            
            // 追加する回数、減らす回数を総当りする
            for(int i = 0; i < K; i++){
                for(int j = 0; j < K; j++){
                    // cnt 番目の数が k になるとき
                    for(int k = 0; k < 10; k++){
                        // マッチの増加数、減少数を調べる
                        int add = 0, del = 0;
                        diff(n, k, &add, &del);

                        // 移動数が上限 K を超えないときは、
                        // DP の表に記録する
                        if(add + i < K && del + j < K){
                            // 次の場所の数に n から k に移動する数を追加する
                            DP[cnt][add+i][del+j] += DP[cnt - 1][i][j];
                        }
                    }
                }
            }
        }

        // 対角線の値を K 個足し合わせる
        long long ret = 0;
        for(int i = 0; i <= K; i++){
            ret += DP[cnt][i][i];
        }
        return ret;
    }
};