AtCoderのABC-Cの解答について質問がございます。

Question

こちらの問題の解答コードに関して質問がございます。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll> x, y;
    y.push_back(0);
    for (int i=0;i<n;++i) {
        ll a;
        cin >> a;
        if (a < 0) x.push_back(-a);
        else y.push_back(a);
    }

    x.push_back(0);//1
    sort(x.begin(), x.end());
    int ms = min(k, (ll)y.size()-1);//2
    ll ans = 1e16;
    for (int i = ms; i >= 0; i--) {
        if (k - i >= x.size()) break;//3
        ans = min(ans, 2 * y[i] + x[k - i]);
        ans = min(ans, 2 * x[k - i] + y[i]);
    }
    cout << ans << endl;
    return 0;
}

#####質問内容
1.なぜ0を追加しているのでしょうか？このひとつ前のfor文で負の数はマイナスして追加してるので正の数にされてるのでsortすると0,...となると思うのですが狙いがわかりません。。
2.なぜy.size()から1引いているのでしょうか？
3.入力する座標の個数(n)がkを上回ったら弾く処理という理解で合ってますでしょうか？
以上になります。よろしくお願い致します。

Answer 1

1.0を追加するのは、正方向、もしくは負方向のキャンドルに火をつけないパターンを特別扱いしなくて済むようにです。xだけソートしているのは逆順にしたかっただけでしょう。入力がもともとソートされているので、ここについてはほかのやり方もいろいろあると思いますが、単にそれを選んだというだけです。

2．yにおける有効なインデックスがy.size() - 1までだからです。その後のforループで変数iがyの有効なインデックスから出ないようにする目的です。

3.2の場合と同じく、k - iがxの有効なインデックスの範囲から出ないようにするためのbreakです。

Comments

[cunwe]

入力例4で言うとsortが終わったところまででxには0,3,4,7,9でyには1,2,3,4で合ってますでしょうか？

[yudedako67]

yにも0が入っています。別の場所で追加してるのでわかりづらいですが、xとyでやってることはほぼ同じです。

[cunwe]

本当ですね、ありがとうございます。話が変わって申し訳ありませんが1文目のans=のansが2文目のmin(ans, ...)のansに入るのですよね？

[yudedako67]

そうです。条件式を使わずに最小値を更新していく典型的な書き方です。

[cunwe]

すいません、自分には0を追加する理由が正/負の方向のキャンドルに火をつけないパターンを特別扱いしなくて済むためというのがまだ理解できません。。どういうことでしょうか...?

[yudedako67]

0を入れずに書いてみればわかります

[cunwe]

あ、kが2でmsも2のときにx[2-2]=x[0]となり、x[0]やy[0]が0だと「0足す」ということで正/負方向しか進まないことを表現できるってことですね。(日本語が下手ですいません。)ありがとうございます！