SRM 219 DIV1 Hard OrderFood
問題
今ここに、Nつのそれぞれentrees[i]円の料理がある。
また、M人の人がいてそれぞれの人に対して、好きな料理(0<=x
- 1 <= N <= 30
- 1 <= M <= 15
解答
分割統治法。
半分にわけて、まず片方を全列挙する。そして人々の状態にたいしての最小コストをメモっとく。
次にもう半分を全列挙する。そのとき、3進数で補数となるようなメモを見て足してやる
コメント
一回定数倍高速化でO(N*3^M)のDPを通してみた。まあResubmitしまくりだけど。
定数倍高速化して通すのは楽しい。しかし全然最適化に関して知識が無いのでそれは悪い。
もっと最適化の知識学ばなきゃなー。
定数倍の嘘でそれなりの問題を素早く通せるようになれたらいいな。
分割統治法は、N<=30から半分の指数かな、とは思ったけどわかってないのでできなかった。しっかりそのバージョンのコードも書いて理解しよう。
…分割統治法解法考えてみたら簡単に思いついて簡単だった。まあ。考え方として、そういう感じを分割統治法と言うんだなと
コード
簡単！分割統治法バージョン
#include <string> #include <vector> #include <sstream> #include <cstring> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f using namespace std; int f[16]; struct OrderFood { int selectEntrees(vector <int> entrees, vector <string> favorites) { int n = entrees.size(), m = favorites.size(); rep(i, m) { stringstream ss(favorites[i]); int x, mask = 0; while(ss >> x) mask |= 1 << x; f[i] = mask; } int n2 = n / 2; static int a[14348907]; mset(a, INF); rep(i, 1<<n2) { int w = 0; rep(j, n2) if((i >> j) & 1) w += entrees[j]; int x = 0; rep(j, m) { int t = __builtin_popcount(f[j] & i); if(t > 2) goto bad; x = x * 3 + t; } a[x] = min(a[x], w); bad:; } int r = INF; rep(i, 1<<(n-n2)) { int w = 0; rep(j, n-n2) if((i >> j) & 1) w += entrees[n2+j]; int x = 0; rep(j, m) { int t = __builtin_popcount((f[j] >> n2) & i); if(t > 2) goto bad2; x = x * 3 + (2 - t); } r = min(r, w + a[x]); bad2:; } return r == INF ? -1 : r; } };
時間かかりまくり！無理やり定数倍高速化バージョン
#include <string> #include <vector> #include <sstream> #include <cstring> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f using namespace std; typedef vector<int> vi; int f[16], g2[33], g3[33]; struct OrderFood { vi e; int n, m; int selectEntrees(vector <int> entrees, vector <string> favorites) { e = entrees, n = e.size(), m = favorites.size(); rep(i, m) { stringstream ss(favorites[i]); int x, mask = 0; while(ss >> x) mask |= 1 << x; f[i] = mask; } rep(i, n) { g3[i] = 0, g2[i] = 0; rep(j, m) { g2[i] = g2[i] * 2 + ((f[j] >> i) & 1); g3[i] = g3[i] * 3 + ((f[j] >> i) & 1); } } //3^mはメモリ的にもギリギリ。 //メモリ節約するにも2つだけ使っても駄目で、一つにする必要がある。 //それぞれのループ内でもアクセスにトポロジカル順序があるなら1つにできる static int dp[14348907]; int pow3m = 1; rep(i, m) pow3m *= 3; mset(dp, INF); dp[pow3m-1] = 0; rep(i, n) { int once = 0, twice = 0; int k; int* p = dp; int ei = e[i], g2i = g2[i], g3i = g3[i]; if(pow3m < 9) { *p = min(*p, ei + *(p+g3i)); ++ p; *p = min(*p, ei + *(p+g3i)); ++ p; if((g2i & 1) == 0) *p = min(*p, ei + *(p+g3i)); ++ p; } else for(int j = 0; j < pow3m; j += 9) { //餡ロールおいしいね！ //x = min(x, y)よりif(x > y) x = y;のほうが速いらしい if((g2i & twice) == 0 && *p > ei + *(p+g3i)) *p = ei + *(p+g3i); ++ p; if((g2i & twice) == 0 && *p > ei + *(p+g3i)) *p = ei + *(p+g3i); ++ p; if((g2i & (twice|1)) == 0 && *p > ei + *(p+g3i)) *p = ei + *(p+g3i); ++ p; if((g2i & twice) == 0 && *p > ei + *(p+g3i)) *p = ei + *(p+g3i); ++ p; if((g2i & twice) == 0 && *p > ei + *(p+g3i)) *p = ei + *(p+g3i); ++ p; if((g2i & (twice|1)) == 0 && *p > ei + *(p+g3i)) *p = ei + *(p+g3i); ++ p; twice |= 2; if((g2i & twice) == 0 && *p > ei + *(p+g3i)) *p = ei + *(p+g3i); ++ p; if((g2i & twice) == 0 && *p > ei + *(p+g3i)) *p = ei + *(p+g3i); ++ p; if((g2i & (twice|1)) == 0 && *p > ei + *(p+g3i)) *p = ei + *(p+g3i); ++ p; twice &=~ 2; k = 2; //3進数カウンタ。 //ループ毎にいちいち割り算するのは遅いので。これならビット演算できる。 //このカウンタの計算時間は(Σj=0..∞ {1/3^j} = 3/2)の感じかな。 //でもそれでも遅いのであんロールした。 //最適化わからないので、もっと速くなると思う //00 → 01 → 11 → 00 do { twice ^= once & (1 << k); once ^= ~twice & (1 << k); }while(~((once | twice) >> k++) & 1); } } return dp[0] == INF ? -1 : dp[0]; } };
