SRM 502 Div2 Hard TheCowDivTwo

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11352&rd=14431

0〜N-1の数字からK個選んだものの和がNで割り切れるような選び方の総数をもとめよ。

やりかた

Writer解を参考にしました。

DP。
dp[i][j][k]:=(i番目の数字まででk個選んだ時の和のmodがjになるような選び方の総数)でdp。
すると

dp[i + 1][k][j] = (dp[i][k][j] //i番目は選ばない
                 + dp[i][k - 1][(j - i + N) % N]) % MOD //i番目を選ぶ

となるのでこれで計算できる。
普通に書くとメモリオーバーになるので、i+1はiの時の状況のみに依存することを利用して、配列を2つ交互に入れ替えて省メモリに計算する。

以下ソース。

const int MOD = 1000000007;
int dp[2][50][1010];

class TheCowDivTwo {
public:
  int find(int N, int K) {
    int result;
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    for(int i = 0; i < N; i++){
      for(int j = 0; j < N; j++){
	dp[(i + 1) % 2][0][j] = dp[i % 2][0][j];
	for(int k = 1; k <= K; k++)
	  dp[(i + 1) % 2][k][j] = (dp[i % 2][k][j] 
				   + dp[i % 2][k - 1][(j - i + N) % N]) % MOD;
      }
    }
    return dp[N % 2][K][0];
  }
};

これはできるべきだった。dpしようとしてメモリたらないなあとかずっと考えていた。省メモリを思いつきすらしなかった。もちろんそこまできちんと詰めて考えられていなかったため、それ以前のところで足踏みしていただけだった。
DP強化週間とかやっていたがまだ身についているようには到底思えないし、実感もない。dpの状態のもたせ方もまだ過不足なく状態を記述できるように思いつくことができずにいる。まずDFSの全探索を考えて（こっちはわりとできる）、その状態をそっくりそのままDPに落とす、という基本的な作業をもういちど見つめなおしたい。