JOI 2017 予選 4 – ぬいぐるみの整理

この問題のポイント

• 種類の並び替えと比較する
• bitDPで計算量をN!から2^Nに削減する

提出したコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
#define rep(i,n) for (int i=0; i< (n); ++i)
typedef pair<int, int> P;

int r[25][252525]; // ある種類のある位置までの数を記録するための配列
int v[25]; // それぞれのぬいぐるみの数を記録するための配列
int dp[2525252]; // dp配列

// 位置r1から位置r2の間の種類uのぬいぐるみの個数を計算
int calc(int r1, int r2, int u) {
  return r[u][r2] - r[u][r1];
}

int main() {
  int n, m;
  cin >> n >> m;
  for (int i=1; i<=n; i++) {
    int x;
    cin >> x;
    x--;
    r[x][i]++;
    v[x]++;
  }
  // rの作成
  for (int i=0; i<m; i++) {
    for (int j=1; j<=199995; j++) {
      r[i][j] += r[i][j-1];
    }
  }
  // dpの初期化
  for (int i=0; i<(1<<m); i++) {
    dp[i] = 999999999;
  }
  dp[0] = 0;

  // bit全探索している間、配置するぬいぐるみの種類を順に追加していくと
  // みなすことでdpを更新していく
  // 左から順番に埋めていく感じになる
  for (int bit=0; bit< (1<<m); bit++) { // ぬいぐるみの並び順全てについて探索
    // 並び終わったものの総数をカウントする
    int done = 0;
    rep(i, m) { 
      if ((1<<i) & bit) {
        done += v[i];
      }
    }
    rep(i, m) { // 新しいぬいぐるみを配置する
      if ((1<<i) & bit) continue;  // 並び終わったものは飛ばす
      int cost = dp[bit]; // コスト（まず、現在までのコストを代入）
      cost += v[i]; // jを追加したときのコストを追加する
      // 今まで取り出したぬいぐるみの種類の総数だけ左から埋まっている
      // (because bit部分のループがそのような順番で更新していくため)
      // それ以降に含まれる新たに追加する数を引く
      cost -= calc(done, done+v[i], i);
      chmin(dp[bit + (1<<i)], cost); // dp更新
    }
  }
  cout << dp[(1<<m) - 1] << endl;
  return 0;
}

atcoder公式から見られる解説を見ながら実装した。
実装を見てもわからないくらい、bitDPで順列を探索する箇所は難しい。
時間をかけてようやく少し理解できてきたが、コメントなどあやしいかもしれないです。。。

感想

これは初見は厳しすぎる印象。
bitDPは基本的に巡回セールスマンなどNP系の問題に使うのかもしれない。
巡回セールスマンも見かけはN!のアルゴリズムなので、実はこれと近いのかもしれないが、今は理解が浅すぎて全然共通項を見いだせていない。（実装もループとメモ化再帰それぞれしかやってないし。。）