問題一覧 > 通常問題

No.2374 ASKT Subsequences

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

問題文

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

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

入力

$N$
$A_1\ A_2\ \cdots \ A_N$

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

出力

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

サンプル

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

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

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

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

  • $(A_1, A_2, A_5, A_8)=(1,19,11,20)\ \cdots\ k = 8$ のとき、条件を満たします。
  • $(A_1, A_2, A_5, A_{10})=(1,19,11,20)\ \cdots\ k = 8$ のとき、条件を満たします。
  • $(A_1, A_2, A_9, A_{10})=(1,19,11,20)\ \cdots\ k = 8$ のとき、条件を満たします。
  • $(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もしくは右上の雲マークをクリックしてアカウントを作成してください。