数列操作に関する手筋まとめ
とりあえず考えること
- 要素/総和のmod/パリティに注目する
- 操作回数を求めることができるか(特に総和を用いて)
- 逆操作が可能か
操作が単純な操作に分解できるか
階差数列を考える
数列2つを一致させるなら差を取る
操作の縮約ができないか/周期を持たないか
- 上の典型的な場合として,単純な一連の操作を考える(最初から順番に操作していくなど)
- 数列を自分で用意することができる場合は,数列も単純なものを用意する({1,2,..}, {n,n,...})
例題 (順次追加)
2つの数列の差を取る & 操作回数が決まる
逆操作
D - Decrease (Contestant ver.)
操作できる数に制約があるので逆操作を考えるのは難しい.
単純な数列で単純な一連の操作を考えると縮約ができる
ARC 086 D - Non-decreasing (600) - 主食は米
単純な操作を考えよう
総和に注目する -> 逆操作を考える -> 階差数列を見る -> 逆操作を分解する
