JOI 2018/2019 予選 過去問から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#D - 日本沈没 (Japan Sinks)
僕が作成、提出したコードは、以下のとおりです。
/* AtCoder Problems in C++ #D - 日本沈没 (Japan Sinks) https://atcoder.jp/contests/joi2019yo/tasks/joi2019_yo_d 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n; cin>>n; vector<int> a(n); for(int i=0;i<n;i++){ cin>>a[i]; } vector<bool> sea(n+2); sea[0]=sea[n+1]=true; for(int i=0;i<n;i++){ sea[i+1]=(a[i]<=0); } int num=0; for(int i=1;i<=n;i++){ if(!sea[i] && sea[i-1]){ num++; } } vector<pair<int,int>> vp; for(int i=0;i<n;i++){ if(a[i]>0){ vp.push_back(make_pair(a[i],i+1)); } } sort(vp.begin(),vp.end()); int ans=num; for(int i=0;i<vp.size();i++){ int j=vp[i].second; sea[j]=true; if(sea[j-1] && sea[j+1]){ num--; }else if(!sea[j-1] && !sea[j+1]){ num++; } if(i+1==vp.size() || vp[i].first<vp[i+1].first){ ans=max(ans,num); } } printf("%d\n",ans); return 0; }