第16回日本情報オリンピック 予選(過去問)から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#D - ぬいぐるみの整理 (Plush Toys)
僕が作成、提出したコードは、以下のとおりです。
/* 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; }