WARush

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

SRM573 Div2 Hard "TeamContestEasy"

N匹のオオカミがいて、各々の居る位置が
2次元座標x(0),x(1)...x(N-1) y(0),y(1)...y(N-1)で与えられている。
オオカミたちはM回動く。
オオカミが(x,y)にいるとすると、1回で(x+1,y)(x-1,y)(x,y+1)(x,y-1)の
いずれかに移動できる。

彼らの目標は、M回移動した時に、全員が同じポイントに到達する事である。
このポイントは任意に選べる。

彼らが目標を達成するような動き方が何パターンあるかを返せ。

制約

2 <= N <= 50
0 <= x(i), y(i) <= 50
1 <= M <= 50

ググル

おお、こんなものが!ありがたやありがたや~
SRM573 WolfPack 解説

うーん・・・nCk mod p の求め方がよく分からないんだよなぁ
ここはDPで行こう。
dp[t][dx][dy] := t回の移動で(x+dx, y+dy)マスに行く移動方法は何パターンあるか?
(50, 50)を原点とするとdp[0][50][50] = 1
配るDPだと更新の仕方はこう
dp[t+1][dx+1][dy] += dp[t][dx][dy];
dp[t+1][dx-1][dy] += dp[t][dx][dy];
dp[t+1][dx][dy+1] += dp[t][dx][dy];
dp[t+1][dx][dy-1] += dp[t][dx][dy];

このdpを使いまわせばいけそう。

ランデブーポイントは制約から
(-50 -50) ~ (100 100)の範囲に収まる。
これを1つ1つ調べていこう。

ソースコード
typedef long long ll;
const int MOD = 1000000007;

int dp[51][101][101]; 

class WolfPackDivTwo {
public:

    int calc(vector <int> x, vector <int> y, int m){
        int n = x.size();
        // dpを初期化
        for( int t = 0; t <= 50; t++ ){
            for( int dy = 0; dy <= 100; dy++ ){
                for( int dx = 0; dx <= 100; dx++ ){
                    dp[t][dy][dx] = 0;
                }
            }
        }
        dp[0][50][50] = 1;
        for( int t = 0; t < m; t++ ){
            for( int ty = 0; ty <= 100; ty++ ){  
                for( int tx = 0; tx <= 100; tx++ ){  
                    static int dx[] = { 0, 0, -1, 1 };
                    static int dy[] = { -1, 1, 0, 0 };
                    for( int d = 0; d < 4; d++ ){
                        int tty = ty + dy[d];
                        int ttx = tx + dx[d];
                        if( tty < 0 || 100 < tty || ttx < 0 || 100 < ttx ) continue;
                        dp[t+1][tty][ttx] += dp[t][ty][tx];
                        dp[t+1][tty][ttx] %= MOD;
                    }
                }
            }
        }

        // ランデブーポイントを一つ一つ調べる
        int res = 0;
        for( int ty = -50; ty <= 100; ty++ ){
            for( int tx = -50; tx <= 100; tx++ ){
                ll add = 1;
                for( int i = 0; i < n; i++ ){
                    int dx = 50 + tx - x[i];
                    int dy = 50 + ty - y[i];
                    if( dx < 0 || 100 < dx || dy < 0 || 100 < dy ) {
                        add = 0;
                    }else{
                        add = add * dp[m][dy][dx];
                    }
                    add %= MOD;
                }
                res += static_cast<int>(add);
                res %= MOD;
            }
        }
        return res;

    }
};