SRM 647 Div2 - tshitaの備忘録Ⅱ

結果

oox 1075 -> 1088

大まかな方針が立ってから詳細を詰めるのが遅すぎる．バッファオーバーフロー恐い．
今回のmedがeasyよりも明らかだったので，見落としがあるのかコーナーケースが恐いのかで確かめるのに時間がかかった．

[Easy: PeacefulLine ]

問題

先生は生徒を一列に並べたい．ただし，任意の隣り合う生徒同士が同じ年齢にならないようにしたい．配列xにすべての生徒の年齢が書かれている．先生が生徒を一列に並べることができるなら"possible"を返し，それ以外は"impossible"と返す．

$1 \le x \le 25, 1 \le x.size() \le 25$

解法

age歳の生徒がnum人いるとします．この時，age歳以外の生徒がnum-1人いればage歳同士は隣り合うこと無く並ぶことができます．したがって，同じ年齢の人が最も多いグループについて成り立っているかを調べれば十分です．

ソースコード

class PeacefulLine {
public:
    string makeLine(vector <int> x) {
        const int n = x.size();
        map<int, int> memo;

        for (int i = 0; i < n; ++i)
            ++memo[x[i]];

        int max_num = 0;
        for (auto it : memo)
            max_num = max(max_num, it.second);

        return (2 * max_num - 1 <= n) ? "possible" : "impossible";
    }
};

[Medium: TravellingSalesmanEasy ]

問題

あなたはセールスマンである．1〜Mの街がM個ある．あなたは複数の商品を持っている．i番目の商品はcity[i]でのみ売ることが出来て，売った利益はprofit[i]である．あなたが訪れる街は既に決まっておりj番目に訪れる街はvisit[j]である．それぞれの街では高々1つの商品しか売ることが出来ない．すべての街を訪れる時，あなたが得ることの出来る総利益の最大値を求めよ．

解法

順番に街を訪れます．i番目の街にいる時に売るべき商品は，i番目の街で売ることが出来る商品の中で最も利益が高い商品です．

$1 \le M \le 100, 1 \le profit \le 100, 1 \le profit.size() \le 100, 1 \le visit.size() \le 2500$

ソースコード

class TravellingSalesmanEasy {
public:
    int getMaxProfit(int M, vector <int> profit, vector <int> city, vector <int> visit) {
        vector<int> item[M];
        const int n = visit.size(), m = profit.size();

        for (int i = 0; i < m; ++i)
            item[city[i] - 1].push_back(profit[i]);

        for (int i = 0; i < M; ++i)
            if (item[i].size() != 0)
                sort(item[i].begin(), item[i].end());

        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (item[visit[i] - 1].size() != 0) {
                res += item[visit[i] - 1].back();
                item[visit[i] - 1].pop_back();
            }
        }

        return res;
    }
};

[Hard: BuildingTowers ]

問題

一列に並んでいる1〜Nの新しい建物をN個建てる．ただし，次の制約を満たすように建物を建てなくてはならない．

それぞれの建物の高さは非負である
1番目の建物の高さは0である
隣り合う建物同士の高さの差の絶対値はK以下である
x[i]番目の建物の高さははt[i]以下である

制約を満たすように建物を建てた時に，最も高い建物の高さを求めよ．

$N \le 10^9, K \le 10^9, 0 \le x.size() \le min(N, 100), t \le 10^9, x[i] < x[i+1]$

解法

建物の制約に着目します．次の具体例を用いて説明します．
N = 20, K = 3, x = {4, 7, 13, 15, 18}, t = {8, 22, 1, 55, 42}

実装を簡単にするために建物の制約x, tに，1番目の建物の高さは0以下，N番目の建物の高さは無限大以下を追加します．ただし，N番目建物の高さの制約が既に与えられている場合は1番目の建物の高さの制約のみを追加します．追加した後のxとtはそれぞれ，
x = {1, 4, 7, 13, 15, 18, 20}, t = {0, 8, 22, 1, 55, 42, INF}
となります．
f:id:tatanaideyo:20150127054846p:plain
この建物の制約をx[i]番目の建物が取りうることの出来る最大の高さh[i]に更新します．
隣り合う建物の高さの差の絶対値はK以下であるので，x[i]番目の建物のh[i]を更新する時はx[i - 1]番目とx[i + 1]番目の建物のh[i - 1]とh[i + 1]に依存します．これは，
$h[i] = min\{h[i], (x[i] - x[i - 1]) \times K + h[i - 1], (x[i + 1] - x[i]) \times K + h[i + 1]\}$
という式で更新されます．
f:id:tatanaideyo:20150127062212p:plain

実装ではx[i]番目の建物に着目した時，その隣り合う建物x[i-1]番目とx[i+1]番目の建物の値h[i-1]とh[i+1]を更新しています．任意のiに対してh[i]をt[i]で初期化して，hの値が最も小さいものから隣り合う建物を更新していきます．更新した後は次のようになります（赤色の点が各々のhの値）．
f:id:tatanaideyo:20150127064012p:plain

最後にx[i]番目とx[i+1]番目の建物の間にある建物の中で最大の高さのものを求めます．
点(x[i], h[i])を通り傾きKの直線l1と，点(x[i+1], h[i+1])を通り傾き-Kの直線l2の交点を(x, h)とします．
この時，hの決め方から点(x[i], h[i])が直線l2の上にあることや，点(x[i+1], h[i+1])が直線l2の上にあることはありません．交点の座標は，
$\left(\frac{(h[i+1] - h[i]) + K \times (x[i] + x[i+1])}{2 \times K} , \frac{(h[i] - h[i+1]) + K \times (x[i+1] - x[i])}{2} \right)$
となります．
この時，x座標は必ず整数を取るわけではないので，切り下げた値x1と切り上げた値x2を見ます．そして，直線l1におけるx1の値と直線l2におけるx2の値の最大値が区間の間で取りうる建物の高さの最大値となります．これをすべての区間で求めると答えになります．
f:id:tatanaideyo:20150127070553p:plain

ソースコード

class BuildingTowers {
public:
    long long maxHeight(int N, int K, vector <int> &_x, vector <int> &_t) {
        // 前処理，番兵の追加
        vector<ll> t(_t.size() + 1);
        vector<int> x(_x.size() + 1);
        x[0] = 1, t[0] = 0;
        for (int i = 1, n = _t.size(); i <= n; ++i) {
            t[i] = _t[i - 1];
            x[i] = _x[i - 1];
        }

        if (_x.size() == 0 || _x[_x.size() - 1] != N) {
            x.push_back(N);
            t.push_back(1e18);
        }
        const int size = x.size();

        // tの値の更新
        priority_queue<pair<ll, int>> que;
        for (int i = 0; i < size; ++i)
            que.push(make_pair(-t[i], i));
        while (!que.empty()) {
            pair<ll, int> now = que.top();
            que.pop();
            if (now.first > t[now.second])
                continue;

            if (now.second != 0) {
                ll next = (ll)abs(x[now.second] - x[now.second - 1]) * K + t[now.second];
                if (next < t[now.second - 1]) {
                    t[now.second - 1] = next;
                    que.push(make_pair(-t[now.second - 1], now.second - 1));
                }
            }
            if (now.second != size - 1) {
                ll next = (ll)abs(x[now.second] - x[now.second + 1]) * K + t[now.second];
                if (next < t[now.second + 1]) {
                    t[now.second + 1] = next;
                    que.push(make_pair(-t[now.second + 1], now.second + 1));
                }
            }
        }

        // 区間の計算
        ll res = 0;
        for (int i = 0; i < size; ++i)
            res = max(res, t[i]);

        for (int i = 0; i < size - 1; ++i) {
            if (x[i + 1] - x[i] <= 0)
                continue;

            int x1 = floor((double)((t[i + 1] - t[i] + (double)K * (x[i] + x[i + 1])) / (2.0 * K)));
            int x2 = ceil((double)((t[i + 1] - t[i] + (double)K * (x[i] + x[i + 1])) / (2.0 * K)));
            ll y1 = (x1 - x[i]) * (ll)K + t[i];
            ll y2 = (x[i + 1] - x2) * (ll)K + t[i + 1];

            res = max({res, y1, y2});
        }

        return res;
    }
};