TopCoderOpen 2021 Round3 : Easy AnnoyingPasswords

これでレート上がっていいのかという出来ではあった。
https://community.topcoder.com/stat?c=problem_statement&pm=17042&rd=18749

問題

整数U,L,Dが与えられる。
以下を満たす文字列は何通りあるか。

• アルファベット大文字がU個、小文字がL個、数字がD個からなる
• 各文字は異なる
• 隣接する文字は、種類が異なる

解法

f(U,L,D,prev) := (U+L+D)文字の文字列のうち、大文字・小文字・数字がU,L,D個で末尾の種類がprevであるものの組み合わせ
としたとき、末尾にprevとは異なる種類の文字を連結する単純なDPで良い。

ll dp[27][27][27][4];
const ll mo=1000000007;

class AnnoyingPasswords {
	public:
	int count(int U, int L, int D) {
		ZERO(dp);
		dp[0][0][0][3]=1;
		int i,x,y,z;
		FOR(x,27) FOR(y,27) FOR(z,11) {
			FOR(i,4) {
				if(x<26&&i!=0) (dp[x+1][y][z][0]+=dp[x][y][z][i]*(26-x))%=mo;
				if(y<26&&i!=1) (dp[x][y+1][z][1]+=dp[x][y][z][i]*(26-y))%=mo;
				if(z<10&&i!=2) (dp[x][y][z+1][2]+=dp[x][y][z][i]*(10-z))%=mo;
			}
		}
		
		return (dp[U][L][D][0]+dp[U][L][D][1]+dp[U][L][D][2]+dp[U][L][D][3])%mo;
		
	}
}

まとめ

Round3って普段のDiv1と同等かちょっと難しいぐらいと思ってたけど、こんな問題出るんだな。