kmjp's blog

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

TopCoder SRM 594 Div1 Easy AstronomicalRecords

for文を回す変数名を凡ミスで落としたSRM594、これでレート冷えは痛い…。
http://community.topcoder.com/stat?c=problem_statement&pm=12804

問題

いくつかの星が1列に並んでいる。
この星から並び順を保ったままいくつかを選び、その大きさの比をとったら数列Aが得られた。
また、並び順を保ったまま再度いくつかを選び、その大きさの比をとったら数列Bが得られた。

数列AとBが与えられたとき、元の星の並びであり得る星の数を最小化せよ。

解法

A[i]とB[j]が実は同じ星を示すと仮定する。
Aの各要素をB[j]倍し、Bの各要素をA[i]倍するとAとBのスケールが一致するので、あとはLongest Common Stringをとる要領で同じ大きさの星の数を数えればよい。
LCSが長いほど、AとBで共通の星が多数あるので全体でlen(A)+len(B)-len(LCS)が答えとなる。

A[i]とB[j]の選び方がO(N^2)で,LCS計算がO(N^2)なので全体でO(N^4)で処理可能。

int dpdp[100][100];
class AstronomicalRecords {
	public:
	int X,Y;
	vector<ll> AA,BB;
	
	int lcs() {
		int x,y;
		ZERO(dpdp);
		FOR(x,X) FOR(y,Y) {
			if(AA[x]==BB[y]) dpdp[x+1][y+1]=max(dpdp[x+1][y+1],dpdp[x][y]+1);
			dpdp[x+1][y+1]=max(dpdp[x+1][y+1],dpdp[x][y+1]);
			dpdp[x+1][y+1]=max(dpdp[x+1][y+1],dpdp[x+1][y]);
		}
		int ma=0;
		FOR(x,X+1) FOR(y,Y+1) ma=max(ma,dpdp[x][y]);
		return ma;
	}
	
	int minimalPlanets(vector <int> A, vector <int> B) {
		X=A.size(),Y=B.size();
		int i,j,k;
		int ret=0;
		AA.resize(X);
		BB.resize(Y);
		
		FOR(i,X) FOR(j,Y) {
			ll g=__gcd(A[i],B[j]);
			FOR(k,X) AA[k]=A[k]*(B[j]/g);
			FOR(k,Y) BB[k]=B[k]*(A[i]/g);
			ret=max(ret,lcs());
		}
		return X+Y-ret;
	}
}

まとめ

毎度LCSの計算は境界まわりで戸惑う。これを機にライブラリ化しておこう。