ABC201 F 解答
F - Insertion Sort（2484）
問題
問題文
1 から N までの番号が振られた N 人の人が左右一列に並んでいます。はじめ、左から i 番目の人の番号は Pi です。
あなたの目標は、以下の 3 種類の操作を繰り返すことで人々が左から番号の昇順で並んでいるようにすることです。これらの操作は、任意の順に何回でも（ 0 回でもよい）行うことができます。
・整数 i ( 1 ≤ i ≤ N )を選ぶ。コスト Ai を払い、人 i を好きな位置に移動させる。
・整数 i (1 ≤ i ≤ N) を選ぶ。コスト Bi を払い、人 i を左端に移動させる。
・整数 i (1 ≤ i ≤ N)を選ぶ。コスト Ci を払い、人 i を右端に移動させる。
目標を達成するまでに支払う合計コストを最小化してください。
制約
1 ≤ N ≤ 2×10^5
1 ≤ Pi ≤ N
1 ≤ Ai, Bi, Ci ≤ 10^9
Pi ≠ Pj ( i ≠ j )
入力は全て整数
考察
公式のyoutube解説に基づいた説明になっています。そのため、本記事での不明点などがあれば、そちらを見ると解決できるかもしれません。逆に、公式解説で説明が簡略化されている点などは本記事がお役に立てるかもしれないです。いきます。
人々を昇順に整列させます。
まずは、節約を考えず最も豪勢にコストを使う場合に、整列完了までに必要となるコストを求めます。言い換えるのあれば、最悪でもこれだけのコストがあれば必ず整列させられるコストです。
人の移動は3種類あります。そのなかで一番自由な移動はコストAiのやつですね。この移動はどの場所へも移動可能です。全ての人がこの移動により好きな場所に1回移動することにより整列が可能となります。
このときのコストは
Σ ai
となります。またサラっと書きましたが、各人は2回以上移動する必要はありません。もし、2回移動するのであれば、2回目の移動先に1回目で移動した方が1回分コストが安くなります（コストは正）。
最悪のケースのコストが求まりました。本記事では
Σ ai からどれだけコストの節約が可能か
という流れで説明をしていきます。
次の例を考えます。
8 2 3 5 7 4 6 1
ここで、先ほどと同じように全ての数字を ai のコストで移動させれば、必ず整列が可能です。ですので、
a0 + a1 + ... + a7
のコストを払えば絶対に整列ができます。ここからどれだけ節約ができるかです。
今回は
誰を動かすか？
ではなく、
誰を動かさないか？
に注目をします。ということで、上記列の「3,5,6」を固定させて整列をしてみます。
ここでは次の４つのことが言えそうです。
１）固定する数字よりも前のもの「１，２」はbiの移動で整列可能なため
ai - bi
だけ節約可能。
２）固定する数字「３，４，５」は移動させる必要がないため
ai
だけ節約可能
３）固定する数字に挟まれる数字「４」はaiの移動が必要なため節約できない。
４）固定する数字よりも後ろの数字「７，８」はciの移動が必要なため
ai - ci
だけ節約可能。
です。もともと多めに見積もっていますので、さらに安い方法で移動できればその分のコストが浮くという感じでしょうか。
以上により
どの数字を固定するか
を調べることで節約できる値がわかります。節約の最大値が求まればそれを最悪値から引いてあげればそれが答えになります。
次に、節約を最大化できる固定の組み合わせを求めます。今回は動的計画法（dp）によりその最大値を求めます。構造はこんな感じです。
dp[i][j] :
左から i 番目の人まで「固定する」「固定しない」と決めた際の
左から j 番目の人を一番最後に固定した場合における
i 番目よりも左側の人たち（iも含む）で節約できるコストの最大値
です。少し複雑ですね。具体的に左から固定をしながら説明をしていきます。
まずは１番目ですね。1番目はあまり複雑ではありません。１番目を固定するかどうかです。とはいうものの、dpをインライン化するという説明を後述しますが、その際には「固定しない」遷移を記述する必要はありません。
1番目をまずは固定してみましょう。そうすると、1番目まででは a0 だけ節約が可能です。もとの配列では１の人は0インデックスで７番目の位置に居ましたので、ある配列の７インデックスのところに a0 と書き込みましょう。ひとまず、書き込んでおきます。
２番目です。２番目では固定できない場合というのが存在します。元の列を見てみますと、１は２よりも右にあります。ですので、少なくともどちらかは移動させないといけません。
ただしこの処理は先ほどの配列を用いると特筆して特殊な処理にはなりません。
２番目を固定する際には次の2つに場合分けができます。
１）２番目よりも前に数字を固定していた場合
２）２番目の数字が初めて固定される数字の場合
１）から見ていきます。2番目よりも前に固定していた場合に、固定できるものは元の列で2よりも「左側」かつ「小さい数字」となります。先ほどの１は「左側」という条件が満たせませんでした。ただし、先ほど書き込んだ配列に注目をします。
急ですがこの配列は実はdpテーブルだったのです、ということにしましょう。つまり、この値はその時点での（曖昧な言い方にしています）節約できる最大値になっています。
２は元の配列で１番目にあります。ですので、着目すべきは配列の１よりも左側の数です（この配列のインデックスは各数字が元あった場所）。ということで、7番目に書き込まれたa0という値にはアクセスすることができません。結果として、１，２をともに固定するという状況を防ぐことができます。
以上が「左側」を考慮できる説明となります。「小さい数字」の方が理解は優しいと思います。この時大切となるのは更新順です。元の数列で８というのは０番目にあります。配列はある値よりも左側を見るので必ずこのインデックスは見られてしまいます。しかし、０番目が更新されるのは一番最後です。それまでは、初期値（０）が入っていますので、計算結果に影響を与えません。
以上により、
今考えている数字が元居た場所のインデックスよりも左側
を見ることにより、今の数字よりも前に固定した数字のうちで、固定が可能な数字の節約した値を求めることができます。
今回は欲しいのは節約値の最大値ですね。ですので、１）における節約値の最大値は
左側インデックスの最大値 ＋ a1
となります。
２）２を初めて固定する場合です。この場合は簡単です。
0は「a0-b0」だけ節約できますので、
a0 - b0 + a1
ですね。もう少しいうのであれば、その数字よりも左側のai - bi の和となります。
１）と２）を比べて大きい数字が２を固定したときの節約の最大値となりますので、dpテーブルの１番目（２は1番目にある）に書き込みましょう。
以上により、その時点での”左側の”節約の最大値が求まりました。ですので、あとは右側の値を求めていき、その和の最大値で答えを更新していきます。
ここで、説明を省略したものを２点ほど補足します。
1点目です。上記の説明で、なんかdpテーブルは１つで計算できてしまいましたね。定義のところでは、iとjの2次元になっていました。このように、2次元のものを1次元化してしまうdpをインラインdpと言うそうです。もし２次元だった場合には、i を増やすたびにdpに入っている全ての値を次のi+1に移す必要があるため、計算が間に合わなくなってしまいます。「固定しない」という遷移も書く必要が出てきます。ですので、1次元にしています。
ただ、1次元にしてもやっていることは同じです。２次元の処理をしています。上記の処理を見てみると「i番目の人を固定させる」と「j インデックスより左の最大値を求める」のように2次元の処理を行っています。ただし、値が変わらない遷移はわざわざ書く必要がないよね、という感じです。
この辺の説明が下手ですみません。更新順に気を付ければ次元を落とせる問題はたくさんありますので、取り組んでみてください。慣れが大きいと思います。
２点目は「j インデックス目よりも左の最大値を求める」です。これは、あの有名なデータ構造が使えそうですね。セグメント木です。いろいろと条件がありますが、区間クエリに関してlog N でその処理を行ってくれるという優れものです。区間取得にはこちらを用いています。
以上により、答えを求めることが可能です。が、あと１点だけ大切なことを。コストb,cについてです。前に移動するものをコストb、後ろに移動するものをコストc、としましたが、これって、コストaよりもb,cの方が小さいという前提があります。実際にaの移動は万能です。どこへでも行けます。ですので、bの移動はaとbの小さいほう、cの移動はaとｃの小さいほうで可能であるという処理を最初の方に入れてあげてください。
あとはコメントで補足していきます。
実装
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
//0-indexed
template<class T, T(*op)(T, T), T(*e)()>
class segtree
{
private:
int n;
vector<T> v;
public:
segtree(int n_)
{
int x = 1;
while (n_ > x) x <<= 1;
n = x;
v.resize(2 * n - 1, e());
}
void set(int k, T x)
{
k += n - 1;
v[k] = x;
while (k > 0)
{
k = (k - 1) / 2;
v[k] = op(v[k * 2 + 1], v[k * 2 + 2]);
}
}
T get(int k) { return v[k + n - 1]; }
//[a,b)
T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
T query_sub(int a, int b, int k, int l, int r) {
if (b <= l || r <= a) return e();
if (a <= l && r <= b) return v[k];
T c1 = query_sub(a, b, 2 * k + 1, l, (l + r) / 2);
T c2 = query_sub(a, b, 2 * k + 2, (l + r) / 2, r);
return op(c1, c2);
}
//display segtree value
void display(string text = "segtree value")
{
cout << text << endl;
int cnt = 0;
int end = 1 << cnt;
int l = v.size();
for (int i = 0; i < l; ++i)
{
cout << v[i] << " ";
if (i == end - 1)
{
++cnt;
end += 1 << cnt;
cout << endl;
}
}
cout << endl;
}
};
ll op(ll a, ll b) { return max(a, b); }
ll e() { return 0; }
int main()
{
int n;
cin >> n;
vector<int> p(n);
rep(i, n) cin >> p[i];
rep(i, n) --p[i];
vector<int> a(n), b(n), c(n);
rep(i, n) cin >> a[i] >> b[i] >> c[i];
//aの方がコストが小さい場合に更新する
rep(i, n) b[i] = min(b[i], a[i]);
rep(i, n) c[i] = min(c[i], a[i]);
//もとの列で何番目いたか（緑色の数字）
vector<int> q(n);
rep(i, n)q[p[i]] = i;
segtree<ll, op, e> seg(n);
//左側と右側の節約値
ll sl = 0, sr = 0;
rep(i, n) sr += a[i] - c[i];
ll ans = 0;
rep(i, n)
{
//i番目までに1つでも固定している場合
//iを小さい順に更新するため、
//iより大きな値が左にあっても0となっている
ll now = seg.query(0, q[i]) + a[i];
//i番目で初めて固定した場合
now = max(now, sl + a[i]);
//セグ木の更新
seg.set(q[i], now);
//区間和の更新
sl += a[i] - b[i];
//判定の前にsrからa[i]-c[i]を取り除く、
//i番目は固定している（a[i]-c[i]の割引は使えない）
sr -= a[i] - c[i];
//１）今のans
//２）now(iを含めて左の値)とsr（iより右の値）の和
//この2つを比べる
ans = max(ans, now + sr);
}
//ansには節約値が入っている
ans *= -1;
rep(i, n) ans += a[i];
cout << ans << endl;
return 0;
}あとがき
説明が不正確な点があるかと思います。私自身、本問題は理解したつもりでいますが、言語化しようとするととっても難しいですね。非常にややこしいです。そのため、理解できない点はなんなりとお申し付けください。ひとえに私の力不足です。
本記事で扱った内容に関して補足や類題などを紹介しておきます。
セグメント木
インライン化
037 - Don't Leave the Spice（★5）
セグ木以外にもいろいろなdpで使えます。使えないのももちろんあります。
これでABC201の解説はおしまいです。難しい問題が多かったです。やはり最近ABCが難化しているような気がします。問題の成長と皆様に負けないように私も精進しなきゃですね。頑張らねば。
ここまで読んでいただきありがとうございました。とても嬉しいです。嬉しさに溢れています。また、ABC202の解答でお会いしましょう。F問題がとっても難しいみたいなので、心が折れないと良いのですが、、、
この記事が気に入ったらサポートをしてみませんか？