寝癖頭の解法

学習中の覚え書きを投稿、更新していきます。

AtCoder Problems in C++ #D - ぬいぐるみの整理 (Plush Toys)

第16回日本情報オリンピック 予選(過去問)から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
競技プログラミング」を略して、「競プロ」などと呼ばれています。

#D - ぬいぐるみの整理 (Plush Toys)

atcoder.jp

僕が作成、提出したコードは、以下のとおりです。

/*
AtCoder Problems in C++
#D - ぬいぐるみの整理 (Plush Toys)
https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_d
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
  int n,m;
  cin>>n>>m;
  vector<vector<int>> vec(m,vector<int>(n+1));
  for(int i=0;i<n;i++){
    int x;
    cin>>x;
    vec[x-1][i+1]=1;
  }
  for(int i=0;i<m;i++){
    for(int j=1;j<=n;j++){
      vec[i][j]+=vec[i][j-1];
    }
  }
  vector<int> dp(1<<m,1e9);
  dp[0]=0;
  for(int i=0;i<(1<<m);i++){
    for(int j=0;j<m;j++){
      if(i&(1<<j)){
        continue;
      }
      int sum=0;
      int add=vec[j][n];
      for(int k=0;k<m;k++){
        if(i&(1<<k)){
          sum+=vec[k][n];
        }
      }
      int r=vec[j][sum+add]-vec[j][sum];
      dp[i|(1<<j)]=min(dp[i|(1<<j)],dp[i]+add-r);
    }
  }
  cout<<dp[(1<<m)-1]<<endl;
  return 0;
}