kmjp's blog

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

Kodamanと愉快な仲間たち : U - Monotonic

3ページ目からが本番。
https://www.hackerrank.com/contests/kodamanwithothers/challenges/monotonic

問題

N個の1桁の数値が並んだ列がある。
隣接要素を連結し、両数値表記を連結した値に置き換える、ということを任意回数とこなえるとする。
数列が広義単調増加となるようにするには、最小何回連結すればよいか。

解法

桁数が徐々に増えるようにすれば単調増加を確実に達成できるので、要素数の最小値はO(√N)程度である。
また、個々の要素もO(√N)桁程度まで考えればよい。

以下をDPで埋めていくことを考える。
f(n,k) := 先頭から(n+k)要素を考えたとき、n要素目からk要素を連結したものが末尾になるような列における最小連結回数
この時、次はk要素またはk+1要素を連結することを考えればよい。

k+2要素以上のことを考える必要はないのかと思うかもしれないが、
f(n,k+1) = min(f(n,k+1), f(n,k)+1)
であることを元にf(n,k+1)からの遷移を考えればそこに含まれるのでf(n,k)からの遷移で考えなくてよい。

こうすると状態がO(N√N)通りで遷移がO(1)通りなのでなんとか間に合う。

int N,T;
string S;
int dp[30303][250];
int same[30303][250];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		S.clear();
		S.push_back(0);
		FOR(i,N) {
			cin>>x;
			S.push_back(x);
		}
		N++;
		FOR(i,N) FOR(j,250) dp[i][j]=1<<20;
		for(j=1;j<=min(N,249);j++) {
			same[N-j][j]=0;
			for(i=N-j-1;i>=0;i--) {
				if(S[i]==S[i+j]) same[i][j]=same[i+1][j]+1;
				else same[i][j]=0;
				
			}
		}
		
		int mi=N-1;
		
		dp[0][1]=0;
		FOR(i,N) {
			for(j=1;j<=249&&i+j<=N;j++) {
				if(i+j<N) dp[i][j+1]=min(dp[i][j+1],dp[i][j]+1);
				int cand=dp[i][j]+(N-i-j);
				mi=min(mi,cand);
				if(i+2*j<=N) {
					if(same[i][j]>=j || S[i+same[i][j]]<S[i+j+same[i][j]]) {
						dp[i+j][j]=min(dp[i+j][j],dp[i][j]+j-1);
					}
					else if(i+2*j+1<=N) {
						dp[i+j][j+1]=min(dp[i+j][j+1],dp[i][j]+j);
					}
				}
			}
		}
		
		
		
		cout<<mi<<endl;
		
	}
}

まとめ

昔AtCoderの有志コンで似たようなの見た気が…。