ustimawさんのソースコード

//------------------------------------------------------------------------------
/// @file
/// @brief    HPCAnswer.hpp の実装 (解答記述用ファイル)
/// @author   ハル研究所プログラミングコンテスト実行委員会
///
/// @copyright  Copyright (c) 2015 HAL Laboratory, Inc.
/// @attention  このファイルの利用は、同梱のREADMEにある
///             利用条件に従ってください

//------------------------------------------------------------------------------

#ifdef PROFILE
#define NOINLINE __attribute__((noinline))
#else
#define NOINLINE
#endif

#include "HPCAnswer.hpp"
#include "HPCMath.hpp"
#include<vector>
#include<algorithm>

/// プロコン問題環境を表します。
namespace hpc {

  namespace{
    struct MyItem{
      Pos destination;
      int period;
      int weight;
      int index;
    };

    typedef short score_t;
    constexpr int CAPASITY=15;
    constexpr int PERIOD=4;
    constexpr int ITEM_MAX=16;
    constexpr int M=10;
    constexpr int W_MAX=31;
    constexpr int WEIGHT_CAR=3;
    constexpr int dy[]={-1,0,1,0};
    constexpr int dx[]={0,1,0,-1};
    constexpr int d[]={dy[0]*W_MAX+dx[0],dy[1]*W_MAX+dx[1],dy[2]*W_MAX+dx[2],dy[3]*W_MAX+dx[3]};

    short (*init_table())[ITEM_MAX];
    __m128i (*init_subset_masks());
    
    int N;
    int schedule_x;
    std::vector<int> schedule[4];
    int di[PERIOD];
    MyItem items[ITEM_MAX];
    short (*score_dp)[ITEM_MAX]=init_table();
    __m128i *subset_masks=init_subset_masks();
    int expected;
    int stage_no;

    //set_scores()で使用するテーブルの初期化
    short (*init_table())[ITEM_MAX]{
      static short table[1<<ITEM_MAX][ITEM_MAX];
      for(int i=0;i<1<<ITEM_MAX;i++){
	for(int j=0;j<ITEM_MAX;j++){
	  if(!(i>>j&1)){
	    table[i][j]=0x7fff;
	  }
	}
      }
      return table;
    }

    //assign_item()で使用するテーブルの初期化
    __m128i (*init_subset_masks()){
      static __m128i masks[8];
      for(int i=0;i<8;i++){
	short s[8];
	for(int j=0;j<8;j++){
	  s[j]=((j&~i)==0)?0x8000:0x7fff;
	}
	masks[i]=_mm_loadu_si128(reinterpret_cast<const __m128i*>(s));
      }
      return masks;
    }

    //引数で立っているビットの位置をvectorに格納
    std::vector<int> to_idx(int i){
      std::vector<int> item_idx;
      for(int j=0;j<N;j++){
	if(i>>j&1){
	  item_idx.push_back(j);
	}
      }
      return item_idx;
    }

    //与えられた荷物の集合を2人で配送する時の分配の仕方を求める
    int select_from(int b,const score_t *score){
      int best=1e9;
      int x=0;
      for(int i=0;;i=(i+1+~b)&b){
	int c=score[i]+score[b^i];
	if(c<best){
	  best=c;
	  x=i;
	}
	if(i==b)break;
      }
      return x;
    }

    //引数からshortの最小値を求める
    short horizontal_min(__m128i mn){
      mn=_mm_min_epi16(mn,_mm_shuffle_epi32(mn,0xE));
      mn=_mm_min_epi16(mn,_mm_shuffle_epi32(mn,0x1));
      mn=_mm_min_epi16(mn,_mm_shufflelo_epi16(mn,0x1));
      return _mm_cvtsi128_si32(mn)&0xffff;
    }

    //引数のshortの並び順を逆転する
    __m128i reverse(__m128i r){
      r=_mm_shuffle_epi32(r,0x1b);
      r=_mm_shufflelo_epi16(r,0xb1);
      r=_mm_shufflehi_epi16(r,0xb1);
      return r;
    }
    
    //荷物を4人にどう割り当てるかを求める(すべての荷物に時間帯指定がない時用)
    NOINLINE
    int assign_items_(const score_t *scores){
      //O(3^N)
      int dp[1<<N];
      dp[0]=0;
      for(int i=1;i<8&&i<1<<N;i++){
	dp[i]=1e9;
	for(int j=i;j>(i^j);j=(j-1)&i){
	  dp[i]=std::min(dp[i],scores[j]+scores[i^j]);
	}
      }
      for(size_t i=8;i<1u<<N;i+=8,i|=((1<<(N-2))&i)<<1){
	__m128i mns[8];
	for(int j=0;j<8;j++){
	  mns[j]=_mm_set_epi16(0x7fff,0x7fff,0x7fff,0x7fff,0x7fff,0x7fff,0x7fff,0x7fff);
	}
	for(size_t j=i;j>(i^j);j=(j-8)&i){
	  __m128i l=_mm_loadu_si128(reinterpret_cast<const __m128i*>(scores+j));
	  __m128i r=reverse(_mm_loadu_si128(reinterpret_cast<const __m128i*>(scores+(i^j))));
	  for(int k=7;k>=0;k--){
	    mns[k]=_mm_min_epi16(mns[k],_mm_adds_epi16(l,r));
	    r=_mm_bsrli_si128(r,2);
	  }
	}
	for(int j=0;j<8;j++){
	  dp[i+j]=horizontal_min(_mm_max_epi16(mns[j],subset_masks[j]));
	}
      }
      int best=1e9;
      int x=0;
      for(int i=0;i<1<<N;i++,i|=(((1<<N)>>2)&i)<<1){
	int c=dp[i]+dp[((1<<N)-1)^i];
	if(c<best){
	  best=c;
	  x=i;
	}
      }
      di[0]=select_from(x,scores);
      di[1]=x^di[0];
      di[2]=select_from(((1<<N)-1)^x,scores);
      di[3]=((1<<N)-1)^x^di[2];
      return best;
    }

    //荷物を2人に割り当てた時の燃料の消費量を求める
    void set_2_items_delivery(int *result,const score_t *scores,const int specified1,int specified2,int nunspecified){
      //O(3^nunspecified)
      result[0]=scores[specified1]+scores[specified2];
      for(int i=1;i<8&&i<1<<nunspecified;i++){
	int best=1e9;
	for(int j=i;;j=(j-1)&i){
	  best=std::min(best,scores[j+specified1]+scores[i^j^specified2]);
	  if(!j)break;
	}
	result[i]=best;
      }
      for(size_t i=8;i<1u<<nunspecified;i+=8){
	__m128i mns[8];
	for(int j=0;j<8;j++){
	  mns[j]=_mm_set_epi16(0x7fff,0x7fff,0x7fff,0x7fff,0x7fff,0x7fff,0x7fff,0x7fff);
	}
	for(size_t j=i;;j=(j-8)&i){
	  __m128i l=_mm_loadu_si128(reinterpret_cast<const __m128i*>(scores+j+specified1));
	  __m128i r=reverse(_mm_loadu_si128(reinterpret_cast<const __m128i*>(scores+(i^j)+specified2)));
	  for(int k=7;k>=0;k--){
	    mns[k]=_mm_min_epi16(mns[k],_mm_adds_epi16(l,r));
	    r=_mm_bsrli_si128(r,2);
	  }
	  if(!j)break;
	}
	for(int j=0;j<8;j++){
	  result[i+j]=horizontal_min(_mm_max_epi16(mns[j],subset_masks[j]));
	}
      }
    }

    //与えられた荷物の集合を2人で配送する時の分配の仕方を求める
    int select_from(int unspecified,const score_t *score,const int *specified){
      int best=1e9;
      int x=0;
      for(int i=0;;i=(i+1+~unspecified)&unspecified){
	int c=score[i+specified[0]]+score[unspecified-i+specified[1]];
	if(c<best){
	  best=c;
	  x=i;
	}
	if(i==unspecified)break;
      }
      return x;
    }

    //荷物を4人にどう割り当てるかを求める
    NOINLINE
    int assign_items(const int *nth_parts,const score_t *score){
      if(nth_parts[0]==N)return assign_items_(score);
      const int unspecified=(1<<nth_parts[0])-1;
      int m[PERIOD];
      for(int i=0;i<PERIOD-1;i++){
	m[i]=(1<<nth_parts[i+1])-(1<<nth_parts[i]);
      }
      m[PERIOD-1]=(1<<N)-(1<<nth_parts[PERIOD-1]);
      //O(3^N)
      int dpab[1<<N],dpcd[1<<N];
      set_2_items_delivery(dpab,score,m[0],m[1],nth_parts[0]);
      set_2_items_delivery(dpcd,score,m[2],m[3],nth_parts[0]);
      int best=1e9;
      int x=0;
      for(int i=0;;i=(i+1+~unspecified)&unspecified){
	int c=dpab[i]+dpcd[unspecified-i];
	if(c<best){
	  best=c;
	  x=i;
	}
	if(i==unspecified)break;
      }
      di[0]=select_from(x,score,m)+m[0];
      di[1]=(x&~di[0])|m[1];
      di[2]=select_from(unspecified-x,score,m+2)+m[2];
      di[3]=((unspecified-x)&~di[2])|m[3];
      return best;
    }

    //引数のshortの16要素同士を足し合わせ、その中での最小を求める
    short add_min(const short *dp_prev,const short *costs){
      __m128i mn=_mm_adds_epi16(_mm_loadu_si128(reinterpret_cast<const __m128i*>(dp_prev)),_mm_loadu_si128(reinterpret_cast<const __m128i*>(costs)));
      mn=_mm_min_epi16(mn,_mm_adds_epi16(_mm_loadu_si128(reinterpret_cast<const __m128i*>(dp_prev+8)),_mm_loadu_si128(reinterpret_cast<const __m128i*>(costs+8))));
      return horizontal_min(mn);
    }
    
    //set_scoresの実装部分
    void set_scores_loop(unsigned i,short (*dp)[ITEM_MAX],const int *weights,const short (*costs)[ITEM_MAX][ITEM_MAX]){
      if(!(i&(i-1)))return;
      if(weights[i]<=CAPASITY){
	for(unsigned rem=i;rem;rem&=rem-1){
	  int j=__builtin_ctz(rem);
	  unsigned prev=i&(rem-1);
	  dp[i][j]=add_min(dp[prev],costs[weights[prev]][j]);
	}
      }
    }

    //1人で荷物を配達する際の燃料の消費量を求める
    NOINLINE
    void set_scores(score_t *scores,const int *nth_parts,const int *weights,const int (*dists)[ITEM_MAX+1]){
      short costs[CAPASITY+1][ITEM_MAX][ITEM_MAX];
      short costs_to_office[CAPASITY+1][ITEM_MAX];
      for(int i=0;i<=CAPASITY;i++){
	for(int j=0;j<ITEM_MAX;j++){
	  for(int k=0;k<ITEM_MAX;k++){
	    costs[i][j][k]=(j<=N&&k<=N)?(i+3)*dists[j][k]:0x7fff;
	  }
	  costs_to_office[i][j]=(i+3)*dists[N][j];
	}
      }
      auto dp=score_dp;
      for(int i=0;i<N;i++){
	dp[1<<i][i]=dists[i][N]*WEIGHT_CAR;
      }
      for(int i=3;i<1<<nth_parts[0];i++){
	set_scores_loop(i,dp,weights,costs);
      }
      for(int i=0;i<PERIOD;i++){
	for(int j=1<<nth_parts[i];j<1<<nth_parts[i+1];j+=1<<nth_parts[i]){
	  for(int k=0;k<1<<nth_parts[0];k++){
	    set_scores_loop(j+k,dp,weights,costs);
	  }
	}
      }
      bool done_unspecified=false;
      for(int i=0;i<PERIOD;i++){
	if(nth_parts[i+1]==nth_parts[i]&&done_unspecified++)continue;
	for(int j=0;j<1<<nth_parts[0];j++){
	  int idx=(1<<nth_parts[i+1])-(1<<nth_parts[i])+j;
	  scores[idx]=(weights[idx]>CAPASITY)?0x7fff:add_min(dp[idx],costs_to_office[weights[idx]]);
	}
      }
      scores[0]=0;
    }

    //それぞれの配達先、集配所について各地点からのルートを求める
    NOINLINE
    void set_to_nth_item(int (*to_nth_item)[W_MAX*W_MAX],const Field &field,const int height,const int width,const Pos officePos){
      bool is_not_wall[W_MAX*W_MAX];
      for(int i=0;i<height;i++){
	for(int j=0;j<width;j++){
	  is_not_wall[i*W_MAX+j]=!field.isWall(j,i);
	}
      }
      for(int i=0;i<N+1;i++){
	for(int j=0;j<W_MAX*W_MAX;j++){
	  to_nth_item[i][j]=-1;
	}
	const Pos pos=(i<N)?items[i].destination:officePos;
	int que[W_MAX*W_MAX];
	auto head=que,tail=que;
	*tail++=pos.y*W_MAX+pos.x;
	while(head!=tail){
	  size_t c=*head++;
	  for(int j=0;j<4;j++){
	    size_t n=c+d[j];
	    bool b=(to_nth_item[i][n]<0)&is_not_wall[n];
	    to_nth_item[i][n]^=-b&~(j^2);
	    *tail=n;
	    tail+=b;
	  }
	}
      }
    }
  }
  
    //------------------------------------------------------------------------------
    /// 各ステージ開始時に呼び出されます。
    ///
    /// ここで、各ステージに対して初期処理を行うことができます。
    ///
    /// @param[in] aStage 現在のステージ。
    void Answer::Init(const Stage& aStage)
    {
      const auto &pitems=aStage.items();
      N=pitems.count();
      for(int i=0;i<N;i++){
	items[i]={pitems[i].destination(),pitems[i].period(),pitems[i].weight(),i};
      }
      std::sort(std::begin(items),std::begin(items)+N,[](const MyItem &a,const MyItem &b){
	  return a.period<b.period;
	});
      int nth_parts[PERIOD+1];
      for(int i=0,j=0;i<PERIOD;i++){
	while(j<N&&items[j].period<i){
	  j++;
	}
	nth_parts[i]=j;
      }
      nth_parts[PERIOD]=N;
      int to_nth_item[ITEM_MAX+1][W_MAX*W_MAX];
      const auto &field=aStage.field();
      const auto height=field.height();
      const auto width=field.width();
      const Pos officePos=field.officePos();
      set_to_nth_item(to_nth_item,field,height,width,officePos);
      int dist[ITEM_MAX+1][ITEM_MAX+1]={};
      for(int i=0;i<N+1;i++){
	const Pos from=(i<N)?items[i].destination:officePos;
	for(int j=0;j<i;j++){
	  int dst=items[j].destination.y*W_MAX+items[j].destination.x;
	  int cur=from.y*W_MAX+from.x;
	  int cd=0;
	  while(cur!=dst){
	    cd++;
	    int dir=to_nth_item[j][cur];
	    cur+=d[dir];
	  }
	  dist[i][j]=dist[j][i]=cd;
	}
      }
      int weights[1<<ITEM_MAX];
      weights[0]=0;
      for(int i=0;i<N;i++){
	for(int j=0;j<1<<i;j++){
	  weights[(1<<i)+j]=weights[j]+items[i].weight;
	}
      }
      score_t scores[1<<ITEM_MAX];
      set_scores(scores,nth_parts,weights,dist);
      int best=assign_items(nth_parts,scores);
      
      expected=height*width*N*10000./best;
      for(int i=0;i<PERIOD;i++){
	int b=di[i];
	if(b==0)continue;
	std::vector<int> vidx=to_idx(b);
	int n=vidx.size();
	vidx.push_back(N);
	int c_weight[1<<M];
	for(int j=0;j<1<<n;j++){
	  int bs=0;
	  for(int k=0;k<n;k++){
	    bs|=(j>>k&1)<<vidx[k];
	  }
	  c_weight[j]=weights[bs];
	}
	int p[1<<M][M];
	int dp[1<<M][M];
	for(int j=0;j<n;j++){
	  dp[1<<j][j]=(weights[b]+WEIGHT_CAR)*dist[N][vidx[j]];
	  p[1<<j][j]=n;
	}
	for(int j=3;j<1<<n;j++){
	  if(!(j&(j-1)))continue;
	  for(int k=0;k<n;k++){
	    if(!(j>>k&1))continue;
	    dp[j][k]=1e9;
	    int prev=j^1<<k;
	    for(int l=0;l<n;l++){
	      if(prev>>l&1){
		int c=dp[prev][l]+(c_weight[((1<<n)-1)^prev]+WEIGHT_CAR)*dist[vidx[l]][vidx[k]];
		if(c<dp[j][k]){
		  dp[j][k]=c;
		  p[j][k]=l;
		}
	      }
	    }
	  }
	}
	int best_dp=1e9;
	int idx=0;
	for(int j=0;j<n;j++){
	  int c=dp[(1<<n)-1][j]+WEIGHT_CAR*dist[vidx[j]][N];
	  if(c<best_dp){
	    best_dp=c;
	    idx=j;
	  }
	}
	int bits=(1<<n)-1;
	int y=officePos.y;
	int x=officePos.x;
	for(;;){
	  int dst_y=!bits?officePos.y:items[vidx[idx]].destination.y;
	  int dst_x=!bits?officePos.x:items[vidx[idx]].destination.x;
	  while(y!=dst_y||x!=dst_x){
	    int dir=to_nth_item[vidx[idx]][y*W_MAX+x];
	    schedule[i].push_back(dir^2);
	    y+=dy[dir];
	    x+=dx[dir];
	  }
	  if(bits==0)break;
	  int obits=bits;
	  bits^=1<<idx;
	  idx=p[obits][idx];
	}
      }
    }

    //------------------------------------------------------------------------------
    /// 各配達時間帯開始時に呼び出されます。
    ///
    /// ここで、この時間帯に配達する荷物をトラックに積み込みます。
    /// どの荷物をトラックに積み込むかを決めて、引数の aItemGroup に対して
    /// setItem で荷物番号を指定して積み込んでください。
    ///
    /// @param[in] aStage 現在のステージ。
    /// @param[in] aItemGroup 荷物グループ。
    void Answer::InitPeriod(const Stage& aStage, ItemGroup& aItemGroup)
    {
      for(int i=0;i<N;i++){
	if(di[aStage.period()]>>i&1){
	  aItemGroup.addItem(items[i].index);
	}
      }
      schedule_x=schedule[aStage.period()].size();
    }

    //------------------------------------------------------------------------------
    /// 各ターンでの動作を返します。
    ///
    /// @param[in] aStage 現在ステージの情報。
    ///
    /// @return これから行う動作を表す Action クラス。
    Action Answer::GetNextAction(const Stage& aStage)
    {
      static const Action actions[]={Action_MoveDown,Action_MoveRight,Action_MoveUp,Action_MoveLeft};
      return actions[schedule[aStage.period()][--schedule_x]];
    }

    //------------------------------------------------------------------------------
    /// 各配達時間帯終了時に呼び出されます。
    ///
    /// ここで、この時間帯の終了処理を行うことができます。
    ///
    /// @param[in] aStage 現在のステージ。
    /// @param[in] aStageState 結果。Playingならこの時間帯の配達完了で、それ以外なら、何らかのエラーが発生した。
    /// @param[in] aCost この時間帯に消費した燃料。エラーなら0。
    void Answer::FinalizePeriod(const Stage& aStage, StageState aStageState, int aCost)
    {
    }

    //------------------------------------------------------------------------------
    /// 各ステージ終了時に呼び出されます。
    ///
    /// ここで、各ステージに対して終了処理を行うことができます。
    ///
    /// @param[in] aStage 現在のステージ。
    /// @param[in] aStageState 結果。Completeなら配達完了で、それ以外なら、何らかのエラーが発生した。
    /// @param[in] aScore このステージで獲得したスコア。エラーなら0。
    void Answer::Finalize(const Stage& aStage, StageState aStageState, int aScore)
    {
#ifdef DEBUG
      if(aScore!=expected){
	fprintf(stderr,"%d\n",stage_no);
	exit(0);
      }
#endif
	stage_no++;
    }
}

//------------------------------------------------------------------------------
// EOF