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

No.3541 Progression (C++)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 20
作問者 : Rho / テスター : alcea tRue souta-1326
ProblemId : 13255 / yukicoder contest TSG LIVE! 16 コードゴルフコンテスト (順位表) / 自分の提出
問題文最終更新日: 2026-05-16 12:27:03
yukicoder contest TSG LIVE! 16 コードゴルフコンテストの他の問題:

問題文

長さ $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もしくは右上の雲マークをクリックしてアカウントを作成してください。