naoya_t@topcoder

SRM397 Div1 Easy: SortingGame

過去問, 練習 | 04:19 |

手間取った。BFSしてみた。ここで馬鹿の一つ覚え的にpriority_queueを使っているが普通のキューないしvector<int>でも深度を１つずつ下げていけば十分。（とTOPの人のコードを見て悟った）

class SortingGame {
  int n;
  int sig(const vector<int> &b){
    int s=0;
    tr(b,it){s=s*n+(*it)-1;}
    return s;
  }
  void reset(vector<int> &b,int sig) {
    for (int i=n-1,s=sig;i>=0;i--,s/=n) b[i]=(s%n)+1;
  }

  public:
  int fewestMoves(vector<int> board, int k) {
    n=sz(board);
    int board_sig=sig(board);
    vector<int> sorted(all(board)); sort(all(sorted));
    int sorted_sig=sig(sorted);
    if(board_sig==sorted_sig) return 0;
    priority_queue<pair<int,int> > pq;
    for(int b=0;b<=n-k;b++) {
      reverse(board.begin()+b,board.begin()+b+k);
      int newsig=sig(board);
      if(newsig==sorted_sig) return 1;
      pq.push(make_pair(-1,newsig));
      reset(board,board_sig);
    }
    map<int,int> visited; visited[board_sig]=0;
    while(!pq.empty()) {
      int depth=pq.top().first, sg=pq.top().second;
      pq.pop();
      if(visited.find(sg)!=visited.end()) continue;
      visited[sg]=depth;
      for(int b=0;b<=n-k;b++) {
        reset(board,sg);
        reverse(board.begin()+b,board.begin()+b+k);
        int newsig=sig(board);
        if(newsig==sorted_sig) return -depth+1;
        pq.push(make_pair(depth-1,newsig));
      }
    }
    return -1;
  }
};