CFR #839 (Div. 3) D. Absolute Sorting 解説

先日開催されたCodeforces Round #839 (Div. 3)のD問題を解説します。
本番中に通せなかったのと、あまりみたことのないタイプの問題だったので記憶に残すためにも書きます。

問題概要

問題文
正の数からなるある数列Aが与えられる。あるxを選び、と置換した時にAがソートされた状態になるようなxを1つ探す。

制約

解説

まずは小さいケースから考えます。
]
この場合は、すでにソートされていますが、どんなxを選ぶことができるでしょうか？ の時条件を満たし、になると条件を満たしません。

]
この場合はどうでしょうか？ になると条件を満たします。

この2ケースを比較すると、連続する2数によってxの上限、下限が決まることに気づくと思います。

サンプルケースの8つ目を実際に試してみます。 ]
初めのxの範囲をbottom = 0, top = 1e9とすると、はじめの2数29613295と52036613では、top = 40824954になります。 以降上限値はずっと変わらず、最後の2数81409090と73215でbottom = 40741153となります。 の範囲であれば、どこでも条件を満たすことになるため、適当に下限値を出力すれば良いでしょう。 テストケースによっては、bottom>topのようになることがあります。この場合は条件を満たすxが存在しないため、-1を出力します。

回答例（ソースコード）

// 諸々は省略

void solve(){
    ll n; cin >> n;
    vi a(n); cin >> a;
    ll l = 0, r = 1000000000;
    rep(i,n-1){
        if(a[i]>a[i+1]){
            chmax(l,(a[i]+a[i+1]+1)/2);
        }else if(a[i]<a[i+1]){
            chmin(r,(a[i]+a[i+1])/2);
        }
    }
    cout << (l<=r?l:-1) << endl;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    int t; cin >> t;
    while(t--) solve();
}