mayoko’s diary

プロコンとかいろいろ。

SRM647div2hard:BuildingTowers

こっちはやや手間取った。

問題:http://community.topcoder.com/stat?c=problem_statement&pm=13606

解法:easy問題のようにすべての頂点について高さを2分探索することはできない。しかし、よく考えると、高さが最大の点は、高さ制約がある点の間で山を作れば良いことがわかる(めっちゃわかりづらいですが、例えば点3に高さ制約2,点7に高さ制約4があるとすると、高さは点3から順に、[2,3,4,5,4]のようにするということ)。
そのためにやることは2つ。まず与えられた条件として、高さの制約があるが、実際には最高でどこまで高さとして可能かを検証する。これはeasy問題と同様二分探索でできる。
次に、それぞれの頂点の間で山を作る。これは、左側と右側それぞれをスタート地点として、どこまで離れたところを山の頂点にできるかを二分探索すれば良い。
以下ソースコード

vector<int> X, T;
vector<int> mX, mT;

bool ok(int pos, ll h, int K) {
    int n = X.size();
    for (int i = 0; i < n; i++) {
        if (h > (ll)K * abs(pos-X[i])+T[i]) return false;
    }
    return true;
}

class BuildingTowers {
public:
    long long maxHeight(int N, int K, vector <int> x, vector <int> t) {
        X.clear(); T.clear();
        mX.clear(); mT.clear();
        X.push_back(1); T.push_back(0);
        for (int i = 0; i < (int)x.size(); i++) {
            X.push_back(x[i]); T.push_back(t[i]);
        }
        int n = X.size();
        for (int i = 0; i < n; i++) {
            int low = 0, high = T[i]+1;
            while (high - low > 1) {
                ll med = (high + low) / 2;
                if (ok(X[i], med, K)) low = med;
                else high = med;
            }
            mX.push_back(X[i]); mT.push_back(low);
        }
        ll ret = (ll)(N-mX[n-1]) * K + mT[n-1];
        for (int i = 0; i < n-1; i++) {
            ll l = mX[i], r = mX[i+1];
            {
                // lからどこまで伸ばせるか
                int low = 0, high = r-l+1;
                while (high - low > 1) {
                    int med = (high+low) / 2;
                    ll h = mT[i] + (ll)K*med;
                    if (h <= mT[i+1]+(ll)K*(r-l-med)) low = med;
                    else high = med;
                }
                ret = max(ret, mT[i]+(ll)K*low);
            }
            {
                // rからどこまで伸ばせるか
                int low = 0, high = r-l+1;
                while (high - low > 1) {
                    int med = (high+low) / 2;
                    ll h = mT[i+1] + (ll)K*med;
                    if (h <= mT[i]+(ll)K*(r-l-med)) low = med;
                    else high = med;
                }
                ret = max(ret, mT[i+1]+(ll)K*low);
            }
        }
        return ret;
    }
};