Official

A - 山の眺め / Mountain View Editorial by kyopro_friends Editorial for printing


初心者の方へ


問題文の指示通りに、毎回愚直に条件の判定を行うと全体で \(\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)

posted:
last update: