AtCoder ABC #313 (第四回日本最強プログラマー学生選手権-予選-) : Ex - Group Photo

コードは短い。
https://atcoder.jp/contests/abc313/tasks/abc313_h

問題

2N+1人を並べて写真を撮る。
前列N人の身長A[i]と、後列N+1人の身長B[i]が与えられる。

前列及び後列はシャッフルできるとする。
後列の人が多少なりをも顔を出せる、すなわちB[i]＞min(A[i],A[i+1])となるようにしたい。
そのような後列の並び方が1つ以上あるような、前列の並び方はN!通り中いくつあるか。

解法

前列を小さい順に挿入することを考える。
その場合、挿入した前列の人の左右には、後列にそれ以上の身長の人を配置できる。

前列が隣接関係に関し何個連結成分があるかを考える。
すなわち
f(n,k) := 前列をn人まで定めたとき、k個の連結成分で構成された場合、各人の左右の後列(n+k)人分に配置可能な人がいるような組み合わせの数
を考える。前列n+1人目の配置として、以下を総当たりしよう。

• 新規連結成分を(k+1)箇所のどこかに追加する
• 既存連結成分の両端のいずれか2k箇所のどこかに追加する
• 2つの隣接する既存連結成分の間にちょうど挟まるよう、(k-1)箇所のどこかに追加する

int N;
int A[5050],B[5050];
ll from[5555],to[5555];
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N+1) cin>>B[i];
	sort(A,A+N);
	sort(B,B+N+1);
	
	from[0]=1;
	FOR(i,N) {
		ZERO(to);
		FOR(j,i+1) if(from[j]) {
			//新規連結成分を作る。
			if(B[i+j]>=A[i]) (to[j+1]+=from[j]*(j+1))%=mo;
			//既存連結成分に追加
			if(B[i+j]>=A[i]) (to[j]+=from[j]*(2*j))%=mo;
			//既存連結成分の間
			if(j) (to[j-1]+=from[j]*(j-1))%=mo;
		}
		
		swap(from,to);
	}
	
	cout<<from[1]<<endl;
	
}

まとめ

後者の(N+1)!人の並びも考えるものと勘違い…。