2014 Yandex.Algorithm Elimination Stage, Round1 F - Data Mining

問題概要

n 個の要素からなる数列 a が与えられる.あなたは以下の操作を k 回行える.

  • ある要素の値を隣接する(どちらかの1方の)要素に加える.

k 回の操作の後の,数列に含まれる値の最小値を最大化せよ.
また,出力はその値を 10^9+7 で割った余りで出力するものとする.

・制約
1 <= n <= 10^4
1 <= k <= 10^6
1 <= a_i <= 10^8

解法

K < N の時は,どう頑張っても a の K + 1 番目の値より大きく出来ず,また逆にこれを実現する分配方法が存在するので,ソートして K + 1 番目の値を出力する.

K >= N のときは,できるだけでかい隣接2項を互いに足し合わせまくって,最後の N - 1 回で残りに足していく感じ.
どの隣接2項が良いかを考えるのだが,互いに足し合わせる操作は N - K + 1 回行われることを考えれば,ある a[i] と a[i + 1] を選んだときの答えは
fib(N - K + 1) * min(a[i], a[i + 1]) + fib(N - K + 2) * max(a[i], a[i + 1])
である.
これが一番大きいものを選べばよいのだが,N - K + 1 が大きいとオーバーフローして計算できないので,long double でごまかす.
とはいっても十分小さい K に対してはフィボナッチ数の比が黄金比に十分近づいていないので,愚直にやらないといけない.
具体的には,N - K + 1 > 40 のとき(これはかなり雑で,オーバーフローギリギリを狙うのが良いと思う),黄金比を φ として
min(a[i], a[i + 1]) + ma(a[i], a[i + 1]) * φ
の大きさで一番大きい i を選択する.
あとは先の値を mod で計算すれば答えになる.

ソースコード

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

using ll = long long;
using ld = long double;

constexpr int mod = 1e9 + 7;

int main() {
    int k, n;
    cin >> k >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    if(k < n) {
        sort(begin(a), end(a));
        cout << a[k] << endl;
    } else {
        vector<ll> fib(k + 1);
        fib[1] = fib[2] = 1;
        for(int i = 3; i < k + 1; ++i) {
            fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
        }
        ll ans = 0;
        if(k - n + 2 <= 40) {
            for(int i = 0; i + 1 < n; ++i) {
                ans = max(ans, fib[k - n + 1] * min(a[i], a[i + 1]) + fib[k - n + 2] * max(a[i], a[i + 1]));
            }
            ans %= mod;
        } else {
            const ld phi = (1.0 + sqrt(5.0)) / 2.0;
            int pos = 0;
            ld val = 0;
            for(int i = 0; i + 1 < n; ++i) {
                if(val < min(a[i], a[i + 1]) + max(a[i], a[i + 1]) * phi) {
                    pos = i;
                    val = min(a[i], a[i + 1]) + max(a[i], a[i + 1]) * phi;
                }
            }

            const ll mi = min(a[pos], a[pos + 1]);
            const ll ma = max(a[pos], a[pos + 1]);
            ans = (((fib[k - n + 1] * mi) % mod) + ((fib[k - n + 2] * ma) % mod)) % mod;
        }

        cout << ans << endl;
    }
}

感想

誤差が不安だったけど,fib(41) / fib(40) の比率がもうほとんど正確な黄金比に近い値になっているので大丈夫なんでしょうきっと.