Official
A - 山の眺め / Mountain View Editorial
by
A - 山の眺め / Mountain View Editorial
by
kyopro_friends
初心者の方へ
- AtCoder をはじめたばかりで何をしたらよいか分からない方は、まずは practice contest の問題A「Welcome to AtCoder」を解いてみてください。基本的な入出力の方法が載っています。
- また、プログラミングコンテストの問題に慣れていない方は、AtCoder Beginners Selection の問題をいくつか解いてみることをおすすめします。
- C++入門 AtCoder Programming Guide for beginners (APG4b) は、競技プログラミングのための C++ 入門用コンテンツです。
- Python入門 AtCoder Programming Guide for beginners (APG4bPython) は、競技プログラミングのための Python 入門用コンテンツです。
問題文の指示通りに、毎回愚直に条件の判定を行うと全体で \(\Omega(N^2)\) かかるため、実行時間制限に間に合わせることは困難です。
山が見える条件は「先頭から順に見て今まで見たどの山よりも高い」という意味なので、今まで見た山の高さの最大値を保持しながら、前から順に条件を確認すればよいです。計算量は \(O(N)\) です。
実装例 (C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<int>h(n);
for(int i=0; i<n; i++) cin >> h[i];
vector<int>ans;
int pre = 0;
for(int i=0; i<n; i++){
if(pre < h[i]){
ans.push_back(i+1);
pre = h[i];
}
}
int k = ans.size();
for(int i=0; i<k; i++){
cout << ans[i];
if(i == k-1){
cout << endl;
}else{
cout << ' ';
}
}
}
実装例 (Python)
N = int(input())
H = list(map(int, input().split()))
ans = []
pre = 0
for i, h in enumerate(H, 1):
if pre < h:
ans.append(i)
pre = h
print(*ans)
