Submission #34599582

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) ;
#endif

// clang-format off
#define rep(i, n) for (int i = 0; (i) < (int)(n); (i)++)

template<class T> bool chmax(T &a, const T &b) {if(a<b) {a=b; return true;} return false; }
template<class T> bool chmin(T &a, const T &b) {if(a>b) {a=b; return true;} return false; }

template<class T> istream& operator>>(istream& is, vector<T>& vec){ rep(i, vec.size()) is >> vec[i]; return is;}
template<class T> ostream& operator<<(ostream& os, vector<T>& vec){ rep(i, vec.size()) os << vec[i] << (i+1==(int)vec.size() ? "" : " "); return os;}
// clang-format on

using ll = long long;
using ull = unsigned long long;

int main() {
   int N, M;
   cin >> N >> M;

   vector<vector<int>> doll_flg(M, vector<int>(N));
   vector<int> doll_cnt(M);

   rep(i, N) {
      int doll;
      cin >> doll;
      doll--;

      doll_flg[doll][i] = 1;
      doll_cnt[doll]++;
   }

   vector<vector<int>> doll_cum(M, vector<int>(N + 1));

   rep(m, M) {
      for (int i = 0; i < N; i++) {
         doll_cum[m][i + 1] = doll_cum[m][i] + doll_flg[m][i];
      }
   }

   int StateSize = 1 << M;
   int INF = numeric_limits<int>::max();
   vector<int> dp(StateSize, INF);

   dp[0] = 0;

   auto arranged_doll_cnt = [&](int arrange_bit) {
      int cnt = 0;
      rep(m, M) {
         if (arrange_bit & (1 << m)) {
            cnt += doll_cnt[m];
         }
      }

      return cnt;
   };

   for (int arrange_bit = 1; arrange_bit < StateSize; arrange_bit++) {
      rep(m, M) {
         if (!(arrange_bit & (1 << m))) {
            continue;
         }

         // 種類mを右端として整理した場合の操作回数
         int child_bit = arrange_bit;
         child_bit ^= 1 << m;

         int child_cnt = dp[child_bit];

         int child_arranged_cnt = arranged_doll_cnt(child_bit);
         int cur_arranged_cnt = child_arranged_cnt + doll_cnt[m];

         int change_cnt = doll_cnt[m];
         change_cnt -= doll_cum[m][cur_arranged_cnt] - doll_cum[m][child_arranged_cnt];

         chmin(dp[arrange_bit], child_cnt + change_cnt);
      }
   }

   int ans = dp[StateSize - 1];
   cout << ans << endl;

   return 0;
}

Submission Info

Judge Result