AtCoder Regular Contest 101 D - Median of Medians

問題

 長さNの数列aについて(l, r)(1 \le l \le r \le N)で切り取られる部分列a_l, a_{l + 1}, \dots, a_rの中央値をm_{l,r}とする。全ての(l,r)についてm_{l,r}を並べた数列mについて中央値を求めよ。

解法

 解説そのまま。

 長さがMである数列bにおける中央値は「bの中にそれより大きいものが\left\lceil \frac{M}{2} \right\rceil個ある整数の中で最大のもの」である。つまりbの中にある数xより大きい整数が何個あるか求められれば二分探索できる。

 mの中にx以上の整数が何個入るか? という問題を考えるとaの各要素について必要な情報はx以上であるかどうかだけ。よってaの各要素をx以上なら1、そうでないなら-1と変換した数列bを考える。これの累積和を取った数列をSとして、S_{l} \le S_{r}である数を求めればよい。これは2(\frac{N(N + 1)}{2}  - (転倒数))であり、転倒数はO(N\log{N})で求まるので間に合う。

反省

 コンテスト終わったすぐ後に解説を見て、中央値は二分探索で求められるんだなーということまでは覚えていたがそこからが思い出せずまた解説を見ることに。この問題の変換はかなり難しいと思う。

 とりあえず作っておいたInversionCountのライブラリを使う機会が来た。マージソート的な実装でやっているんだけど、他の人の提出を見るとBITでやっているほうが多いかもしれない。確かに実行時間1155 msってのはちょっと不安だな。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class InversionCount {
public:
    InversionCount(vector<ll> target) : target_(target) {}
    ll count(ll left = 0, ll right = -1) {
        if (right < 0) {
            //rはtarget_.size()で初期化
            right = target_.size();
        }
        if (right <= left + 1) {
            return 0;
        }
        ll mid = (left + right) / 2;
        ll result = 0;
        //左半分を数える
        result += count(left, mid);

        //右半分を数える
        result += count(mid, right);

        //左右またぐ数を数える
        result += merge(left, mid, right);

        return result;
    }
private:
    ll merge(ll left, ll mid, ll right) {
        vector<ll> l, r;
        for (ll i = left; i < mid; i++) {
            l.push_back(target_[i]);
        }
        for (ll i = mid; i < right; i++) {
            r.push_back(target_[i]);
        }
        //番兵
        l.push_back(LLONG_MAX);
        r.push_back(LLONG_MAX);

        ll left_index = 0;
        ll right_index = 0;
        ll result = 0;
        for (ll i = left; i < right; i++) {
            if (l[left_index] <= r[right_index]) {
                target_[i] = l[left_index];
                left_index++;
            } else {
                target_[i] = r[right_index];
                right_index++;
                result += ((mid - left) - left_index);
            }
        }
        return result;
    }

    vector<ll> target_;
};

int main() {
    ll N;
    cin >> N;
    vector<ll> a(N);
    for (ll i = 0; i < N; i++) {
        cin >> a[i];
    }

    auto medianNum = [&](ll x) {
        vector<ll> b(N + 1, 0);
        for (ll i = 0; i < N; i++) {
            b[i + 1] = (a[i] >= x ? 1 : -1) + b[i];
        }
        InversionCount ic(b);
        return N * (N + 1) / 2 - ic.count();
    };

    ll ok = 0, ng = INT_MAX;
    while (ok + 1 != ng) {
        ll mid = (ok + ng) / 2;
        ll num = medianNum(mid);
        (2 * num >= N * (N + 1) / 2 ? ok = mid : ng = mid);
    }
    cout << ok << endl;
}

AtCoder Regular Contest 058 E - 和風いろはちゃん / Iroha and Haiku

問題

 長さがNであり、各要素が1から10までの整数である数列a_0, a_1, \dots, a_{N - 1}について、連続する部分列で和がX, Y, Zとなるものがこの順で連続しているときXYZを含むとする。XYZを含むものが何通りか求めよ。

解法

 ほぼ解説の通り。

 XYZを含まないものの数を考える。左から一つずつ数列の値を決定していくDPをしていくとき、必要な状態は直前の数列のいくつかである。具体的には和がX + Y + Zまでとなるような直前の数列を保持していれば今考えているところの数字を決定できる。

 これは数字を1 \to "1",2\to "10",3 \to "100", 4 \to "1000"と符号化し、直前の数列とはこれを並べたものとして表現することで状態数を減らすことができる。直前の数列の和は符号化後の数字の長さとなるため、状態数はO(2^{X + Y + Z})となる。あとはこれをN個分、各数字が1から10まで回していくだけなので全体の計算量はO(10N2^{X + Y + Z})

 DPの遷移はたとえば直前の数列を符号化したものが sであったとすると

今回の数字 遷移後の数列を符号化したもの
1 s1
2 s10
3 s100
4 s1000

 となるので、今回の数字をiとすると結局siだけ左にシフトしたものと1i - 1だけ左にシフトしたもののorで書ける。

 「遷移した数列がXYZを含んでいる⇔符号化したものについてX + Y + Z個目,Y + Z個目,Z個目のビットが立っている」なのであらかじめそのようなビットを立てたものを用意しておくとXYZを含んでいるかの判定も簡単に行える。

反省

 数日前1時間10分ほど考えたが解けなかったので今日はすぐ解説を見たが、それでも1時間近くかかった。

 解いていたときは、X, Y, Zの長さを全探索して含まれないところは自由に取れるというので解けるんじゃないかと勘違いしてサンプルが合わずずっと悩んでいた。問題を解いた人の記事を探してみると同じような誤解をしていた人もちらほら見かけるのでちょっと安心するなど。

 解説はぱっと見では何を言っているのかわからないし、実装もどうするのかよくわからなかったけれど、creep04の実装を参考になんとか理解してみるとすごく賢い解法で良い問題に思えた。こういう問題を解けるようになりたい。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, X, Y, Z;
    cin >> N >> X >> Y >> Z;

    constexpr ll MOD = (ll)1e9 + 7;
    const ll MAX = 1LL << (X + Y + Z - 1);

    //XYZを含む⇔符号化するとX + Y + Z - 1個目, Y + Z - 1個目, Z - 1個目のビットが立っている
    const ll NG_BITS = (1LL << (X + Y + Z - 1)) | (1LL << (Y + Z - 1)) | (1LL << (Z - 1));

    //dp[i][j] := i番目まで見て,直前の数列を符号化したものがjであるときのXYZとなっていない数
    vector<vector<ll>> dp(N + 1, vector<ll>(MAX, 0));
    dp[0][0] = 1;

    for (ll i = 0; i < N; i++) {
        for (ll j = 1; j <= 10; j++) {
            for (ll k = 0; k < MAX; k++) {
                //k:前回までのbit列
                //遷移:kをjだけ左にシフトして、そこに先頭だけ1を立てたものを入れる
                ll t = (k << j) | (1LL << (j - 1));

                //XYZとなっているかの判定
                if ((NG_BITS & t) != NG_BITS) {
                    //上の方は関係ないのでマスクする
                    t &= (MAX - 1);

                    dp[i + 1][t] += dp[i][k];
                    dp[i + 1][t] %= MOD;
                }
            }
        }
    }

    //全ての数からXYZとならない数を引く
    ll ans = 1;
    for (ll i = 0; i < N; i++) {
        ans *= 10;
        ans %= MOD;
    }

    for (ll i = 0; i < MAX; i++) {
        ans += MOD - dp[N][i];
        ans %= MOD;
    }
    cout << ans << endl;
}

AtCoder Regular Contest 057 C - 2乗根

問題

 \sqrt{N}の上k桁がa_1 a_2 \dots a_kとなるような最小の正整数Nを求めよ。

解法

 解説そのまま。

 10進法でa_1 a_2 \dots a_kと表記されるものをAとする。\sqrt{N}の上k桁がAとなっていることはある整数tが存在しA^2 \times 10^{2t} \le N \lt (A + 1)^2 \times 10^{2t}と同値。

 t = nでこの条件を満たす正整数Nが存在する場合、t = n + 1ではより範囲が広がるのでやはり正整数Nが存在する。またt = nで条件を満たすNが存在しないとt = n - 1でも存在しない。よってtを大きいほうから考えていき条件が満たされない状況になるまで小さくしていけば良い。

 これを整数の範囲で考えるので下限は切り上げ、上限は切り下げで考えていくと上手く範囲が取れる。

反省

 1時間44分(1WA)でAC。数が大きすぎてまともに扱えないので桁DP的な感じで決定していくのかとか、桁数に対する二分探索とかいろいろ考えたけど結局わからなかった。多倍長整数を使うとできるということを考えもしなかったのがひどいが、他の人の解法を見てもなんでこれで上手く範囲が取れているのかいまいち理解ができない。

 C++でやるなら#include <boost/multiprecision/cpp_int.hpp>としてboost::multiprecision::cpp_int;を使えば良いらしい。環境がないのでPythonで実装をした。

コード

 AtCoderでコードを見るとC++の文法を前提としているからかPythonの切り捨て除算//コメントアウトっぽく表示されて非常に見にくい。

a = int(input())
b = a + 1

a = a * a
b = b * b - 1

while (a + 99) // 100 <= b // 100:
    a = (a + 99) // 100
    b //= 100
print(a)

AtCoder Regular Contest 056 C - 部門分け

問題

 N人の社員をいくつかの部門に分けることを考える。社員ijの間には信頼度w_{i,j}が定まっており、部門分けのスコアはKを定数として \displaystyle (部門の数)\times K - (異なる部門に属する2人の間の信頼度の総和)

 として計算される。スコアの最大値を求めよ。

解法

 dp[S]を社員の集合Sに対する問題の答えとする。Sの部分集合をTとして、これが一つの部門であるとすると

 {\displaystyle dp[S] = dp[S - T] + K + (S-TとTの間の信頼度の総和)}

 となる(解説を参照のこと)。これはSに含まれる社員間の信頼度の総和から、S-Tに含まれる社員間の信頼度の総和およびTに含まれる社員間の信頼度の総和を引いたものとなる。つまり任意の部分集合について社員間の信頼度の総和をあらかじめO(2^n)で求めておけば、DPの遷移はO(1)で行える。

 このDPの計算量はO(3^n)となるため間に合う。

反省

 1時間59分(2WA)でAC。30分そこそこで部分点解法を書いたあとはあまり考察が進まず。集合に対してDPを考えるというのも典型なんだろう。しっかりできるようになっておきたい。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, K;
    cin >> N >> K;
    vector<vector<ll>> w(N, vector<ll>(N));
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < N; j++) {
            cin >> w[i][j];
        }
    }

    //各部分集合ごとの信頼度の和
    vector<ll> sum(1LL << N, 0);
    for (ll i = 0; i < (1LL << N); i++) {
        vector<ll> members;
        for (ll j = 0; j < N; j++) {
            if (i & (1LL << j)) {
                members.push_back(j);
            }
        }
        for (ll j = 0; j < members.size(); j++) {
            for (ll k = j + 1; k < members.size(); k++) {
                sum[i] += w[members[j]][members[k]];
            }
        }
    }

    //dp[i] := 頂点集合iに対する答え
    vector<ll> dp(1LL << N, 0);
    for (ll i = 1; i < (1LL << N); i++) {
        for (ll j = i; j > 0; j = (j - 1) & i) {
            dp[i] = max(dp[i], dp[i ^ j] + K - (sum[i] - sum[i ^ j] - sum[j]));
        }
    }
    cout << dp[(1LL << N) - 1] << endl;
}

AtCoder Regular Contest 055 C - ABCAC

問題

 文字列S(|S| \le 2 \times 10^5)が与えられるので、それを空でない文字列A, B, Cを用いてABCAC (文字列を連結したもの)と分割する方法が何通りあるかを求めよ。

解法

 ABC / ACと分ける切れ目を全探索する。分けられた前半部分と後半部分で、prefixとsuffixがそれぞれ何文字一致しているかが分かれば、それをA,Cとして分割する方法が何通りあるかはO(1)で求められる。

 このprefix/suffixが何文字一致しているかはあらかじめもとのSに対してZ-algorithmを適用すれば先頭に対する最長共通接頭辞の長さがO(|S|)でわかる。Sを反転したものに対してもZ-algorithmを適用することで末尾に対する最長共通接尾辞の長さもO(|S|)でわかるため、この問題が解ける。

反省

 2時間10分(1WA)でAC。1時間ほど考えてわからなかったのでとりあえず嘘っぽい部分点解法を出して諦めた。部分点解法は2回目のAが出てくる位置、及びAの長さをループし、さらに文字列比較でその長さ分だけかかるので、O(|S|^3)になっているのではないかという気がするが、800msecほどでなんとか部分点は取れだ

 解説を読むと、最初はKMPとかを使って解くのかと思ったんだけど、書いてあるようにZ-algorithmを使えばスマートらしい。Z-algorithmはよく知らなかったので多少調べて、なんとなく確かに上手くいきそうだなーくらいの理解で他人の実装を写して出した。答えとして調整する部分もいまいち理解が浅くてもう一度出されても苦労しそうな問題に思える。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

//A[i] := SとSのi文字目以降の最長共通接頭辞の長さ
//としたものを返す
//参考:http://snuke.hatenablog.com/entry/2014/12/03/214243
vector<ll> Z_algorithm(string S) {
    vector<ll> A(S.size());
    A[0] = S.size();
    ll i = 1, j = 0;
    while (i < S.size()) {
        while (i + j < S.size() && S[j] == S[i + j]) {
            j++;
        }
        A[i] = j;
        if (j == 0) {
            i++;
            continue;
        }
        ll k = 1;
        while (i + k < S.size() && k + A[k] < j) {
            A[i + k] = A[k];
            k++;
        }
        i += k;
        j -= k;
    }
    return A;
}

int main() {
    string S;
    cin >> S;

    vector<ll> z = Z_algorithm(S);
    reverse(S.begin(), S.end());
    vector<ll> rz = Z_algorithm(S);
    reverse(rz.begin(), rz.end());

    const ll n = S.size();
    ll ans = 0;

    for (ll i = n / 2 + 1; i < n; i++) {
        ll a = min(n - i - 1, z[i]);
        ll c = min(n - i - 1, rz[i - 1]);
        ans += max(min(a + c - (n - i) + 1, n - i - 1), (ll)0);
    }

    cout << ans << endl;
}

AtCoder Regular Contest 054 C - 鯛焼き

問題

 タイヤと木がそれぞれN個あり、各タイヤと木の組について相性が良いか悪いかが決まっている。相性の良いタイヤと木のみを組み合わせて全てのタイヤと木を組み合わせる方法が何通りあるか、その偶奇を求めよ。

解法

 行列式を計算して2で割った余りを求める。詳細は解説なり各種ブログで。

反省

 3時間14分(11WA)でAC。久しぶりに地獄という感じだった。

 考察は1時間で諦めた。完全マッチングの組み合わせ数って数えられるのかなとググってNP困難とか書いてあるのを見つけたくらい。行列として見てどうにかするっていうのも一瞬考えたけど行列式求めるだけで良いっていうのはわからなかった。

 大変だったのは解説を読んでから。行列式が求められない。後でわかったことは、整数行列の行列式の値は整数にはなるが、自分の実装では途中で小数まで考えないといけないはずの計算が発生していたので整数型では答えが合わなくなるということだった。ACしたときは適当にxor取っている他の人の実装パクったら通ったという感じ。

 整数型で計算途中にmodも取らず通している提出もあるので実装の問題なんだろう。自分の提出をdoubleにしても誤差でめちゃくちゃになっているようなので、この計算方法はダメらしい。整数型でmod2における逆元を計算するか、なぜか誤差の出ない上の方法でやるしかないようだ。

 テストケースが非公開なのはやはり地獄。あと数回分くらいの我慢だ……。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

//n×n行列の行列式を求める
ll determinant(vector<vector<ll>> M) {
    const ll n = M.size();
    ll result = 1;
    for (ll i = 0; i < n; i++) {
        if (M[i][i] == 0) {
            //対角成分が0だった場合はその列の値が0でない行と交換する
            for (ll ni = i + 1; ni < n; ni++) {
                if (M[ni][i] != 0) {
                    swap(M[i], M[ni]);
                    //result = -result;
                    break;
                }
            }
        }

        if (M[i][i] == 0) {
            return 0;
        }

        for (ll ni = i + 1; ni < n; ni++) {
            //ni行のi列目を全て0にする
            //ll r = M[ni][i] / M[i][i];

            for (ll j = i + 1; j < n; j++) {
                //M[ni][j] -= r * M[i][j];
                M[ni][j] ^= M[ni][i] * M[i][j];
            }
        }

        //行列式は対角成分の積
        result *= M[i][i];
    }
    return result;
}

int main() {
    ll N;
    cin >> N;
    vector<vector<ll>> M(N, vector<ll>(N));
    for (ll i = 0; i < N; i++) {
        string S;
        cin >> S;
        for (ll j = 0; j < N; j++) {
            M[i][j] = S[j] - '0';
        }
    }

    cout << (determinant(M) % 2 == 0 ? "Even" : "Odd") << endl;
}

AtCoder Regular Contest 053 C - 魔法使い高橋君

問題

 N(\le 10^5)個の魔法があり、i番目の魔法を唱えると気温がa_i(\le 10^9)度上がってb_i(\le 10^9)度下がる。全ての魔法を1回ずつ唱えるとき、この間の気温の最大値を最小化せよ。

解法

 まずa_i \lt b_iであるものについてa_iの昇順に、次にa_i = b_iであるものについて任意の順番に、最後にa_i \gt b_iであるものについてb_iの降順に使用していけば良い。

 a_i \lt b_iであるものについてa_iの昇順に使用すれば良いことはわかりやすいが、a_i \gt b_iであるものについてb_iの降順に使用すれば最善となることについては、逆から見た状況を考えると良い。最後の温度から考え始めてa_i \gt b_iであるものを用いて気温の最大値を最小化するのは、最初の気温からa_i \lt b_iであるものを用いて最小化するのと変わらない状況である。

反省

 1時間12分(0WA)でAC。1時間考察したがコードを書く段階には到達せず、結局1行も書かないまま解説を見ることになった。

 これが解けないのはちょっとつらいところ。a_ib_iの大小関係で場合分けして考えることはしていたが、a_i \gt b_iであるものについてどういう順番で使用すれば最善なのかがわからなかった。逆から見るという発想が完全に抜けてしまっていたとは……。そうでなくとも大きいbが来ればそれ以降はその中に変化が収まってしまうみたいなところは考えていたのになぁ。残念。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<pair<ll, ll>> lesser, equal, greater;
    for (ll i = 0; i < N; i++) {
        ll a, b;
        cin >> a >> b;
        if (a > b) {
            greater.emplace_back(a, b);
        } else if (a == b) {
            equal.emplace_back(a, b);
        } else {
            lesser.emplace_back(a, b);
        }
    }

    sort(lesser.begin(), lesser.end(), [&](pair<ll, ll>& lhs, pair<ll, ll>& rhs) {
        return lhs.first < rhs.first;
    });
    sort(greater.begin(), greater.end(), [&](pair<ll, ll>& lhs, pair<ll, ll>& rhs) {
        return lhs.second > rhs.second;
    });

    ll ans = 0, curr = 0;
    for (auto p : lesser) {
        curr += p.first;
        ans = max(ans, curr);
        curr -= p.second;
    }
    for (auto p : equal) {
        curr += p.first;
        ans = max(ans, curr);
        curr -= p.second;
    }
    for (auto p : greater) {
        curr += p.first;
        ans = max(ans, curr);
        curr -= p.second;
    }

    cout << ans << endl;
}

AtCoder Regular Contest 061E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip

問題

 N(\le 10^5)個の駅がM(\le 2\times 10^5)個の路線で繋がれている。各路線は一つの会社によって運営されており、同じ会社の路線を使い続ける限り料金は1である一方、違う会社の路線に乗り換える場合は新たに料金が1かかる。駅1から駅Nまで移動するのにかかる料金の最小値を求めよ。

解法

 頂点に「最後に使った路線の会社」の情報も加えてダイクストラ法を行う。このとき普通に行うと頂点数がO(M)、一つの頂点から出ている辺の数がO(M)となり、全体で辺の数がO(M^2)となって間に合わない。

 各頂点について違う会社に乗り換えるときはある特殊な部分を通過するということにする。これによって辺の総数はO(N + M)となり解けた。

反省

 2時間19分(8WA)でAC。最初は会社ごとにノードを作ってそれでダイクストラ法をやれば解けると勘違いしてWA(TLE, MLE含む)。これは同じ会社が管理しているものでも飛び石になったりしている場合があるし、計算量も全然十分ではなくてんでダメ。

 次はダイクストラ法の各更新部分でdfsして同じ会社の路線を埋めていくという方針でやったがWA。最短で行ける場合ではなくとも、その後に同じ会社の路線が多く続いていて有利になるパターンというのはあるので最短だけ取ってもダメ。

 この二つをやって1時間20分くらい経ってしまったので諦めて解説PDFを見たが、辺の数がO(M^2)になるという説明が理解できず(辺の総数と、ある頂点における辺の数とを混同していた!)愚直な辺の構築をやってTLEというのを2回ほど。

 テストケースが公開されているのを思い出してTLEになった部分をやってみると、priority_queueのサイズがO(M)になって各頂点でO(M)の辺の数を調べていくのでそれはそうだということにようやく気付いた。

 あとは解説で書かれているように、乗り換えるパターンを書いてAC。あまりきれいなコードにはならなかった。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N, M;
    cin >> N >> M;

    struct Edge {
        ll to, c;
    };
    //edges[i][j] := 頂点iに路線jでいるときコスト0で行ける次の頂点
    vector<map<ll, vector<ll>>> edges(N);
    for (ll i = 0; i < M; i++) {
        ll p, q, c;
        cin >> p >> q >> c;
        p--; q--; c--;
        edges[p][c].push_back(q);
        edges[q][c].push_back(p);
    }

    constexpr ll INF = INT_MAX;
    vector<map<ll, pair<bool, ll>>> cost(N);
    struct Element {
        ll node, cost, c;
        bool operator>(const Element& rhs) const {
            return cost > rhs.cost;
        }
    };
    priority_queue<Element, vector<Element>, greater<Element>> pq;

    cost[0][-1] = { true, 0 };
    pq.push({ 0, 0, -1 });

    while (!pq.empty()) {
        Element t = pq.top();
        pq.pop();

        if (cost[t.node][t.c].first && t.cost > cost[t.node][t.c].second) {
            continue;
        }

        if (t.c == -1) {
            for (auto p : edges[t.node]) {
                ll new_cost = t.cost + 1;
                for (auto next : p.second) {
                    if (!cost[next][p.first].first || new_cost < cost[next][p.first].second) {
                        cost[next][p.first].first = true;
                        cost[next][p.first].second = new_cost;
                        pq.push({ next, new_cost, p.first });
                    }
                }
            }
        } else {
            ll new_cost = t.cost;
            for (auto next : edges[t.node][t.c]) {
                if (!cost[next][t.c].first || new_cost < cost[next][t.c].second) {
                    cost[next][t.c].first = true;
                    cost[next][t.c].second = new_cost;
                    pq.push({ next, new_cost, t.c });
                }
            }
            //-1への遷移
            if (!cost[t.node][-1].first || new_cost < cost[t.node][-1].second) {
                cost[t.node][-1].first = true;
                cost[t.node][-1].second = new_cost;
                pq.push({ t.node, new_cost, -1 });
            }

        }
    }

    ll ans = (cost[N - 1][-1].first ? cost[N - 1][-1].second : INF);

    cout << (ans == INF ? -1 : ans) << endl;
}

SRM519 Div1 Easy - BinaryCards

問題

 なんだっけ。

解法

 なるほどなぁ。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class BinaryCards {
public:
    long long largestNumber(long long A, long long B) {
        if (A == B) {
            return B;
        }
        ll ans = 0;
        while (true) {
            ll a = f(A);
            ll b = f(B);
            if (a != b) {
                return ans + b * 2 - 1;
            }
            ans += a;
            A -= a;
            B -= b;
        }
    }
private:
    ll f(ll x) {
        for (ll i = 1; ; i *= 2) {
            if (i > x) {
                return i / 2;
            }
        }
    }
};

SRM518 Div1 Easy - LargestSubsequence

問題

 辞書順最大の部分文字列を求めよ。

解法

 大きい文字から取っていって、一番最後に取った位置を記録しておく。次の文字はそこからスタート。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class LargestSubsequence {
public:
    string getLargest(string s) {
        string ans;
        ll start = 0;
        for (ll i = 25; i >= 0; i--) {
            for (ll j = start; j < s.size(); j++) {
                if (s[j] - 'a' == i) {
                    ans += s[j];
                    start = j;
                }
            }
        }
        return ans;
    }
};