Quiz
https://atcoder.jp/contests/joi2019yo/tasks/joi2019_yo_d
AC code
https://atcoder.jp/contests/joi2019yo/submissions/9864231
補足
- 公式解説 https://www.ioi-jp.org/joi/2018/2019-yo/2019-yo-t4-review.html
- これでなんとなく分かるのだが、実装上の注意ポイントがある
- 1:最初から全部沈没している場合(コーナーケース)
- 2:高さが同じものがあるので、それらは同時に沈没させる必要
- 3:高さが同じで連続するものもありうる(例 2 1 1 1 2)
- 3については意識したくないので、C++のuniqueを使って、連続する同じ数字を除去する(工夫ポイント)
2 1 1 1 2 => 2 1 2
- map<int, vector<int>> で高さごとに添え字を管理して、高さの低いものから沈没させ、島数のmaxを取ってAC
// 高さごとにリスト管理
map<ll, VI> mp;
rep(i, N){
ll h = H[i];
mp[h].push_back(i);
}
Code
int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N; cin >> N; VI H(N); rep(i, N) cin>>H[i]; // 最初から全部沈没は除外 ll sum = 0; for(ll h : H) sum+=h; if(sum==0){ p(0); return 0; } if(N==1 || N==2){ p(1); return 0; } // 同じ高さの連続は除外 auto it = unique(ALL(H)); H.erase(it, H.end()); N = H.size(); // 高さごとにリスト管理 map<ll, VI> mp; rep(i, N){ ll h = H[i]; mp[h].push_back(i); } ll island = 1; ll ma = 1; vector<bool> sink(N); for(auto pa : mp){ // ll h = pa.first; VI V = pa.second; for(auto idx : V){ sink[idx] = true; if(idx==0){ if(sink[idx+1]) island--; } else if(idx==N-1){ if(sink[idx-1]) island--; } else{ island++; if(sink[idx+1]) island--; if(sink[idx-1]) island--; } } chmax(ma, island); } p(ma); return 0; }