ABC 362 E — Count Arithmetic Subsequences

考察

長さ1の部分列は必ず等差数列でN個ある。長さ2以上では先頭位置i、第2位置jを選ぶと公差d=A_j−A_iが一意に決まる。先頭がiで長さl、公差dの列は、j>iかつA_j−A_i=dである「先頭j、長さl−1、公差d」の列の前へA_iを付けたものとして分解できる。各pair(i,j)は長さ2の等差部分列を一つ作り、それより長い列はdp[j][l−1][d]をそのまま延長する。dは負数や10^9規模も取るため、位置ごとの連想配列または事前列挙した差の座標圧縮で管理する。

採用する候補: iを後ろから処理し、dp[i][length][difference]へ後続jの同じ公差の状態を加える。

位置順・長さ・公差という等差部分列の必要情報だけで閉じ、Nが80なので全長を同時に数えられる。

棄却する候補: 全ての部分列をbit maskで列挙し、隣接差が一定か判定する。

部分列数が指数的で、N=80では列挙の入口にも立てない。

ans[1]=Nとする。iをN−1から0へ、j>iを走査してd=A_j−A_iを得る。dp[i][2][d]へ1を足し、各l≥3でdp[j][l−1][d]をdp[i][l][d]へ加える。同時に各追加分をans[l]へ法上で加算し、全長の答えを出力する。

典型の発動条件

部分列の先頭追加DP

発動条件: 先頭二要素で属性が決まり、残りが同属性の短い部分列になるとき。

後ろから状態を確定し、後続状態の前に一要素を接続する。

疎な差分状態

発動条件: 差や傾きが大きな整数範囲を取るが、実際に現れる種類が入力pairに限られるとき。

mapまたは位置別圧縮で存在する公差だけを保存する。

問題固有の要素

「最後の二項」で延長する定番DPと対称に、「最初の二項」を固定して後ろから処理しても公差情報が閉じる。

別の問題へ持ち帰る視点: 部分列DPでは走査方向を選び、既に確定した側の状態へ一要素を付ける形にする。

正当性

等差列の最初二indexを固定すると公差が定まり、その後は同公差の次index始まり列だけ接げる。右から計算して依存先を確定する。各列は最初二indexと残りに一意分解され長さ別に漏れ重複なく数えられる。

実装上の注意

  • 長さ1をDPのpair遷移とは別に数える。A_j−A_iは負も含み、各加算を指定modで正規化する。

復習の核

  • 長さ2のbase caseと長さ3の延長を具体的な三要素で追う。dpのiが先頭か末尾かをコード中でも統一する。

計算量と制約

時間

N≤80。始点、次index、長さの走査 O(N³)、hash公差照会はexpected O(1)。

空間

始点×長さ×異公差を全保存する安全な上界 O(N³)、公差mapを使う。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 80; 1 \leq A_i \leq 10^9; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Count Arithmetic Subsequences の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 列・subsequence DP

主題
  • 列・subsequence DP: 列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 列・subsequence DP

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 列・subsequence DP

      • 列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題