静かで孤独な日記

のんびりたまに

AOJ 2334 Roads on Towns

#include<bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;

//幾何ライブラリ
//ほぼ、https://ei1333.github.io/algorithm/geometry_new.html からパクりました

using Real=double;//問題によってはlong double に変更してください
const Real EPS=1e-8;//問題によって値を変更してください
const Real PI=acos(-1.0);//3.141592653589793238...
inline bool eq(Real a,Real b){return fabs(b-a)<EPS;}//誤差を考慮した等価判定
static const int COUNTER_CLOCKWISE=1;
static const int CLOCKWISE=-1;
static const int ONLINE_BACK=2;
static const int ONLINE_FRONT=-2;
static const int ON_SEGMENT=0;
typedef complex<Real> Point;//点

//直線
struct Line{
    Point p1,p2;
    Line()= default;
    Line(Point a,Point b):p1(a),p2(b){};
};

//線分
struct Segment:Line{
    Segment()= default;
    Segment(Point a,Point b):Line(a,b){}
};

//点同士の大小比較
namespace std {
    bool operator<(const Point &a, const Point &b) {
        return a.real() != b.real() ? a.real() < b.real() : a.imag() < b.imag();
    }
}

//外積
Real cross(const Point& a,const Point& b){
    return a.real()*b.imag()-a.imag()*b.real();
}

//内積
Real dot(const Point& a,const Point& b){
    return a.real()*b.real()+a.imag()*b.imag();
}


int ccw(Point a,Point b,Point c){
    b=b-a;c=c-a;
    if(cross(b,c)>EPS)return COUNTER_CLOCKWISE;//1
    if(cross(b,c)<-EPS)return CLOCKWISE;//-1
    if(dot(b,c)<0)return ONLINE_BACK;//2
    if(norm(b)<norm(c))return ONLINE_FRONT;//-2
    return ON_SEGMENT;//0
}

bool intersect(const Segment& s,const Segment& t){
    return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2)<=0 && ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2)<=0;
}

//Shortest_Path
//グラフの最短距離を求めるアルゴリズムを3種類持っているクラスです
class shortest_path{
public:
    
    //dijkstra法とBellman_Ford法を使うときは、このコンストラクタを使ってください
    explicit shortest_path(int n):vertex(n),INF((double)1e9){
        v1.resize(static_cast<unsigned long>(vertex));
    }
    
    //Warshall_Floyd法を使うときは、こちらのコンストラクタを使ってください
    shortest_path(int n,double inf):vertex(n),INF(inf){
        v2.resize(static_cast<unsigned long>(vertex));
        for(int i=0;i<vertex;i++)v2[i].resize(static_cast<unsigned long>(vertex));
        for(int i=0;i<vertex;i++){
            for(int j=0;j<vertex;j++){
                v2[i][j]=INF;
            }
        }
        for(int i=0;i<vertex;i++)v2[i][i]=0;
    }
    
    //dijkstra法とBellman_Ford法専用のadd_edge(int from,int to,ll cost)です
    //コストcostの頂点fromから頂点toへの有向辺を追加するときadd_edge(int from,int to,ll cost)
    void add_edge(int from,int to,double cost){
        v1[from].push_back({to,cost});
    }
    
    //Warshall_Floyd法専用のadd_edge(int from,int to,ll cost)です
    //コストcostの頂点fromから頂点toへの有向辺を追加するときadd_edge(int from,int to,ll cost)
    void add_edge_(int from,int to,ll cost){//warshall_floyd
        v2[from][to]=cost;
    }
    
    //Dijkstra法です
    //各頂点への距離が格納されたvector<ll>が求まります
    //負のコストの辺がある場合は使えません
    //start地点の頂点番号を引数に入れてください
    vector<double> dijkstra(unsigned int start){
        vector<double> d(static_cast<unsigned long>(vertex),INF);
        priority_queue<pair<double,int> > q;
        d[start]=0;
        q.push({0,start});
        while(!q.empty()){
            int now=q.top().se;
            double now_cost=-q.top().fi;
            q.pop();
            if(d[now]<now_cost)continue;
            for (auto &i : v1[now]) {
                if(d[i.fi]>now_cost+ i.se){
                    d[i.fi]=now_cost+ i.se;
                    q.push({-d[i.fi], i.fi});
                }
            }
        }
        return d;
    }
    
    //Warshall_Floyd法です
    //各頂点への距離が格納されたvector<ll>と閉路があるかどうかの情報の2つのtupleが返されます
    //閉路があるとき、返り値はtrueです
    tuple<vector<vector<ll> >,bool> warshall_floyd(){
        for(int k=0;k<vertex;k++){
            for(int i=0;i<vertex;i++){
                if(v2[i][k]==INF)continue;
                for(int j=0;j<vertex;j++){
                    if(v2[k][j]==INF)continue;
                    v2[i][j]=min(v2[i][j],v2[i][k]+v2[k][j]);
                }
            }
        }
        bool is_negative_cycle=false;
        for(int i=0;i<vertex;i++){
            if(v2[i][i]<0)is_negative_cycle=true;
        }
        return make_tuple(v2,is_negative_cycle);
    }

    //Bellman_Ford法です
    //各頂点への距離が格納されたvector<ll>と閉路があるかどうかの情報の2つのtupleが返されます
    //閉路があるとき、返り値はtrueです
    //start地点の頂点番号を引数に入れてください
    tuple<vector<ll>,bool> bellman_ford(int start){
        vector<ll> d(static_cast<unsigned long>(vertex),INF);
        d[start]=0;
        bool is_negative_cycle=false;
        for(int i=0;i<vertex;i++){
            bool update= false;
            for(int j=0;j<vertex;j++){
                if(d[j]==INF)continue;
                for(int k=0;k<(int)v1[j].size();k++){
                    if(d[v1[j][k].fi]>d[j]+v1[j][k].se){
                        d[v1[j][k].fi]=d[j]+v1[j][k].se;
                        update= true;
                    }
                }
            }
            if(i==vertex-1 && update)is_negative_cycle=true;
            else if(!update)break;
        }
        return make_tuple(d,is_negative_cycle);
    }
private:
    double INF;
    int vertex;
    vector<vector<pair<int,double> > > v1;
    vector<vector<ll> > v2;
};

int na,nb;
double xa[1001],ya[1001],xb[1001],yb[1001];

int main(){
  int na,nb;
  cin>>na>>nb;
  for(int i=0;i<na;i++){
    cin>>xa[i]>>ya[i];
  }
  for(int i=0;i<nb;i++){
    cin>>xb[i]>>yb[i];
  }
  Point tmp(xb[0],yb[0]);
  Point tmp2(xb[1],yb[1]);
  Segment s1(tmp,tmp2);
  shortest_path sp1(na);
  //cout<<1<<endl;
  for(int i=0;i<na;i++){
    for(int j=i+1;j<na;j++){
      Point a(xa[i],ya[i]);
      Point b(xa[j],ya[j]);
      Segment aa(a,b);
      //cout<<aa.p1<<" "<<aa.p2<<endl;
      if(!intersect(s1,aa)){
        //cout<<i<<"--"<<j<<endl;
        sp1.add_edge(i,j,sqrt((xa[i]-xa[j])*(xa[i]-xa[j])+(ya[i]-ya[j])*(ya[i]-ya[j])));
        sp1.add_edge(j,i,sqrt((xa[i]-xa[j])*(xa[i]-xa[j])+(ya[i]-ya[j])*(ya[i]-ya[j])));
      }
    }
  }
  vector<double> di1=sp1.dijkstra(0);
  double ans;
  if(di1[1]!=1e9){
    ans=di1[1]+getDistance(tmp,tmp2);
  }else{
    ans=inf;
  }
  Point tmp3(xa[0],ya[0]);
  Point tmp4(xa[1],ya[1]);
  Segment s2(tmp3,tmp4);
  shortest_path sp2(nb);
  //cout<<2<<endl;
  for(int i=0;i<nb;i++){
    for(int j=i+1;j<nb;j++){
      Point a(xb[i],yb[i]);
      Point b(xb[j],yb[j]);
      Segment aa(a,b);
      if(!intersect(s2,aa)){
        //cout<<i<<"--"<<j<<endl;
        sp2.add_edge(i,j,sqrt((xb[i]-xb[j])*(xb[i]-xb[j])+(yb[i]-yb[j])*(yb[i]-yb[j])));
        sp2.add_edge(j,i,sqrt((xb[i]-xb[j])*(xb[i]-xb[j])+(yb[i]-yb[j])*(yb[i]-yb[j])));
      }
    }
  }
  vector<double> di2=sp2.dijkstra(0);
  if(di2[1]!=inf){
    ans=min(ans,di2[1]+getDistance(tmp3,tmp4));
  }else{
    ans=min(ans,inf);
  }
  if(ans!=inf){
    printf("%.12f\n",ans);
  }else{
    cout<<-1<<endl;
  }
  return 0;
}
  • 街の数が1000くらいだからO(n^2)解があるだろうなんて考えたら簡単に思いついた。
  • 交差判定して交差してなかったら変を追加。
  • 変を追加したら0から1への最短距離求めるためにdijkstraやるだけ。

AOJ 2511 Sinking islands

#include<bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;

//union_find
//_n mast be unsigned int
//BEGIN CUT HERE
class union_find{
public:
    explicit union_find(int _n):n(_n){
        par.resize(static_cast<unsigned long>(_n));
        rank.resize(static_cast<unsigned long>(_n));
        sizes.resize(static_cast<unsigned long>(_n));
        for(int i=0;i<_n;i++){
            par[i]=i;
            rank[i]=0;
            sizes[i]=1;
        }
    }
    
    //親ノードを見つけます
    int find(int a){
        if(par[a]==a)return a;
        return par[a]=find(par[a]);
    }
    
    //aとbが同じグループかの判定
    bool same(int a,int b){
        return find(a)==find(b);
    }
    
    //aとbを同じグループにします
    void unite(int a,int b){
        link(find(a),find(b));
    }
    
    //aが属するグループの要素数を求めます
    int size(int a){
        return sizes[find(a)];
    }
    
    //全体がどのグループに属しているかがわかります
    void view(){
        for(int i=0;i<n;i++){
            cout<<" par"<<"["<<i<<"]="<<par[i]<<((i==n-1)?"\n":",");
        }
        for(int i=0;i<n;i++){
            cout<<"size"<<"["<<i<<"]="<<sizes[i]<<((i==n-1)?"\n":",");
        }
        cout<<endl;
    }

    void init(){
      for(int i=0;i<n;i++){
        par[i]=i;
        rank[i]=0;
        sizes[i]=1;
      }
    }

private:
    void link(int a,int b){
        if(same(a,b))return;
        if(rank[a]>rank[b]){
            par[b]=a;
            sizes[a]+=sizes[b];
            sizes[b]=0;
        }else{
            par[a]=b;
            if(rank[a]==rank[b])rank[b]++;
            sizes[b]+=sizes[a];
            sizes[a]=0;
        }
    }
    int n;
    vector<int> par;
    vector<int> rank;
    vector<int> sizes;
};

int main(){
  int n,m;
  while(cin>>n>>m,n){
    vector<pair<int,int> > h;
    for(int i=0;i<n;i++){
      int a;cin>>a;
      h.push_back({a,i});
    }
    union_find tmp(n);
    vector<pair<pair<int,int>,int> > v;
    for(int i=0;i<m;i++){
      int a,b,c;cin>>a>>b>>c;
      a--;b--;
      tmp.unite(a,b);
      v.push_back(make_pair(make_pair(c,a),b));
    }
    if(tmp.size(0)!=n){
      cout<<0<<endl;
      continue;
    }
    sort(h.begin(),h.end());
    reverse(h.begin(),h.end());
    sort(v.begin(),v.end());
    union_find uf(n);
    ll ans=0;
    bool ok[201];
    int cont=0;
    for(int i=0;i<n;i++)ok[i]=0;
    for(int i=0;i<n;i++){
      ok[h[i].se]=1;
      if(i==n-1 || h[i].fi!=h[i+1].fi){
        for(int j=0;j<m;j++){
          int nowa=v[j].fi.se;
          int nowb=v[j].se;
          if(ok[nowa] && ok[nowb] && !uf.same(nowa,nowb)){
            ans+=v[j].fi.fi;
            cont++;
            uf.unite(nowa,nowb);
          }
        }
        if(cont!=i){
          uf.init();
          cont=0;
          ans=0;
        }
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}
  • 日本語が難しかった。。
  • こういう問題に当たりたくないなぁ。。

AOJ 2510 Twin book report

#include<bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;
bool dp[1001][1001];

int main(){
  int n;
  while(cin>>n,n){
    vector<pair<int,int> > v;
    int sum=0,maxe=0;
    int sumw=0;
    int maxw=0;
    vector<int> vv;
    for(int i=0;i<n;i++){
      int a,b;cin>>a>>b;
      v.push_back({a,b});
      vv.push_back(b);
      sum+=a;
      if(maxe<a){
        maxe=a;
        maxw=i;
      }
      sumw+=b;
    }
    if(maxe<=sum-maxe){
      cout<<sum+sumw<<endl;
    }else{
      int ans=maxe*2+v[maxw].se;
      int nokori=maxe-(sum-maxe);
      vv.erase(vv.begin()+maxw);
      sort(vv.begin(),vv.end());
      int vvsum=0;
      for(int i=0;i<(int)vv.size();i++)vvsum+=vv[i];
      for(int i=0;i<=(int)vv.size();i++)for(int j=0;j<=nokori;j++)dp[i][j]=0;
      dp[0][0]=1;
      for(int i=0;i<(int)vv.size();i++){
        for(int j=0;j<=nokori;j++){
          if(dp[i][j]==0)continue;
          if(j+vv[i]<=nokori){
            dp[i+1][j+vv[i]]=1;
          }
          dp[i+1][j]=1;
        }
      }
      for(int i=nokori;i>=0;i--){
        if(dp[vv.size()][i]){
          cout<<ans+vvsum-i<<endl;
          break;
        }
      }
    }
  }
  return 0;
}
  • とりあえず本を早く全部読み終わりたい。
  • 本当は待たずに全部の本読みたいけど、一つだけめちゃめちゃ読むのに時間がかかる本があるとそうはいかない。
  • そんな場合は待ち時間に感想文書けば良い。
  • 待ち時間をどんなふうに使うのが一番かはdpしてあげるのが一番簡単。

AOJ 2333 My friends are small

#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
using namespace std;
const ll MOD=(ll)1e9+7;
const int inf=(ll)1e9;
//const ll inf=(ll)1e14;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};

int n,w;
int a[211];
int sum[202];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
  cin>>n>>w;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  a[n]=inf;
  n++;
  sort(a,a+n);
  ll ans=0;
  for(int i=0;i<n+1;i++){
    int sum=0;
    for(int j=0;j<i;j++){
      sum+=a[j];
    }
    int nokori=w-sum;
    if(nokori<0)continue;
    //show(nokori);
    int minw=a[i];
    //show(minw);
    ll dp[2][10001];
    for(int j=0;j<2;j++)for(int k=0;k<=w;k++)dp[j][k]=0;
    dp[(i+1)&1][0]=1;
    for(int j=i+1;j<n;j++){
      for(int k=0;k<=w;k++){
        dp[(j+1)&1][k]=0;
      }
      for(int k=0;k<=w;k++){
        if(dp[j&1][k]==0)continue;
        if(k+a[j]<=nokori){
          dp[(j+1)&1][k+a[j]]=(dp[(j+1)&1][k+a[j]]+dp[j&1][k])%MOD;
        }
        dp[(j+1)&1][k]=(dp[(j+1)&1][k]+dp[j&1][k])%MOD;
      }
      /*for(int k=0;k<=w;k++){
        cout<<dp[j&1][k]<<" ";
      }
      cout<<endl;*/
    }
    for(int j=0;j<=nokori;j++){
      if(nokori-j<minw)ans=(ans+dp[n&1][j])%MOD;
    }
  }
  cout<<ans<<endl;
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}
  • 数え上げはもれなくダブりなくを意識したい。
  • 今回はソートして初めて鞄に入れられなかった小人で場合分けをする。これはもれなくダブりのない場合わけである。
  • ソートをする理由は、ソートをせずにナップザックのようなことをすると、もう鞄の中にどんな小人も入る事ができないかどうかの判定ができないからである。

AOJ 1196 Bridge Removal

#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
using namespace std;
const int inf=(int)1e9;

vector<vector<pair<int,int> > > v;
bool past[801];
bool leaf[801];

void dfs(int now){
  bool flag=1;
  for(int i=0;i<(int)v[now].size();i++){
    if(past[v[now][i].fi])continue;
    flag=0;
    past[v[now][i].fi]=1;
    dfs(v[now][i].fi);
  }
  if(flag)leaf[now]=1;
}

int bfs(int s){
  int d[801];
  for(int i=0;i<801;i++){
    d[i]=0;
  }
  queue<pair<int,int> > q;
  q.push({s,0});
  bool p[801];
  for(int i=0;i<801;i++)p[i]=0;
  p[s]=1;
  while(!q.empty()){
    int now=q.front().fi;
    int nowcost=q.front().se;
    q.pop();
    for(int i=0;i<(int)v[now].size();i++){
      if(leaf[v[now][i].fi])continue;
      if(p[v[now][i].fi])continue;
      p[v[now][i].fi]=1;
      d[v[now][i].fi]=v[now][i].se+nowcost;
      q.push({v[now][i].fi,v[now][i].se+nowcost});
    }
  }
  int res=0;
  for(int i=0;i<801;i++){
    res=max(res,d[i]);
  }
  return res;
}

int main(){
  int n;
  while(cin>>n,n){
    v.resize(n);
    for(int i=0;i<n;i++)v.resize(0);
    for(int i=0;i<n;i++){
      past[i]=0;
      leaf[i]=0;
    }
    int tmp[801];
    for(int i=0;i<n-1;i++){
      cin>>tmp[i];tmp[i]--;
    }
    ll ans=0;
    for(int i=0;i<n-1;i++){
      int cost;cin>>cost;
      ans+=cost*3;
      v[i+1].push_back({tmp[i],cost});
      v[tmp[i]].push_back({i+1,cost});
    }
    past[0]=1;
    dfs(0);
    for(int i=0;i<n;i++){
      past[i]=0;
    }
    for(int i=0;i<n;i++){
      if(leaf[i]){
        past[i]=1;
        dfs(i);
        break;
      }
    }
    for(int i=0;i<n;i++){
      if(leaf[i])ans-=2*v[i][0].se;
    }
    ll ans2=ans;
    //show(ans);
    for(int i=0;i<n;i++){
      if(leaf[i])continue;
      int maxedge=bfs(i);
      ans2=min(ans2,ans-maxedge);
      //show(maxedge);
    }
    cout<<ans2<<endl;
  }
  return 0;
}
  • あまりいい方法が考えられず、解けなかった
  • どんな場所は何回通るのかをしっかり意識して考えたい。

AOJ 2200 Mr.Rito Post Office

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll inf=(ll)1e14;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
  int n,m;
  while(cin>>n>>m,n){
    ll land[201][201],sea[201][201];
    int a[1001];
    for(int i=0;i<201;i++){
      for(int j=0;j<201;j++){
        land[i][j]=inf;
        sea[i][j]=inf;
      }
    }
    for(int i=0;i<201;i++){
      land[i][i]=0;
      sea[i][i]=0;
    }
    for(int i=0;i<m;i++){
      int x,y;ll t;
      char sl;
      cin>>x>>y>>t>>sl;
      x--;y--;
      if(sl=='S'){
        sea[x][y]=t;
        sea[y][x]=t;
      }else{
        land[x][y]=t;
        land[y][x]=t;
      }
    }
    int r;cin>>r;
    for(int i=0;i<r;i++){
      cin>>a[i];a[i]--;
    }
    for(int k=0;k<n;k++){
      for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
          sea[i][j]=min(sea[i][j],sea[i][k]+sea[k][j]);
          land[i][j]=min(land[i][j],land[i][k]+land[k][j]);
        }
      }
    }
    ll dp[1001][201];
    for(int i=0;i<r;i++)for(int j=0;j<n;j++)dp[i][j]=inf;
    dp[0][a[0]]=0;
    for(int i=0;i<r-1;i++){
      for(int j=0;j<n;j++){
        if(dp[i][j]==inf)continue;
        for(int k=0;k<n;k++){
          dp[i+1][k]=min(dp[i+1][k],dp[i][j]+land[a[i]][j]+sea[j][k]+land[k][a[i+1]]);
          if(j==k){
            dp[i+1][k]=min(dp[i+1][k],dp[i][j]+land[a[i]][a[i+1]]);
          }
        }
      }
    }
    /*for(int i=0;i<r;i++){
      for(int j=0;j<n;j++){
        cout<<dp[i][j]<<" ";
      }
      cout<<endl;
    }
    cout<<endl;*/
    ll ans=inf;
    for(int i=0;i<n;i++){
      ans=min(ans,dp[r-1][i]);
    }
    cout<<ans<<endl;
  }
  return 0;
}
  • 解いたの2回目なのにある所でずっと躓いていた。
  • 反省点 必ずしもdp[i][k]+dp[k][j]= dp[i][j]ではないということ。
  • これを意識すればチョロかった。

AOJ 1619 Making Lunch Boxes

#include<bits/stdc++.h>
using namespace std;

int dp[2][(1<<24)];
string s[501];
int n,m;
bool a[501][501];

int main(){
  while(cin>>n>>m,n){
    for(int i=0;i<n;i++){
      cin>>s[i];
      for(int j=0;j<m;j++){
        a[i][j]=(s[i][j]=='1');
      }
    }
    if(n<=m){
      int ans=0;
      for(int i=0;i<(1<<n);i++){
        if(ans>=__builtin_popcount(i))continue;
        bool ok=1;
        for(int j=0;j<m;j++){
          int cont=0;
          for(int k=0;k<n;k++){
            if(a[k][j] && i&(1<<k))cont++;
          }
          if(cont&1){ok=0;break;}
        }
        if(ok)ans=max(ans,__builtin_popcount(i));
      }
      cout<<ans<<endl;
    }else{
      int list[501];
      fill(list,list+n,0);
      for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
          if(a[i][j]){
            list[i]=list[i]|(1<<j);
          }
        }
      }
      for(int i=0;i<2;i++)for(int j=0;j<(1<<m);j++)dp[i][j]=-1;
      dp[0][0]=0;
      for(int i=0;i<n;i++){
        for(int j=0;j<(1<<m);j++)dp[(i+1)&1][j]=-1;
        for(int j=0;j<(1<<m);j++){
          if(dp[i&1][j]==-1)continue;
          dp[(i+1)&1][j^list[i]]=max(dp[(i+1)&1][j^list[i]],dp[i&1][j]+1);
          dp[(i+1)&1][j]=max(dp[(i+1)&1][j],dp[i&1][j]);
        }
      }
      cout<<dp[n&1][0]<<endl;
    }
  }
}
  • 基本的には審判長講評に書いてあることをそのまま実装.
  • n<=mなら「どのメニューを作るか」の組合せで全探索.
  • n>mならbitDP.
  • 漸化式はdp[(今、選ぶかどうか考えているメニューの番号:i)%2][1つ余っている素材の集合を表すbit列:j]:=この状況になるようなメニューの組合せのうち最大のメニュー数
  • よって、dp[(i+1)%2][j^list[i]]=max(dp[(i+1)%2][j^list[i]],dp[i%2][j])
  • もうひとつは、dp[(i+1)%2][j]=max(dp[(i+1)%2][j],dp[i%2][j])
  • ここで、list[i]はi番目のメニューで使われる素材の集合を表すbit列です.
  • 最後はひとつも素材を余らせてはいけないのでdp[n%2][0]を出力します.
  • のりで配列の再利用をしたけど、しなくてもいけるのかな?
  • あ、あと__builtin_popcount(i)はiを二進数で表した時に1になっている桁の個数です.
  • 例)__builtin_popcount(7)=3,__builtin_popcount(8)=1,__builtin_popcount(9)=2
  • 初期化をミスして2時間無駄にしたのはココだけの話.