Hardより苦戦した。
http://community.topcoder.com/stat?c=problem_statement&pm=14789
問題
N要素の数列Xが与えられる。
数列の各要素を任意の色で塗り分けることを考える。
ただし隣接要素は同じ色で塗れない。
塗り分けた後、登場する各色について、その色で塗られた要素の最大値の総和を最小化せよ。
解法
色の数は少ないのがいいのは自明。
４色以上使う理由はないので、３色以下の場合のみ考えよう。
まず２色(以下)の場合は隣接要素同士を交互に塗るしかないので塗り方は一意に決まる。
あとは３色の場合を考えよう。
３色のうち１色は、最大値が数列全体の最大値になるのは明らかである。
あと２色の最大値を総当たりする方法がまず思いつくが、こうすると大体のアプローチがO(N^3)になって失敗する。
そこで考え方を変えよう。
Xのうち値の大きい順上位a個を1色目で塗り、(a+1)個目を2色目で塗ったとする。
(a+2)番目以降の要素は３色のうちどれで塗ってもよく、「～～の総和」は1色目の最大値、すなわち数列全体の最大値と、(a+1)番目の要素と、あとは3色目で塗った要素の最大値となる。
前２つは確定済みなので、３色目で塗った最大値を小さくすることを考えよう。
すでに色が確定した要素で挟まれた、未確定の要素群について考える。
例えば1色目で塗った要素同士の間に奇数個未確定の要素がある場合、12121...121のように塗れば３色目は不要である。
逆に偶数個ある場合、どこか１個３色目を入れなければならい。
だとすると、間の要素のうち最小値を取るのが良い。
同様に考えると、未確定の連続した要素群毎に３色目を入れる要素の候補がでるので、その最大値が実際３色目の最大値となる。
上記手順では、aを総当たりするのと、３色目の候補探索を合わせてO(N^2)で終えることができる。
class LineColoring { public: int minCost(vector <int> x) { int N=x.size(); // 2 col; int ma[2]={}; int i,j; FOR(i,N) ma[i%2]=max(ma[i%2],x[i]); int ret=ma[0]+ma[1]; // 3col vector<pair<int,int>> V; FOR(i,N) V.push_back({x[i],i}); sort(ALL(V)); reverse(ALL(V)); vector<pair<int,int>> V2; V2.push_back({V[0].second,1}); for(i=1;i<N;i++) { int cur=V[i].second; V2.push_back({cur,2}); sort(ALL(V2)); int tmp=V[0].first+x[cur]; int ma=0; FOR(j,V2.size()-1) { int a=V2[j].first; int b=V2[j+1].first; if(a+1==b && V2[j].second==V2[j+1].second) { ma=1<<30; continue; } if((b-a)%2==abs(V2[j].second-V2[j+1].second)) continue; int t=1<<30,z; for(z=a+1;z<b;z++) t=min(t,x[z]); ma=max(ma,t); } ret=min(ret,tmp+ma); FORR(c,V2) if(c.first==cur) c.second=1; } return ret; } } *まとめ
