寝癖頭の解法

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

AtCoder Problems in C++ #C - あみだくじ

第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;
}