yukicoder : No.3427 Erasing a Subsequence

意外にコードが短い。
https://yukicoder.me/problems/no/3427

問題

２つの数列S,Tが与えられる。
SはTを部分列として含む。また、Tは乱数で生成されている。
SからTを取り除いてできる数列のうち、辞書順最小のものを求めよ。

解法

dp(n,m) := S[0...(n-1)]からT[0...(m-1)]を取り除いてできる数列のうち、辞書順最小のもの
とする。
すると以下のように遷移できる。

• S[n]!=T[m]の場合、dp(n+1,m) = dp(n,m) + S[n]
• S[n]=T[m]の場合、dp(n+1,m+1) = min(dp(n,m), dp(n,m+1))

DPでこのテーブルを埋める際、前者はinplaceに更新すると、１回O(1)で遷移できる。
後者は数列の大小判定をするので、１回O(|S|)かかる。
ただしTが乱数で作られていることから、後者の発生頻度はさほど高くないため、これで問題ない。

int N,M;
int S[1010],T[1010];
vector<int> dp[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,1000+1) dp[i+1]={2020};
	
	cin>>N>>M;
	FOR(i,N) cin>>S[i];
	FOR(i,M) cin>>T[i];
	
	FOR(i,N) {
		x=S[i];
		for(j=M;j>=0;j--) {
			dp[j].push_back(x);
			if(j&&x==T[j-1]) {
				dp[j]=min(dp[j],dp[j-1]);
			}
		}
	}
	FORR(a,dp[M]) cout<<a<<" ";
	cout<<endl;
	
}

まとめ

Tが乱数で作られてるって部分をどう生かすかでちょっと悩む。