mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #330 (Div. 1) A. Warrior and Archer

つい最近, 作問ミスをしたので他人事ではない。

解法

なんとなく思うのは, Warrior 側の人は, 端っこ以外の数字をとっても得しないということです。つまり, Warrior 側の人が取る数字は左端から l 個, 右端から r 個 (l+r = (n-2)/2) となるはずです。一方で, Archer 側の人は, これらの値を取られた際に距離を最大化しようとするので, なんとなく x[n-1-r] - x[l] が答えになりそうな気がします。
この予想は正しくて, Warrior 側の人がどういう順番で l+r 個の数字を取り除いても, 上手いこと真ん中らへんの数字を取り除くことで Warrior 側の人がそれ以上有利に数字を取り除くことが出来ないようにすることが出来ます。

ということで, Warrior 側の人が端っこの数字をどのように取り除くか(要するに l と r の配分)で場合分けして得られる値の最小値が答えになります。

さて, この問題はコンテスト中は n が偶数という制約がついていなかったことによって上の解法が嘘解法であることが判明してコンテストからこの問題が取り消され, コンテスト自体も unrated になりました。ということで, 上の解法の反例を示してみます。

n = 5 の時, x として
1 2 3 4 5
という数列を考えます。上の解法を用いると, 例えば 4 と 5 を消した際の 3-1 = 2 が最小値になりそうな気がしますが, 実際には
Warrior が初手で 5 を取ると, Archer 側は,
4 を取る -> Warrior は 3 を取れば 1
3 を取る -> Warrior は 4 を取れば 1
2 を取る -> Warrior は 1 を取れば 1
1 を取る -> Warrior は 4 を取れば 1
となり, 最小値は 1 であることがわかります。ということで, 上の解法は通用しません。このようなことが起こってしまう原因は, 最後に数字を取り除くのが n : odd の場合 Warrior になり, Archer が真ん中らへんの数字を取り除いても Warrior 側が更に距離を詰められる様に数字を取り除けるのが原因です。そのために, n : even という制約が必要なのでした。

const int MAXN = 200020;
int x[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> x[i];
    sort(x, x+n);
    int ans = x[n-1]-x[0];
    for (int i = 0; i <= (n-1)/2; i++) {
        int l = i;
        int r = n-1 - ((n-1)/2-i);
        ans = min(x[r]-x[l], ans);
    }
    cout << ans << endl;
    return 0;
}