7K12 blog

猫でも分かるアルゴリズム解説

技術室奥プログラミングコンテスト#4 Day1 D - スキップ

f:id:tkr987:20200620193523p:plain

https://atcoder.jp/contests/tkppc4-1/submissions/13233825

  • 単調増加、減少をカウントするためフラグの初期値を0にして、単調増加になったらフラグを1、単調減少になったらフラグを-1にする

f:id:tkr987:20200620202418p:plain

絶対値の差  |A_{vj} - A_{vi}| はマスjとマスiの距離(のようなイメージ)になるので、Σ(隣り合ったマスの距離)=増加する限界までの距離 になる。減少も同様の考え方になる。したがって、単調増加と単調減少が何回でてくるかカウントした値が答えになる。単調増加と単調減少をカウントするためchangeフラグ初期値を0として、単調増加になったらフラグを1、単調減少になったらフラグを-1にして、カウントする実装が考えられる。