mayoko’s diary

プロコンとかいろいろ。

2016 TCO Algorithm Round 1A med: EllysSocks

TopCoder
問題

TopCoder Statistics - Problem Statement

解法

二分探索します。

check(x) = (ペアの socks の差が x 以内で P 個のペアを作ることが出来るか) というのを求められれば良いです。
これには貪欲解法が使えます。まず S をソートし, 0 から順番に見ていきます。「S[i] と S[i+1] の差が x 以内なら (i, i+1) をペアにする」という戦略でペアを作っていくのが良く, 一回ソートしておけば O(|S|) でチェック出来ます。

この貪欲戦略が正しい理由は, 以下のとおりです。

  • S[0] と S[1] がペアに出来るなら, 1 < i, j を満たす i, j を使って 0-i, 1-j とペアを作ることが出来たとしても, 0-1 とペアにする戦略と比べて損することはない(逆に 0-i, 1-j をペアに出来るなら 0-1, i-j がペアに出来ることが保証されるので)
  • S[0] と S[1] がペアに出来ないなら, 0 は 任意の i とペアに出来ないので, S[1] 以降から考えれば良い

本番考えた理由はこれなんですが, 2 通りの方法で証明できそうなのでやってみます。


上に書いた証明は「最初の一歩を貪欲で選んだことで後で後悔しない」ってやつです。「この貪欲をするとこういう解しか出来ないけれど, 最適解としてこういう極端なのだけ候補にしてしまっていいのか」ってのを考えてみます。

方針としては, 仮想的に最適解を一つ考えます。この最適解が上で考えたような解(つまり i-i+1 のようにペア同士が隣接している解)と一致していない場合, 一致させるように最適解を変化させていけることを示します。

最適解であるペアの集合を Ps とします。Ps の中にはたくさんのペア p がありますが, そのなかで min(p.first, p.second) の値が最小のものを選び, その最小値を i とします。

i と i+1 がペアになっている場合
隣り合っているので OK
i+1 とペアになっている index があるが, それが i でない場合
i とペアになっている index を x, i+1 とペアになっている index を y とすると, i < i+1 < x, i < i+1 < y が成り立ちます。
この時, 以下のように i-i+1, x-y とペアにしても構わないことがわかるので, i-i+1 をペアにして良い

  • i < i+1 < y < x の時, S[i+1]-S[i] <= S[x]-S[i], S[x]-S[y] <= S[x]-S[i] より
  • i < i+1 < x < y の時, S[i+1]-S[i] <= S[x]-S[i], S[y]-S[x] = (S[y]-S[i+1]) - (S[x]-S[i+1]) <= (S[y]-S[i+1]) より

i+1 とペアになっている index が存在しない場合
i-x がペアになっていたとすると, i-i+1 をペアにして, x のペアが存在しないようにしてもペアの数は変わらないので問題ないです。

これを繰り返すと, 結局ペアはすべて隣り合うことになります。

bool ok(int x, const vector<int>& S, int P) {
    int cnt = 0;
    int n = S.size();
    for (int i = 0; i < n-1; ) {
        if (S[i]+x >= S[i+1]) {
            cnt++;
            i += 2;
        } else i++;
    }
    return cnt >= P;
}

class EllysSocks {
public:
    int getDifference(vector <int> S, int P) {
        sort(S.begin(), S.end());
        int low = -1, high = 1e9+7;
        while (high-low > 1) {
            const int med = (low+high)/2;
            if (ok(med, S, P)) high = med;
            else low = med;
        }
        return high;
    }
};