TopCoder SRM 694 Div2 Hard UpDownNess

門松…？
https://community.topcoder.com/stat?c=problem_statement&pm=14304

問題

1～Nのpermutationを成す数列Pのうち、i＜j＜kかつP[i]＜P[j]＞P[k]となる(i,j,k)の組み合わせがK個となるものを求めよ。

解法

挿入DPで解く。
大きい順に値をPに埋めていくことを考えよう。

a個空きがある数列にaを埋める場合、左からb個目に数字を埋めると、その左には(b-1)個、右には(a-b)個aより小さい数字が入るので、あとの数字の埋め方はどうであってもP[i]＜P[a]＞P[j]となる(i,a,j)の組は(b-1)*(a-b)個増える。
あとは残り(a-1)個空きがある数列に(a-1)を埋めることを考えればよい。

この考察から、以下の状態をDPで更新していけば良いことがわかる。
dp[i][j] := 大きい順にi個目までの数字を埋めたところ、問題文の条件を満たす数字の並びがj回登場した。
あとはdp[N][K]を答えればよい。

jはO(N^3)程度まで大きくなるが、jがKより大きいケースは考える必要がない。

ll mo=1000000007;
ll dp[51][5050];

class UpDownNess {
	public:
	int count(int N, int K) {
		ZERO(dp);
		dp[0][0]=1;
		for(int i=1;i<=N;i++) for(int x=0;x<=K;x++) if(dp[i-1][x]) {
			int left=N+1-i;
			for(int j=0;j<left;j++) {
				int y=x+j*(left-j-1);
				if(y<=K) (dp[i][y] += dp[i-1][x])%=mo;
			}
			
		}
		return dp[N][K];
	}
}

まとめ

今回は少し易しめだったね。