第16回日本情報オリンピック 予選(過去問)から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#E - 尾根 (Ridge)
僕が作成、提出したコードは、以下のとおりです。
/* AtCoder Problems in C++ #E - 尾根 (Ridge) https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_e 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int h,w; int calc(int x,int y){ return (x*w+y+1); } int main(void){ cin>>h>>w; vector<pair<int,pair<int,int>>> v; for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ int m; cin>>m; v.push_back({m,{i,j}}); } } sort(v.begin(),v.end()); vector<int> dx={1,0,-1,0}; vector<int> dy={0,1,0,-1}; int ans=0; vector<vector<int>> vv(h,vector<int>(w)); for(auto i : v){ int x=i.second.first; int y=i.second.second; set<int> s; for(int j=0;j<4;j++){ if((0<=x+dx[j] && x+dx[j]<h) && (0<=y+dy[j] && y+dy[j]<w) && vv[x+dx[j]][y+dy[j]]!=0){ s.insert(vv[x+dx[j]][y+dy[j]]); } } int num=s.size(); if(s.find(-1)!=s.end() || num>1){ vv[x][y]=-1; ans++; }else if(num==1){ vv[x][y]=*s.begin(); }else if(num==0){ vv[x][y]=calc(x,y); } } cout<<ans<<endl; return 0; }