WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM567 Div2 Hard "MountainsEasy"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12380

訳(簡単に)

H * Wのグリッド上に点が並んでいる。
最初、全ての点は'.'となっている。

下記のような操作をN回行う。
任意の点を選ぶ。
選んだ点が(x, y)とすると、まず(x, y)を'.'から'X'に変える。
それから一段下がって(x-1, y+1), (x, y+1), (x+1, y+1)を'X'に変える。
それから一段下がって(x-2, y+2), (x-1, y+2), (x, y+2),
(x+1, y+2), (x+2, y+2)を'X'に変える。
これを一番下の段まで繰り返す。

例)

(4, 3)を選ぶ
0......     0......
1......     1......
2...... ->  2......
3......     3....X.
4......     4...XXX
 012345      012345

続いて(0, 1)を選ぶ
0......     0......
1......     1.X....
2...... ->  2XXX...
3....X.     3XXXXX.
4...XXX     4XXXXXX
 012345      012345

最終的な点の状態と、操作回数Nが与えられるので、
そのような状態になる点の選び方の数を返せ。

制約

1 <= H, W <= 50
1 <= N <= 50



解法

こちらを参考にさせて頂きました。m(_ _)m
TopCoder SRM 567 Div2 Hard MountainsEasy - kmjp's blog

まず、必ず選ばなくてはならない点(F)とどうでもいい点(E)があるので、
それぞれの点の数を出しておく。
Fの点を1つ以上選ぶようなFとEの点の選び方の数が答えとなる。

その求め方ははkmjpさんのブログにも書かれているとおり、SRM567 Editorialsの解法が鮮やか。

どうでもいい点を選んだ時

具体的に、選ぶ点の数(N)を4、1回以上選ばなくてはならない点(Fの点)の数を2
選ばなくてもよい点(Eの点)の数を4とする。
f:id:Ekaing:20130331214313j:plain

Eの点から選ぶと
f:id:Ekaing:20130331214417j:plain

状態は、Nが1つ減る
f:id:Ekaing:20130331214540j:plain

なので、(N=4 F=2 E=4)において、Eの点を選んだ時の選び方の数は、
Eの点が4つあるので、(N=3 F=2 E=4)の選び方の数に4を掛けたものとなる。

1回以上選ばなくてはいけない点を選んだ時

Fの点から選ぶと
f:id:Ekaing:20130331215137j:plain

状態は、Nが1つ減るとともに、Fが1つ減り、Eが1つ増える
f:id:Ekaing:20130331215239j:plain

なので、(N=4 F=2 E=4)において、Fの点を選んだ時の選び方の数は、
Fの点が2つあるので、(N=3 F=1 E=5)の選び方の数に2を掛けたものとなる。


最終的に(N=4 F=2 E=4)の時の選び方の数は、
(N=3 F=2 E=4) * 4 + (N=3 F=1 E=5) * 2となる。

あとはこれを再帰的にやっていけばよい。
ただし、Nが最大50あるので、このままだと計算量が2^50になってしまう。
よって、N Fのそれぞれの状態のときの結果をメモしていく。
F + E = 6で、EはFに依存するのでEについてはメモをとる必要はない。


ソースコード

Editorialを訳しただけみたいな感じだけど一応

const int MOD = 1000000009;
// memo[n][f]
//選ぶポイントが残りn個で、
//選ばなきゃいけないポイントがf個残っているときの 
//ポイントの選び方の総数
int memo[55][55];

class MountainsEasy {
public:

    /*
     * N,E,Fの状態の時のポイントの選び方の数を返す。
     *
     * N - 残りの数
     * E - どうでもいいポイントの総数 
     * F - 選ばなきゃいけないポイントの総数
     */
    long long dfs( int N, int E, int F ){

        // メモがあればそれを返す
        int& m = memo[N][F];
        if( m != -1 ) return m;

        long long res = 0;
        if( N == 0 ){
            // Fの点が残っていたら、そのような点の選び方はダメ
            res = (F == 0 ? 1 : 0);
        }else{
            // どうでもいいポイントを選択
            res += dfs( N-1, E, F ) * E;
            res %= MOD;
            // 選ばなきゃいけないポイントを選択
            if( F > 0 ){
                res += dfs( N-1, E+1, F-1 ) * F;
                res %= MOD;
            }
        }
        return m = (int)res;
    }

    int countPlacements(vector <string> picture, int N){
        int H = picture.size();
        int W = picture[0].length();
        
        // どうでもよいポイントEと選ばなきゃいけないポイントFの数を数える
        int E = 0, F = 0;
        for( int y = 0; y < H; y++ ){
            for( int x = 0; x < W; x++ ){
                if( picture[y][x] != 'X' ) continue;
                // ここは選ばなくてはならない
                F++;
                // 山になるところをドットにする
                for( int my = y; my < H; my++ ){
                    for( int mx = x - my + y; mx <= x + my - y; mx++ ){
                        if( mx < 0 || W <= mx ) continue;
                        if( picture[my][mx] != 'X' ) continue;
                        picture[my][mx] = '.';
                        // ここはどうでもいい
                        E++;
                    }
                }
                E--; // 選ばなくてはいけないポイントを含んでいるため
            }
        }
        
        // メモをリセット
        memset( memo, -1, sizeof(memo) );

        return (int)dfs( N, E, F );
    }
};