Slope Trick

Slope Trick

初めて触れた用語.
関連問題の解決も非常に困難であり,この概念を理解する過程もかなり困難である.
https://www.acmicpc.net/problem/13323
この問題と関係があるので,先に解いた人は解くことができる.

関連する問題

https://codeforces.com/contest/713/problem/C
https://codeforces.com/contest/866/problem/D
https://github.com/ranaldmiao/sg_noi_archive/blob/master/2018/statements/NOI%202018%20Tasks.pdf
すべて数列に関する問題ですが、白準13323号とCode Force C号は実際には同じ問題です.
13323はA数列の中でランダムに存在する数字で、B数列は昇順で、2つの差の最小のB数列を求めます.
すなわち,A数列内の各数字が1ずつ増加または減少することは,B数列の最小数字増減回数,すなわちC番を求めることに等しい.
いずれにしても、A数列はどうしても最小の昇順で並べなければならないので、どうやって近づくのでしょうか.

に近づく

例として13323の例1入力を用いる.
A数列を(9 4 8 20 14 15 18)とする.
以降はAnAnAn=(A数列のn桁)を使用する.
次に、F(x,k)F(x,k)F(x,k)F(x,k)という関数を作成して使用します.
x=1の場合
ex)F(1,2)F(1,2)F(1,2)は、A数列の第1桁が2の最小数値増減回数である.
では、A数列の最初の数字は9なので、少なくとも7回移動しなければなりません.
つまり、F(1,k)F(1,k)F(1,k)は87 k-A 1∣k-A 1∣k
x>=2の場合
F(x,k)F(x,k)F(x,k)A数列のxビット数がkでなければならない場合
A数列xビットの昇順を達成するためには,全体的に増減する最小数値個数が必要である.
だからF(x,k)=min(F(x,1,k),...F(x−1,0))+∣k−Ax∣F(x,k) = min(F(x-1,k-1),...F(x-1,0)) + |k-Ax|F(x,k)=min(F(x−1,k−1),...F(x−1,0))+∣k−Ax∣
min式部分からk−1までの数字しか存在しないため、他の数字は存在しない.
A数列が最終的に昇順になるには、次の数字がkより小さくなければならないからです.
ex)F(2,3)F(2,3)F(2,3)は最終的にmin(F(1,2)、F(1,1)、F(1,0)+ͩ3ͩmin(F(1,2、F(1,1)、F(1,0)+|3-4|min(F(1,2)、F(1,1)、F(1,0)+ͩ4ͪ
x部分を定数にして87 k-Ax-Ax-∣Ax∣を描くと、よく知られている絶対値パターンが得られます.

では、min(F(x,k),...F(x−1,0))min(F(x-1,k-1),...F(x-1,0))min(F(x−1,k−1),...F(x,1,0)をグラフィックで描画できる場合
どうしても最小値が見つかります.
まず、xが1=1 x−1=1=1であれば、F(xⓐ1,k 1)F(x−1,k 1)F(xⓐ1,k 1)のグラフを以下に示す.
ここで、最小値K 1 K 1 K 1 K 1はA 1 A 1 A 1である.

ではF(2,k)=min(F(1,kά1),...F(1,0))+∣k−A2∣F(2,k) = min(F(1,k-1),...F(1,0)) + |k-A2|F(2,k)=min(F(1,k−1),...F(1,0)+∮∮A 2∮は?
F(1,9)F(1,9)F(1,9)は、まず、例1によって最大値が0となる.
このとき、k=9 k=9 k=9であればmin(F(1,kά1),...F(1,0))=F(1,8)=1min(F(1,k-1),...F(1,0)) = F(1,8) = 1min(F(1,k−1),...F(1,0)=F(1,8)=1.
k=10 k=10 k=10であればmin(F(1,k),...F(1,0))=F(1,9)=0min(F(1,k-1),...F(1,0)) = F(1,9) = 0min(F(1,k−1),...F(1,0)=F(1,9)=0.
つまり、min(F(1,k),...F(1,0))min(F(1,k-1),...F(1,0))min(F(1,k−1),...F(1,0)は、F(1,k)F(1,k)F(1,k)F(1,k)をk軸に平行にして1で示す図形である.
F(2,k)=min(F(1,k−1),...F(1,0))+∣k−A2∣F(2,k) = min(F(1,k-1),...F(1,0)) + |k-A2|F(2,k)=min(F(1,k−1),...F(1,0)+∏∏A 2∏(例ではA 2=4)
以下に示すように、2つの図形の和で表すことができます.

実際には、グラフィックの傾斜が増加した部分では、最大値は表示されません.
いっそ0になってもいいです.
F(x∮1,k)F(x−1,k)F(x∮1,k)をk軸に沿って1だけ平行移動させる場合のパターンの最大値はMである.
∣∣∣∣∣∣∣∣∣𕕤𕕤𕕤𕕤𕕤𕕤𕕤𕕤𕕤

Ax
グラフィック全体の最大値はAxとMの違いによって上昇します.
kがAxであろうとMであろうと、最も高い値を有する.

Ax
グラフィック全体の最大値はAxとMの違いによって上昇します.
kがMの場合にのみ最高の値を有する.

Ax>=MAX>=MAX>=M

グラフィック全体の最大値は変更されません.
kがAxの時だけ最高の価格があります.

最終的に、優先順位キューを利用して、新たに入力した数字AiAi
以前に入力した数字以上の場合はpushを適用するだけです.
新しく入力した数字AiAi.
前に入力した数字を下回ると、一番高い数字がポップアップされます.
AiAiを押すだけでいいです

결국, 우선 순위 큐 안에는 같은 숫자들이 여러 개 존재할 수도 있다.
만약에 큐 안에 (20,20)이 존재한다면
k=20을 기준으로 왼쪽은 기울기가 -2, 오른쪽은 기울기가 0이라는 뜻이다.

큐 안에 (4,20,20)이 존재한다면
k<4인 구역은 기울기가 -3
4<k<20인 구역은 기울기가 -2
k>20인 구역은 기울기가 0이다.