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の計算は境界まわりで戸惑う。これを機にライブラリ化しておこう。