SRM 642 Div2

結果

oox 1037 -> 1080

「値が大きいと二分探索」を100回唱えたい．
毎回，二分探索という解法を疑うのを忘れてしまうので反省．

[Easy: ForgetfulAddition ]

問題

数字からなる文字列sが与えられる．
sの任意の分割に対して，
sの前半部分の数字 + sの後半部分の数字
の中で最も大きい値となるものを返す．

解法

全探索をする．

ソースコード

class ForgetfulAddition {
public:
    int minNumber(string exp) {
        int ans = INT_MAX;
        const int n = exp.size();

        for (int i = 1; i < n; ++i) {
            string a = exp.substr(0, i);
            string b = exp.substr(i, n - i + 1);

            int sum = stoi(a) + stoi(b);
            ans = min(ans, sum);
        }

        return ans;
    }
};

[Medium: LightSwitching ]

問題

N個の電球の列が与えられる．
それぞれの状態は，点灯している（'Y'）か消灯している（'N'）かである．
i番目の電球のスイッチを押して状態を反転すると，iの倍数番目の各々の電球も状態が反転する．
（例．i=2,N=6なら2,4,6番目の電球の状態が反転する）
すべての電球を消灯するのに必要な最小のスイッチ回数を求める．

解法

i番目のスイッチとj番目のスイッチに対して，i < jならばj番目のスイッチを押すことによってi番目の状態を反転させることは出来ない．
なので，小さい番号のi番目電球から見ていって点灯しているならスイッチを押して，iの倍数番目の各々の電球の状態を反転させる．
計算量は．

ソースコード

class LightSwitchingPuzzle {
public:
    int minFlips(string state) {
        int n = state.size();
        int ans = 0;

        for (int i = 0; i < n; ++i) {
            if (state[i] == 'Y') {
                ++ans;
                for (int j = 2; j * (i + 1) <= n + 1; ++j) {
                    int idx = j * (i + 1) - 1;

                    if (state[idx] == 'Y')
                        state[idx] = 'N';
                    else
                        state[idx] = 'Y';
                }
            }
        }
        return ans;
    }
};

[Hard: TallShoes ]

問題

N頂点からなる単純連結無向グラフGと非負の整数Bが与えられ，
Gの各々の辺には非負の重みheightが与えられます．
0番目の頂点からN-1番目の頂点へのパスの中で，パスに含まれるheightの最小値を最大化するものを見つけてください．
ただし，それぞれの辺のheightはkだけ増加することが出来ます．
kだけ増加すると費用がだけかかります．
増加したすべての辺の費用の総和がBを超えてはいけません．

解法

求める値fを2分探索法を使って求めます．
Gの0からN-1の頂点へのパスの中で最小のheightがf以上となるパスが存在するのかを確認します．
もし，そのようなfが存在するならばfを大きくして，存在しないのなら小さくします．
確認方法はGの辺の重みを次のように変形させたグラフ上で最短距離dを求めます．
辺eの重みheightがf以下ならば辺の重みを0にします．
辺eの重みheightがfより大きいならば，辺の重みをとします．

ソースコード

typedef long long ll;

const ll INF = (1LL << 50);

class TallShoes {
    ll g[51][51];
    int N;
    ll B;

public:
    int maxHeight(int _N, vector <int> X, vector <int> Y, vector <int> height, long long _B) {
        N = _N;
        B = _B;
        int SIZE = X.size();

        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                g[i][j] = (i == j) ? 0 : INF;
        for (int i = 0; i < SIZE; ++i)
            g[X[i]][Y[i]] = g[Y[i]][X[i]] = height[i];

        ll lb = 0, ub = (1LL << 30);
        ll ans = 0LL;

        while (ub - lb > 1) {
            ll mid = (lb + ub) * 0.5;

            if (C(mid)) {
                lb = mid;
                ans = max(ans, mid);
            }
            else
                ub = mid;
        }

        return ans;
    }

    ll C(ll f) {
        ll d[N][N];

        for (int i = 0; i < N; ++i) {
            for (int j = i; j < N; ++j) {
                if (i == j)
                    d[i][j] = 0;
                else if (g[i][j] >= INF)
                    d[i][j] = d[j][i] = INF;
                else if (f <= g[i][j])
                    d[i][j] = d[j][i] = 0;
                else
                    d[i][j] = d[j][i] = (f - g[i][j]) * (f - g[i][j]);
            }
        }

        for (int k = 0; k < N; ++k)
            for (int i = 0; i < N; ++i)
                for (int j = 0; j < N; ++j)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

        return d[0][N - 1] <= B;
    }
};