問題一覧 > 通常問題

No.2374 ASKT Subsequences

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 113
作問者 : Kanten4205Kanten4205 / テスター : KowerKoint2010KowerKoint2010 hibit_athibit_at poyonpoyon
7 ProblemId : 9677 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-07-07 00:44:49

問題文

ある整数列について、長さ 44 の連続とは限らない部分列 (a1,a2,a3,a4)(a_1, a_2, a_3, a_4) が以下の条件を満たすとき、その部分列をあさかつ型の部分列と言います。

  • ある正整数 kk であって、a2=a1+(k+10),a3=a2k,a4=a3+(k+1)a_2 = a_1 + (k + 10), a_3 = a_2 - k, a_4 = a_3 + (k + 1) をすべて満たす kk が存在する。
長さ NN の整数列 AA が与えられます。整数列 AA の部分列のうち、あさかつ型の部分列の個数を求めてください。ただし、22 つの部分列が整数列として同じでも、取り出す位置が異なる場合は区別するものとします。

入力

NN
A1 A2  ANA_1\ A_2\ \cdots \ A_N

  • 4N20004 \leq N \leq 2000
  • 1Ai2000 (1iN)1 \leq A_i \leq 2000\ (1 \leq i \leq N)
  • 入力はすべて整数

出力

整数列 AA の部分列のうち、あさかつ型の部分列の個数を 11 行に出力してください。

サンプル

サンプル1
入力
4
1 15 11 16
出力
1

部分列 (A1,A2,A3,A4)(A_1, A_2, A_3, A_4) は、k=4k = 4 としたときに、A2=A1+(4+10), A3=A24,A4=A3+(4+1)A_2 = A_1 + (4 + 10),\ A_3 = A_2 - 4, A_4 = A_3 + (4 + 1) となり、問題文の条件を満たすので、あさかつ型の部分列です。
整数列 AA の部分列のうち、あさかつ型の部分列はこれしかないので、11 を出力します。

サンプル2
入力
10
1 19 4 14 11 50 15 20 11 20
出力
4

次の 44 つの部分列が、それぞれあさかつ型の部分列になります。

  • (A1,A2,A5,A8)=(1,19,11,20)  k=8(A_1, A_2, A_5, A_8)=(1,19,11,20)\ \cdots\ k = 8 のとき、条件を満たします。
  • (A1,A2,A5,A10)=(1,19,11,20)  k=8(A_1, A_2, A_5, A_{10})=(1,19,11,20)\ \cdots\ k = 8 のとき、条件を満たします。
  • (A1,A2,A9,A10)=(1,19,11,20)  k=8(A_1, A_2, A_9, A_{10})=(1,19,11,20)\ \cdots\ k = 8 のとき、条件を満たします。
  • (A1,A4,A5,A7)=(1,14,11,15)  k=3(A_1, A_4, A_5, A_7)=(1,14,11,15)\ \cdots\ k = 3 のとき、条件を満たします。

サンプル3
入力
10
1 1 1 1 1 1 1 1 1 1
出力
0

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