kmjp's blog

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

Codeforces #696 Div2 F. 1 2 3 4 ...

Codeforces

本番中のACがかなり少ない問題。
https://codeforces.com/contest/1474/problem/F

問題

整数Xと整数列Dが与えられる。
これらを用いて以下の数列Pを作る。

  • まずP=[X]とする
  • その後、各D[i]に対し、順次以下の処理を行う。
    • D[i]＞0なら、Pの末尾に、(現在の末尾の値+1)である要素を追加する、という処理をD[i]回行う。
    • D[i]＜0なら、Pの末尾に、(現在の末尾の値-1)である要素を追加する、という処理を|D[i]|回行う。

この時、LISの長さと、そのLISを作れるような要素の選び方が何通りかを求めよ。

解法

D中で、符号の同じ連続する値は、その和で置き換えてしまおう。
そうすると、構成されるPは上下にジグザグ動くことになる。

そのジグザグの折れ目の位置の値だけ抜き出した数列Qを以下のように構築する。
Q[0]=X
Q[i+1]=A[i]+D[i]
i＜jにおいてQ[j]-Q[i]の最大値を考えれば、Q中にQ[i]～Q[j]の値はこの順で最低1回ずつ登場するので、1足せばLISの長さとなる。
よって、LIS長はi＜jとしたときのmax(Q[j]-Q[i])となり、容易に計算できる。

あとはLISの組み合わせを考えよう。
Q[x]から初めてQ[x]+1、Q[x]+2…をどこの折れ線から取っていくかを考えると、以下の値が得られる。
f(n,y,x) := x個目のジグザグの折れ目からLISを始めた場合、値nを取るのはy個目の折れ線の途中または端点であるような組み合わせ中

f(n,y,x)→f(n+1,z,x)となる状態遷移の組み合わせは行列で表現でき、行列累乗を使えばf(n,y,x)→f(m,z,x)を一気に計算できる。
あとはi＜jとしたときのmax(Q[j]-Q[i])を達成する(i,j)についてのf(Q[j],j,i)の総和を求めよう。

int N,X;
ll S[55];
const ll mo=998244353;

const int MAT=55;
struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);};};

Mat mulmat(Mat& a,Mat& b,int n=MAT) {
	ll mo2=4*mo*mo;
	int x,y,z; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(x,n) FOR(z,n) FOR(y,n) {
		r.v[x][y] += a.v[x][z]*b.v[z][y];
		if(r.v[x][y]>mo2) r.v[x][y] -= mo2;
	}
	FOR(x,n) FOR(y,n) r.v[x][y]%=mo;
	return r;
}

Mat powmat(ll p,Mat a,int n=MAT) {
	int i,x,y; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(i,n) r.v[i][i]=1;
	while(p) {
		if(p%2) r=mulmat(r,a,n);
		a=mulmat(a,a,n);
		p>>=1;
	}
	return r;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	int pre=0;
	FOR(i,N) {
		cin>>x;
		if(x==0) {
			i--,N--;
			continue;
		}
		if(pre==0) {
			S[i+1]=S[i]+x;
			pre=x;
		}
		else if((x>0)==(pre>0)) {
			S[i]+=x;
			i--,N--;
		}
		else {
			S[i+1]=S[i]+x;
			pre=x;
		}
	}
	S[N+1]=S[N];
	
	
	ll ma=0,mi=0,d=0;
	vector<ll> V;
	FOR(i,N+1) {
		V.push_back(S[i]);
		V.push_back(S[i]-1);
		V.push_back(S[i]+1);
		ma=max(ma,S[i]);
		mi=min(mi,S[i]);
		d=max(d,S[i]-mi);
	}
	
	if(d==0) {
		cout<<1<<" "<<(-S[N]+1)%mo<<endl;
		return;
	}
	
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	
	Mat A;
	FOR(y,N+1) FOR(x,y) if(S[y]-S[x]==d) A.v[x][x]=1;
	FOR(i,V.size()-1) {
		ll a=V[i];
		ll b=V[i+1];
		
		{
			Mat B;
			mi=0;
			FOR(j,N+1) {
				mi=min(mi,S[j]);
				if(mi==S[j]&&b<=mi) B.v[j][j]=1;
				if(S[j]<S[j+1]&&S[j]<=a&&b<S[j+1]) B.v[j][j]=1;
				if((S[j]<=a&&a<=S[j+1])||(S[j]>=a&&S[j+1]<=a)) {
					for(k=j+1;k<N;k++) {
						if((S[k]<=b&&b<S[k+1])||(S[k]>=b&&S[k+1]<b)) {
							B.v[k][j]=1;
						}
					}
					if(b==S[N]) B.v[N][j]=1;
				}
			}
			ma=-1LL<<60;
			for(j=N;j>=0;j--) {
				ma=max(ma,S[j]);
				if(S[j]==ma&&a>=S[j]) B.v[j][j]=1;
			}
			B=powmat(b-a,B,N+1);
			A=mulmat(B,A,N+1);
		}
	}
	ll ret=0;
	FOR(y,N+1) FOR(x,y) if(S[y]-S[x]==d) ret+=A.v[y][x];
	cout<<(d+1)<<" "<<ret%mo<<endl;
	
	
}

まとめ

LISを求めるDPをするとき、縦横入れ替える感じかな。
ARCでも似たようなのあったよね、解けなかったけど…。