主食は米

主に競プロ備忘録

数列操作に関するメモ

とりあえず考えること

  • 要素/総和のmod/パリティに注目する
  • 操作回数を求めることができるか(特に総和を用いて)

  • 逆操作が可能か

  • 操作が単純な操作に分解できるか

  • 階差数列を考える

  • 操作の縮約ができないか/周期を持たないか

  • 上の典型的な場合として,単純な一連の操作を考える(最初から順番に操作していくなど)
  • 数列を自分で用意することができる場合は,数列も単純なものを用意する({1,2,..}, {n,n,...})

例題 (順次追加)

D - Decrease (Contestant ver.)

操作できる数に制約がある. 単純な数列で単純な一連の操作を考えると縮約ができる

ARC 086 D - Non-decreasing (600) - 主食は米
単純な操作を考えよう

AGC 010 B - Boxes - 主食は米

総和に注目する -> 逆操作を考える -> 階差数列を見る -> 逆操作を分解する