第8回日本情報オリンピック 本選(過去問)から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#C - あみだくじ
https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf#page=7
僕が作成、提出したコードは、以下のとおりです。
/* AtCoder Problems in C++ #C - あみだくじ https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf#page=7 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n,m,h,k; cin>>n>>m>>h>>k; vector<int> x(m),y(m); vector<vector<int>> a(h,vector<int>(n)); vector<vector<int>> b(h,vector<int>(n)); for(int i=0;i<n;i++){ cin>>b[h-1][i]; } vector<vector<bool>> g(h-1,vector<bool>(n-1,false)); for(int i=0;i<m;i++){ cin>>x[i]>>y[i]; g[--y[i]][--x[i]]=true; } for(int i=0;i<n;i++){ a[0][i]=i; } for(int i=0;i<h-1;i++){ a[i+1]=a[i]; for(int j=0;j<n-1;j++){ if(g[i][j]){ swap(a[i+1][j],a[i+1][j+1]); } } } for(int i=h-2;i>=0;i--){ b[i]=b[i+1]; for(int j=0;j<n-1;j++){ if(g[i][j]){ swap(b[i][j],b[i][j+1]); } } } int cnt=0; for(int i=0;i<k;i++){ cnt+=b[0][i]; } int ans=cnt; for(int i=0;i<m;i++){ int num=cnt; if(a[y[i]][x[i]]<k){ num+=(b[y[i]][x[i]+1]-b[y[i]][x[i]]); } if(a[y[i]][x[i]+1]<k){ num+=(b[y[i]][x[i]]-b[y[i]][x[i]+1]); } ans=min(ans,num); } cout<<ans<<endl; return 0; }