yukicoder : No.3119 A Little Cheat

意外に難しい。
https://yukicoder.me/problems/no/3119

問題

N要素の整数列Aと、整数値Mが与えられる。
Bを、N要素で各値が1～Mの整数値を取る数列とすると、BはM^N通りある。

f(B)を、最大1回まで隣接要素をswapした時A[i]＜B[i]となるiの個数の最大値とする。
B全通りにおけるf(B)の総和を求めよ。

解法

swapをしない場合に比べ、swapをするとf(B)は最大1個だけ増えることが考えられる。
よって先頭からBを決めて行ったとき、swapでf(B)が増えそうなタイミングのうち最初に増やすとする。

B[i]まで値を決めたとき、

• まだswapをしてないとき、B[i]の値が

- [0,min(A[i],A[i+1]))
- [min(A[i],A[i+1]),max(A[i],A[i+1]))
- [max(A[i],A[i+1]),M]

• もうswapした

の4つのいずれであるかを状態として持ち、B[i+1]を決めて行くようDPをしていくとよい。

int N,M;
int A[202020];
ll pm[202020];

const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}


ll dp[202020][4];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	pm[0]=1;
	FOR(i,N) {
		cin>>A[i];
		pm[i+1]=pm[i]*M%mo;
	}
	dp[0][0]=min(A[0],A[1]);
	dp[0][1]=max(A[0],A[1])-min(A[0],A[1]);
	dp[0][2]=M-max(A[0],A[1]);
	
	ll ret=(M-A[0])*pm[N-1]%mo;
	for(i=1;i<N;i++) {
		ll X[4]={0,min(A[i],A[i-1]),max(A[i],A[i-1]),M};
		ll Y[4]={0,min(A[i],A[i+1]),max(A[i],A[i+1]),M};
		
		FOR(x,3) FOR(y,3) {
			if(A[i-1]<A[i]) {
				//swapすると1回回数が増える
				if(y==1&&x!=y) {
					ll num=X[y+1]-X[y];
					(dp[i][3]+=dp[i-1][x]*num)%=mo;
					(ret+=dp[i-1][x]*num%mo*pm[N-1-i])%=mo;
				}
				else {
					FOR(k,3) {
						ll num=max(0LL,min(X[y+1],Y[k+1])-max(X[y],Y[k]));
						(dp[i][k]+=dp[i-1][x]*num)%=mo;
						if(y==2) (ret+=dp[i-1][x]*num%mo*pm[N-1-i])%=mo;
					}
				}
			}
			else {
				//swapすると1・2回回数が増える
				if(x==1&&y!=x) {
					ll num=X[y+1]-X[y];
					(dp[i][3]+=dp[i-1][x]*num)%=mo;
					(ret+=dp[i-1][x]*num%mo*pm[N-1-i]*((y+2)/2))%=mo;
				}
				else {
					FOR(k,3) {
						ll num=max(0LL,min(X[y+1],Y[k+1])-max(X[y],Y[k]));
						(dp[i][k]+=dp[i-1][x]*num)%=mo;
						if(y!=0) (ret+=dp[i-1][x]*num%mo*pm[N-1-i])%=mo;
					}
				}
			}
		}
		
		
		//もうswap使用済みの場合
		(ret+=dp[i-1][3]*(M-A[i])%mo*pm[N-1-i])%=mo;
		(dp[i][3]+=dp[i-1][3]*M)%=mo;
	}
	cout<<ret<<endl;
	
	
}

まとめ

★3.5でもいい気はする。