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

第８回日本情報オリンピック 本選（過去問）から、その提出コードの解答例です。
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;
}

AtCoder Problems in C++ #E - ペンキの色

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

#E - ペンキの色

https://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf#page=11

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

/*
AtCoder Problems in C++
#E - ペンキの色
https://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf#page=11
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int main(void){
  ll h,w;
  cin>>h>>w;
  vector<ll> x{0,h},y{0,w};
  ll n;
  cin>>n;
  vector<ll> a(n),b(n),c(n),d(n);
  for(ll i=0;i<n;i++){
    cin>>a[i]>>b[i]>>c[i]>>d[i];
    x.push_back(a[i]);
    y.push_back(b[i]);
    x.push_back(c[i]);
    y.push_back(d[i]);
  }
  sort(x.begin(),x.end());
  sort(y.begin(),y.end());
  x.erase(unique(x.begin(),x.end()),x.end());
  y.erase(unique(y.begin(),y.end()),y.end());
  h=x.size();
  w=y.size();
  map<ll,ll> mpx,mpy;
  for(ll i=0;i<h;i++){
    mpx[x[i]]=i;
  }
  for(ll i=0;i<w;i++){
    mpy[y[i]]=i;
  }
  vector<vector<ll>> r(h,vector<ll>(w));
  for(ll i=0;i<n;i++){
    r[mpx[a[i]]][mpy[b[i]]]++;
    r[mpx[a[i]]][mpy[d[i]]]--;
    r[mpx[c[i]]][mpy[b[i]]]--;
    r[mpx[c[i]]][mpy[d[i]]]++;
  }
  h--;
  w--;
  for(ll i=0;i<h;i++){
    for(ll j=0;j<w;j++){
      r[i+1][j]+=r[i][j];
      r[i][j+1]+=r[i][j];
      r[i+1][j+1]-=r[i][j];
    }
  }
  ll ans=0;
  for(ll i=0;i<h;i++){
    for(ll j=0;j<w;j++){
      if(r[i][j]){
        continue;
      }
      queue<pair<ll,ll>> q;
      q.push({i,j});
      ans++;
      r[i][j]=1;
      while(!(q.empty())){
        auto[x,y]=q.front();
        q.pop();
        for(ll k=0;k<4;k++){
          ll nx=x+dx[k];
          ll ny=y+dy[k];
          if((0<=nx && nx<h) && (0<=ny && ny<w) && !r[nx][ny]){
            r[nx][ny]=1;
            q.push({nx,ny});
          }
        }
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}

AtCoder Problems in C++ #sheet - 色紙 (Sheet)

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

#sheet - 色紙 (Sheet)

https://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf

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

/*
AtCoder Problems in C++
#sheet - 色紙 (Sheet)
https://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
  ll n;
  cin>>n;
  ll h,w;
  cin>>w>>h;
  vector<vector<ll>> c(h,vector<ll>(w));
  for(ll i=0;i<h;i++){
    for(ll j=0;j<w;j++){
      cin>>c[i][j];
      c[i][j]--;
    }
  }
  vector<vector<ll>> g(n);
  for(ll i=0;i<n;i++){
    ll minh=h,minw=w,maxh=0,maxw=0;
    for(ll j=0;j<h;j++){
      for(ll k=0;k<w;k++){
        if(c[j][k]==i){
          minh=min(minh,j);
          minw=min(minw,k);
          maxh=max(maxh,j);
          maxw=max(maxw,k);
        }
      }
    }
    for(ll j=minh;j<=maxh;j++){
      for(ll k=minw;k<=maxw;k++){
        if(c[j][k]==-1 || c[j][k]==i){
          continue;
        }
        ll t=c[j][k];
        g[i].push_back(t);
      }
    }
  }
  vector<ll> ans;
  vector<ll> v(n);
  for(ll i=0;i<n;i++){
    for(auto j : g[i]){
      v[j]++;
    }
  }
  queue<ll> q;
  for(ll i=0;i<n;i++){
    if(v[i]==0){
      q.push(i);
    }
  }
  while(!(q.empty())){
    ll num=q.front();
    q.pop();
    ans.push_back(num);
    for(auto i : g[num]){
      v[i]--;
      if(v[i]==0){
        q.push(i);
      }
    }
  }
  for(ll i=0;i<n;i++){
    cout<<ans[i]+1<<((i==n-1) ? "\n" : " ");
  }
  return 0;
}