kmjp's blog

競技プログラミング参加記です

yukicoder : No.770 Median Sequence

こっちこそ★4~4.5でよくない…?
https://yukicoder.me/problems/no/770

問題

整数Nが与えられる。
1~Nの値を取るN要素の数列Bnを考える。
 A_1=med(1,B_1,N)
...
 A_i=med(med(med(\dots med(\dots med(med(1,B_1,N-i+1),B_2,N-i+2),\dots ,B_j,N-i+j)\dots ),B_{i-1},N-1),B_i,N)
と表現される数列Anは何通りか。

解法

実験してみると、以下のことがわかる。
 \displaystyle  A_j \ge \max_i^j(min(B_i,N-(j-i))
よって、B_iはできるだけ小さく抑えておいた方が、以後のA_jを小さくできる。
ただB_jを大きくしないとA_jも大きくならない。

よって、

  •  \displaystyle  A_j \g \max_i^{j-1}(min(B_i,N-(j-i))なら A_j = B_j
  •  \displaystyle  A_j \ge \max_i^{j-1}(min(B_i,N-(j-i))なら B_j = 1

とするのがよい。

さて、A_1から順にA_jを求めていくことを考える。
DPをすることを考えると \displaystyle \max_i^{j-1}(min(B_i,N-(j-i))を管理できるようにしなければならない。
それには、2値 \displaystyle \max_i^{j-1}(min(B_i,N-(j-i))の現在値と、あとjがいくつ大きくなったらこの値がデクリメントするかを考えていけばよい。
そうするとO(N^3)のDPを行うことができる。

あとは累積和を用いてO(N^2)に落とすことができる。
この際、配列全体を1つずらす必要があるので、indexを1個ずらすことで配列全体のコピーを防ごう。
(EditorialではQueueを使うと書いている)

int N;
ll mo=1000000007;
ll dp[6030][3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll re[3030]={};
	for(i=1;i<=N;i++) {
		dp[N-i][i]=1;
		re[i]=1;
	}
	int shift=0;
	FOR(i,N-1) {
		ll sum=0;
		for(x=1;x<N;x++) {
			sum+=re[x];
			(dp[shift+1+N-(x+1)][(x+1)]+=sum)%=mo;
		}
		for(x=N;x>1;x--) {
			(re[x]+=sum)%=mo;
			(sum+=mo-re[x-1])%=mo;
		}
		
		// shift
		for(x=1;x<=N;x++) {
			(dp[shift+1][x]+=dp[shift][x])%=mo;
			(re[x]+=dp[shift][x])%=mo;
		}
		for(r=2;r<=N;r++) {
			(dp[shift+1][r-1]+=dp[shift][r])%=mo;
			(re[r-1]+=dp[shift][r])%=mo;
		}
		for(x=1;x<=N;x++) (re[x]+=mo-dp[shift][x])%=mo;
		
		shift++;
	}
	
	ll ret=0;
	FOR(x,N+1) FOR(y,N+1) ret+=dp[shift+x][y];
	cout<<ret%mo<<endl;
	
	
}

まとめ

実験で解いたけど、いいアプローチはなんなんだろうな。