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とする。
Eの点から選ぶと
状態は、Nが1つ減る
なので、(N=4 F=2 E=4)において、Eの点を選んだ時の選び方の数は、
Eの点が4つあるので、(N=3 F=2 E=4)の選び方の数に4を掛けたものとなる。
1回以上選ばなくてはいけない点を選んだ時
Fの点から選ぶと
状態は、Nが1つ減るとともに、Fが1つ減り、Eが1つ増える
なので、(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 ); } };