SRM 474 :: DIV2 :: 1000pt
SRM474 Div2 Hard(1000) SquaresCovering - 赤コーダーになりたい
こちらを参考に、自分なりに解釈して書いてみたけど、だめだった。
#define REP(i,n) for(int i=0; i<(int)(n); i++) struct SquaresCovering { int bcnt(int n){ n = ( n & 0x55555555 ) + ( n >> 1 & 0x55555555 ); n = ( n & 0x33333333 ) + ( n >> 2 & 0x33333333 ); n = ( n & 0x0f0f0f0f ) + ( n >> 4 & 0x0f0f0f0f ); n = ( n & 0x00ff00ff ) + ( n >> 8 & 0x00ff00ff ); n = ( n & 0x0000ffff ) + ( n >>16 & 0x0000ffff ); return n; } int minCost(vector<int> x, vector<int> y, vector<int> cost, vector <int>sides) { pair<int,int> p[x.size()]; int memo[1<<16]; const int inf = 2100000000; REP(i,(1<<x.size()))memo[i]=inf; REP(i,x.size()){ p[i].first = x[i]; p[i].second = y[i]; } sort(p, p+x.size()); memo[0] = 0; for(int bit=0;bit<x.size();bit++) for(int k=0; k<(1<<x.size()); k++)if( bcnt(k)==bit && memo[k]<inf ){ int p1; REP(i,x.size())if( (k&(1<<i))==0 ){ p1 = i; break; } REP(j,sides.size()){ int r1,r2,r3,r4; r1 = r2 = r3 = r4 = k; REP(l,x.size())if( (k&(1<<l))==0 && abs(p[p1].first-p[l].first)<=sides[j] && abs(p[p1].second-p[l].second)<=sides[j] ) { if( p[p1].first<=p[l].first && p[p1].second<=p[l].second ){ r1 |= (1<<l); memo[r1] = min(memo[r1],memo[k]+cost[j]); } if( p[p1].first<=p[l].first && p[p1].second>=p[l].second ){ r2 |= (1<<l); memo[r2] = min(memo[r2],memo[k]+cost[j]); } if( p[p1].first>=p[l].first && p[p1].second>=p[l].second ){ r3 |= (1<<l); memo[r3] = min(memo[r3],memo[k]+cost[j]); } if( p[p1].first>=p[l].first && p[p1].second<=p[l].second ){ r4 |= (1<<l); memo[r4] = min(memo[r4],memo[k]+cost[j]); } } } } return memo[(1<<x.size())-1]; } };
何がだめなんだろう。
2点を選ぶと正方形の置き方が一意に決まるのは解かるんだけど、
それらしい処理部分が理解できないため、1点を決定し、
4種類の置き方に場合わけをしたときに含まれる点の状態に対してDPしたつもりのコードが上記。
サンプルは全部通るけど、例えば、
x[] = {0, 7, 6, 4, 4, 8, 5, 4, 9, 7, 10, 3, 7, 4, 10, 8} y[] = {8, 6, 2, 8, 5, 0, 9, 3, 5, 8, 3, 1, 6, 6, 7, 6} cost[] = {266, 1069, 578, 513, 157, 1027, 412, 717, 1064, 864, 685, 1001, 1130, 593, 1156, 761, 1004, 1027, 580, 408, 496, 323, 529, 936, 531, 1052, 1176, 476, 960, 872, 842, 602, 474, 1119, 401, 222, 282, 638, 1158, 277, 367, 506, 144, 1114, 932, 1110, 312, 856, 786, 1037} sides[] = {2, 10, 5, 5, 1, 10, 4, 7, 10, 8, 6, 10, 11, 5, 11, 7, 10, 10, 5, 4, 4, 3, 5, 9, 5, 10, 11, 4, 9, 8, 8, 6, 4, 11, 4, 2, 2, 6, 11, 2, 3, 5, 1, 11, 9, 11, 3, 8, 7, 10}
みたいなデータのとき、
正しい出力は 1001 らしいのだけど、上記のコードだと 1112 と大きい値が出力されてしまう。
部分的最適解が間違ってるが…どこが間違ってるのかわからないorz
rng_58先生のコードを拝見したところ、
先に、点の状態に対して同時にカバーできる部分的最適解を求めた後、
点の状態を構成する部分的状態を利用してDP(みたいな感じ?…)
mask2 = mask & (mask2-1)
という処理が印象的だったのでめも。
うーん、1点を決める→正方形の4つの頂点に対応させたときのDPでもいけるはず…。
バグどこー