けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

CODE FESTIVAL 2016 qual A C - 次のアルファベット / Next Letter (400 点)

辞書順最小の教育的例題!!!

問題へのリンク

問題概要

長さ  N の文字列  S が与えられる。この文字列に以下の操作をちょうど  K 回行う。行った結果得られる文字列の辞書順最小なものを求めよ。

  •  S の文字を 1 つ選んで、1 文字進める。ただし 'z' は 'a' になる

制約

  •  1 \le N \le 10^{5}
  •  1 \le K \le 10^{9}

考えたこと

辞書順最小なものを求めるというのは、何を差し置いてもまず 0 文字目を最小にして、それが済んだら 1 文字目を最小にして...とすれば OK

とりあえず最後の 1 文字になるまでは

  • 0 文字目を 'a' にするのに必要な回数を t として、t が残り回数 K 以上だったら、0 文字目を 'a' にして K -= t とする
    • t が K 未満だったら、操作しない方が得なので何もせずに次の桁へ進む
  • 1 文字目を 'a' にするのに必要な回数を t として、t が残り回数 K 以上だったら、0 文字目を 'a' にして K -= t とする
    • t が K 未満だったら、操作しない方が得なので何もせずに次の桁へ進む
  • ...

というのを繰り返す。そうすると最後の桁になったときに、こうなったら K 回を全部消費する。なお、最後の桁以外で余分に操作をしておいた方が結局全体を小さくできる可能性がないかと気になるかもしれないが、最後の桁以外で余分に 26 回回したとしても結局結果は変わらない。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

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

    for (int i = 0; i < S.size(); ++i) {
        int con = ((int)('a' - S[i]) + 26) % 26;
        if (con <= K) {
            S[i] = 'a';
            K -= con;
        }

        if (i == (int)S.size()-1) {
            K %= 26;
            S.back() += K;
        }
    }
    cout << S << endl;
}