yukicoder1077を解いた

はじめに (ネタバレ無し)

こんにちは
ひぽたふです。

解きながらの考察、実際の解法をまとめておこうかなと思います。

今回解いた問題はこれです。

No.1077 Noelちゃんと星々4 - yukicoder

星2.5の問題です。
なんとか解けた、という感じの問題でした。

以下はネタバレがあるので見る際は注意してください。

解きながらの考察 (ネタバレ　方針まで)

ここからはネタバレがあります。 問題を解いている際に考えていたことをまとめておこうかなと思います。

---

問題概要

点がN個与えられる。
点の高さはである。

点が広義単調増加(全て )になるように変化させたい。
動かす必要のある距離の総和の最小値を求めよ。

考察

単調増加になるようなパターンを全部検討できると話が早いね。
どこの点を動かしているかと、今まで動かした点の最高位置が分かれば他の点についても検討できるかな？

制約は・・・点の数が10³と、動ける範囲が10⁴かあ。
愚直にDPを考えるとで10⁷に収まりそうだね。

点を動かせる範囲がY通り考えられるから、さらにが追加でかかってちょっとはみ出す感じかな。

分岐が複雑じゃなさそうだから、内部処理を高速化できるかな？
とりあえずDPを実装してみるよ。

加算しながら最小値を求める・・・、高速化しにくい形が出てきたかなあ。

具体的にどういう順番で計算しているかを確認してみようかな。
すると、同じ計算を何度もしている部分を発見！

(自分はここでセグ木なり何なりを考えてしまって時間がかかりました。)

最終的によーく計算順番を見て、最小値を求める順番を考えるとDPの内部処理が高速化されてAC！

あとがき + 解法(ネタバレ全開)

DP問題ですね。

動かしたい点()と、今まで動かした点の最大値()を引数に考えます。
戻り値は最小コストとします。

DPテーブルのサイズはですね。

点を動かす最大値がで本当にいいのかも考えておきます。

最大値をより高い方向にずらす場合を考えます。
特定の点をにずらしたい場合というのは、動かしたい点より前に以上の高さが存在する場合です。
そのような点は、それよりも前に以上の高さが存在する必要があり・・・。

開始点まで考えても以上にある点は存在しないので、点を動かす範囲をまでで考えます。

次に分岐を考えます。

点を動かせる範囲は、今までの最大値() ~ 取りうる最大値()です。
分岐数はですね。

ここまで整理すると以下の漸化式になります。

そのため、単純なDPを考えるとの計算量がかかってしまいます。
10^{4 + 3 + 3}なのでこのままだと厳しいですね。

そこで、内部ループの高速化を考えます。
単純に実装した場合、下図のような計算を行なっています。

こののところで毎回同じ計算していることに気がつくと思います。

そのため、予め加算しておくと下図のような計算になります。

毎回minを求めているのでまだ高速化できていません。
このminをそれぞれで求めるために、右側（小さい区間）から計算します。
(自分はここでセグ木を使って最小値を求め始めて泥沼化しました・・・。)

右側から求めた場合、番目から終端までのminは、min(直前の区間の値, 番目の値)になってで求めることができますね。

これでの値がで求まり、最終的にとなります。

ソースコード

int main() {
  ll input(n);
  vector<ll> y(n);
  REP(i, n) cin >> y[i];

  ll YMAX = 10000;
  vector<vector<ll>> table(n + 1);

  // 初期値
  REP(i, n + 1) {
    if (i == n) table[i] = vector<ll>(YMAX + 1, 0);
    else table[i] = vector<ll>(YMAX + 1);
  }

  // DPの計算
  REPD(i, n) {
    ll minv = LLONG_MAX;
    FORD(h, YMAX, 0) {
      // ここの式が今回の難しいポイントだったと思います
      minv = min(minv, table[i + 1][h] + abs(y[i] - h));
      table[i][h] = minv;
    }
  }

  print(table[0][0]);
}

マクロに関しては別の記事でまとめてあります。

テンプレート - 競プロを頑張るブログ

ループと入出力のみ使用しています。
REPは半開区間、FORは閉区間となっています。

https://yukicoder.me/submissions/496223

DPの終端を0で初期化していますね。
変化させる場所がない時はコストが0だからというお気持ちを込めています。

コードにしてみると簡潔ですね。

それでは、またっ！