No.3541 Progression (C++)
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 20
作問者 :
Rho
/ テスター :
alcea
tRue
souta-1326
タグ : / 解いたユーザー数 20
作問者 :
Rho
/ テスター :
問題文最終更新日: 2026-05-16 12:27:03
問題文
長さ $N$ の正整数列 $A = (A_1, A_2, \ldots, A_N)$ が与えられます。
$A$ の連続部分列の中で等差数列であるもののうち、最長なものの長さを求めてください。
入力
$N$ $A_1\ A_2\ \ldots\ A_N$
- 入力は全て整数
- $1 \leq N \leq 2000$
- $1 \leq A_i \leq 10^9$
出力
答えを一行に出力せよ。
末尾の改行や空白の有無は問わない。
スコア
想定解: $114$ bytes
スコア計算式
提出されたソースコードのコード長が $x$、この問題の想定解のコード長が $y$ であるとき、そのソースコードのスコアは、$\max(500 - x + y, 100)$ 点である。この問題のスコアはこの問題に提出されたソースコードのスコアの最大値である。
サンプルプログラム (C++)
C++ での解答例を示す。このコードを提出することで、$194$ 点を得ることができる。
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> A(N);
for(int i = 0; i < N; i++) {
cin >> A[i];
}
int ans = 1;
for(int i = 0; i < N - 1; i++) {
int d = A[i + 1] - A[i];
for(int j = i + 1; j < N; j++) {
if(A[j] - A[j - 1] != d) {
break;
}
if(ans < j - i + 1) {
ans = j - i + 1;
}
}
}
cout << ans << endl;
}
サンプル
サンプル1
入力
5 3 1 4 7 5
出力
3
$A$ の連続部分列 $(A_2, A_3, A_4)=(1, 4, 7)$ は等差数列であり、その長さは $3$ です。
$A$ の等差数列である連続部分列であって、長さが $3$ より長いものは存在しないので、$3$ を出力してください。
サンプル2
入力
5 3 1 4 1 5
出力
2
サンプル3
入力
1 1000000000
出力
1
サンプル4
入力
10 10 9 8 7 6 5 4 3 2 1
出力
10
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。