結果

問題 No.3456 Common Difference is D
コンテスト
ユーザー 96chanmen
提出日時 2026-02-28 15:56:56
言語 Python3
(3.14.3 + numpy 2.4.2 + scipy 1.17.0)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
WA  
実行時間 -
コード長 2,257 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 812 ms
コンパイル使用メモリ 20,956 KB
実行使用メモリ 32,020 KB
最終ジャッジ日時 2026-02-28 15:57:07
合計ジャッジ時間 6,984 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 5 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

N, D = map(int, input().split())
A = list(map(int, input().split()))

from collections import defaultdict

# def optimized_dp(nums, max_diff=100, threshold=3):
#     n = len(nums)
#     dp = [defaultdict(int) for _ in range(n)]
#     total = 0
    
#     # 「j番目の要素」と「i番目の要素」のペアを比較し、それらを基に等差数列を構築
#     # (外側のループ) i 番目の要素を終点とする等差数列の情報がすべて更新される
#     for i in range(n):
#         for j in range(i):
#             diff = nums[i] - nums[j]
#             # 差分が max_diff を超える場合はスキップ
#             if abs(diff) > max_diff:
#                 continue
            
#             # j番目の要素で終わり、公差が diff の等差数列の個数
#             prev = dp[j].get(diff, 0)
#             # 新たに i 番目の要素を加えることで、長さが1増加した等差数列を構築できるため、+1 をする。
#             current = prev + 1
#             # i番目の要素で終わり、公差が diff の等差数列の個数
#             dp[i][diff] += current

#             if current >= threshold:
#                 total += 1

#             print(dp)

#     return total

# result2 = optimized_dp(A, max_diff=2, threshold=D)

# 1. テーブル定義
# キー：(数列の中身のタプル), 値：その数列ができる通り数
cnt=0
dp = defaultdict(int)

# 2. 初期値（空の数列を1つとみなす、あるいは長さ1から始めるなど実装による）
dp[tuple()] = 1

def is_arithmetic(seq):
    if len(seq) <= 2:
        return True
    diff = seq[1] - seq[0]
    return seq[-1] - seq[-2] == diff

for x in A:
    # 3. 前の状態の引継ぎ
    prev_dp = dp.copy()

    # 4. 更新
    for seq_tuple, count in prev_dp.items():
        # 現在の数列 seq_tuple に x をくっつける
        new_seq = list(seq_tuple)
        new_seq.append(x)

        # 等差数列の条件を満たすなら辞書に追加
        if is_arithmetic(new_seq):
            dp[tuple(new_seq)] = (dp[tuple(new_seq)] + count)
            if len(new_seq)==3:
                if new_seq[-1]-new_seq[-2]==D:
                    cnt += 1

# 集計
print(cnt)
0