公式
A - 連続上昇気温 / Consecutive Rising Temperatures 解説
by
A - 連続上昇気温 / Consecutive Rising Temperatures 解説
by
physics0523
初心者の方へ
- 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 入門用コンテンツです。
隣接項 \(A_k,A_{k+1}\) について \(A_k<A_{k+1}\) となることが最も長く連続する部分を検出すればよいです。
このためには、 \(A_k<A_{k+1}\) となる部分を繋げられるだけ繋げ、 \(A_k \ge A_{k+1}\) となるなら直ちに分断するとよいです。
以下の手続きで正解できます。
- 現在の上昇期間 \(cur=1\) 、答え \(res=1\) と初期化します。
- \(i=2,3,\dots,N\) について、以下を繰り返す。
- \(A_{i-1} < A_i\) なら現在の上昇期間が続くため、 \(cur\) に \(1\) 加算する。
- \(A_{i-1} \ge A_i\) ならこれ以上上昇期間を延ばすことができず新たな上昇期間が始まるため、 \(cur=1\) とする。
- \(res=\max(res,cur)\) とする。
メモ: \(-40 \le A_i \le 45\) より上昇期間の最大の長さは高々 \(86\) です。このことから、より愚直な解法でも正答できます。
実装例 (C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin >> N;
vector<int> A(N);
for(auto &nx : A){cin >> nx;}
int res=1,cur=1;
for(int i=1;i<N;i++){
if(A[i-1]<A[i]){
cur++;
}
else{
cur=1;
}
res=max(res,cur);
}
cout << res << "\n";
return 0;
}
投稿日時:
最終更新:
