SRM 480 div2 hard: SignalIntelligence

問題

TopCoder Statistics - Problem Statement

解法

最後の数以外は, number[i] < number[i+1] を満たすように並べていくのが最適なので, 最後の数で場合分けして, 他の数は sort してシミュレーションすると答えが得られます。

なぜなのかを考えてみます。
貪欲を考えるときは, p 番目の数 number[p] と p+1 番目の数 number[p+1] について, number[p] < number[p+1] のほうが得(損することはない)ことを示せば良いです。

最後の数以外を考えているので, number[p] を足した後は 2^i - 1 番目からスタート -> 2^j - 1 番目に移動, のような遷移のみを考えれば良いです。

number[p] < number[p+1] とします。
2^i - 1 番目からスタートしたとして, number[p] を足しこんだ後 2^j - 1 に遷移し, number[p+1] を足しこんだ後も同様に 2^j - 1 に遷移したとします。

この場合, 2^j - 1 からの遷移は number[p] を足しこんでも number[p+1] を足しこんでも 2^(j+1) - 1 になります。

これは, どちらも 2^j - 1 に遷移したということから number[p+1] < 2^j, number[p] < 2^j となることからわかります。

一方で, number[p] では 2^j - 1 に遷移して, number[p+1] では 2^k - 1 に遷移する(j < k)場合は, 次に遷移する変化数が 直前の遷移の変化数よりも増加することはないので, number[p] -> number[p+1] と足しこんでいくほうが得です。

bool done[55];
ll pos[63];

class SignalIntelligence {
public:
    long long encrypt(vector <int> numbers) {
        int n = numbers.size();
        memset(done, false, sizeof(done));
        ll ret = 1ll<<62;
        for (int i = 1; i < 63; i++) pos[i] = pos[i-1]*2+1;
        for (int i = 0; i < n; i++) {
            vector<int> v;
            for (int j = 0; j < n; j++) if (i!=j) v.push_back(numbers[j]);
            sort(v.begin(), v.end());
            ll cur = 0;
            for (int j = 0; j < n-1; j++) {
                cur += v[j];
                cur = *upper_bound(pos, pos+63, cur);
            }
            ret = min(ret, cur+numbers[i]);
        }
        return ret;
    }
};