ARC 134

Table of Contents

A - Bridge and Sheets

すでに敷いたシートの右端を $r$ とすると, $r < x$ となる $x$ までをカバーするのに必要なシーツの枚数は $\displaystyle \left\lceil \frac{x-r}{W} \right\rceil$ である. これをひたすら繰り返す

提出コード

B - Reserve or Reverse

$l = 1, r = N$ として以下を繰り返すと辞書順最小になる

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vvint a(26);
    rep(i, n) {
        a[s[i] - 'a'].push_back(i);
    }

    int l = 0, r = n - 1;
    while (l < r) {
        // [l,r] の範囲にある文字のうち s[l] 未満の最小の文字のうちで一番右側にあるものの index を探す
        int ok = 0;
        rep(c, 26) {
            if (s[l] - 'a' <= c)
                break;

            // 右端以上になっている要素は消す
            while (!a[c].empty() && a[c].back() > r)
                a[c].pop_back();

            // 一つも要素がない or 左端より小さい値しかなかったら交換できないので飛ばす
            if (a[c].empty() || a[c].back() < l)
                continue;
            r = a[c].back();
            ok = 1;
            break;
        }
        if (ok) {
            swap(s[l], s[r]);
            r--;
        }
        l++;
    }
    cout << s << endl;
}

$r^\prime$ の探し方を二分探索で探すという方法もある.

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vvint a(26);
    rep(i, n) {
        a[s[i] - 'a'].push_back(-i);
    }
    rep(i, 26) reverse(all(a[i]));

    int r = -(n - 1);
    rep(i, n) {
        rep(c, 26) {
            if (s[i] - 'a' <= c)
                break;
            if (a[c].empty())
                continue;
            // 文字 c のうち, index が r 以下かつ, r にもっとも近いもの
            auto it = lower_bound(all(a[c]), r);
            if (it == a[c].end())
                continue;
            int j = -*it;
            if (i < j) {
                r = -(j - 1);
                swap(s[i], s[j]);
                break;
            }
        }
    }
    cout << s << endl;
}

$a_1 < a_2 < \cdots < a_n$ のときに $a_i \leq x$ となる最大の $i$ を求めたいときは $-a_n < \cdots < -a_1$ にして $-x$ で lower_bound を取ると楽.

$-1$ 倍しない方式だと場合わけが面倒になる.

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vvint a(26);
    rep(i, n) {
        a[s[i] - 'a'].push_back(i);
    }

    int r = n - 1;
    rep(i, n) {
        rep(c, 26) {
            if (s[i] - 'a' <= c)
                break;
            if (a[c].empty())
                continue;
            // 文字 c のうち, index が r 以下かつ, r にもっとも近いもの
            auto it = lower_bound(all(a[c]), r);
            int j = -1;
            if (it != a[c].end() && *it == r) {
                j = *it;
            } else if (it == a[c].begin()) {
                continue;
            } else {
                j = *(it - 1);
            }

            if (i < j) {
                r = j - 1;
                swap(s[i], s[j]);
                break;
            }
        }
    }
    cout << s << endl;
}