問題一覧 > ショートコード

No.3541 Progression (C++)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 27
作問者 : Rho / テスター : alcea tRue souta-1326
お気に入りにしたユーザー ProblemId : 13255 / 自分の提出
問題文最終更新日: 2026-05-16 12:27:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
TSG LIVE! 16 コードゴルフコンテスト (順位表) の他の問題:

Problem Statement

You are given a sequence of positive integers $A = (A_1, A_2, \ldots, A_N)$ of length $N$.
Among the contiguous subarrays of $A$ that are arithmetic progressions, find the length of the longest one.

Input

$N$
$A_1\ A_2\ \ldots\ A_N$

  • All input values are integers.
  • $1 \leq N \leq 2000$
  • $1 \leq A_i \leq 10^9$

Output

Output the answer on one line.
Trailing newlines and whitespace are ignored.

Score

Intended solution: $114$ bytes

Score Formula If the code length of a submitted source code is $x$ and the code length of the intended solution of this problem is $y$, the score of that source code is $\max(500 - x + y, 100)$ points.
The score for this problem is the maximum score among the source codes submitted to this problem.

Sample Program (C++)

An example solution in C++ is shown below. By submitting this code, you can obtain $194$ points.

#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;
}

Sample

Sample 1
Input
5
3 1 4 7 5
Output
3

The contiguous subarray $(A_2, A_3, A_4)=(1, 4, 7)$ of $A$ is an arithmetic progression, and its length is $3$.
No contiguous subarray of $A$ that is an arithmetic progression has length greater than $3$, so output $3$.

Sample 2
Input
5
3 1 4 1 5
Output
2

Sample 3
Input
1
1000000000
Output
1

Sample 4
Input
10
10 9 8 7 6 5 4 3 2 1
Output
10

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。