ichirin2501's diary

いっちりーん。

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でもいけるはず…。
バグどこー