yukicoder : No.563 超高速一人かるた large

★４はあっていいと思うけど、4.5かどうかは悩ましいな。
https://yukicoder.me/problems/no/563

問題

smallと同じだが札数Nの上限が2000となっており、BitDPは行えない。
yukicoder : No.562 超高速一人かるた small - kmjp's blog

解法

カードを取るときの疲労度について、以下の考察が必要となる。

取るかるたの部分集合が定まっていると、総疲労度は取る順に依存しない。
文字列の集合Sが昇順にソートされていたとする。S[b]を取るときの疲労度は、前後S[(a+1)..(b-1)],S[(b+1)...(c-1)]がすでに取られているとすると、max(f(a,b),f(b,c))となる。
- 要は残されたかるたのうち、前後のかるただけ見れば疲労度が求められることがわかる。

さらに、上の二つを組み合わせて考える。
取るかるたの部分集合を定め、かつ前から順に取っていくとすると、S[b]を取るときの疲労度は(後ろはまだ取ってないので)max(f(a,b),f(b,b+1))と前に取ったかるただけに依存する。

この事実をもとに数え上げよう。
S[a]が取られず、S[a+1]～S[b-1]を取ってS[b]を取ることを考える。
疲労度は上に書いた通りmax(f(a,b),f(b,b+1))である。

N枚からK枚取るとき、上記のとおり取らない1枚(S[a])と取る(b-a)枚(S[a+1]～S[b])が確定しているので、あとは残り(N-(b-a+1))枚から(K-(b-a))枚を選べばよいことがわかる。
この考察をもとに、a,bに対しK枚取る場合のS[b]の疲労度の影響を数え上げよう。
このままだとO(N^3)かかるので、(b-a)が等しくなるものについてはまとめて計算するとO(N^2)に落とし込める。

最初にとる1枚については、手前に取らない1枚(S[a])が存在しないので注意。

int N;
string S[2002];
ll mo=1000000007;
int cost[2020][2020];
ll ret[2020];
ll dp[2020];

const int CN=4001;
ll C[CN][CN];
ll fact[CN];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	fact[0]=1;
	FOR(i,2020) fact[i+1]=fact[i]*(i+1)%mo;
	FOR(i,CN) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j])%mo;
	
	cin>>N;
	FOR(i,N) cin>>S[i];
	
	sort(S,S+N);
	FOR(y,N) {
		cost[y][y]=cost[y][N]=cost[N][y]=1;
		FOR(x,y) {
			cost[x][y]=1;
			while(cost[x][y]<=S[x].size() && cost[x][y]<=S[y].size() && S[x][cost[x][y]-1]==S[y][cost[x][y]-1]) cost[x][y]++;
			cost[y][x]=cost[x][y];
		}
	}
	
	FOR(y,N) for(x=y+1;x<=N;x++) (ret[x]+=cost[y][y+1]*C[N-(y+1)][x-(y+1)]%mo*fact[x])%=mo;
	
	FOR(x,N) for(y=x+1;y<N;y++) dp[y-x]+=max(cost[x][y],cost[y][y+1]);
	for(i=1;i<=N-1;i++) for(x=i;x<=N;x++) (ret[x]+=dp[i]*C[N-(i+1)][x-i]%mo*fact[x])%=mo;
	
	for(i=1;i<=N;i++) cout<<ret[i]%mo<<endl;
	
}

まとめ

面白かったです。