SRM 695 BearPasswordLexic

問題の勘違いはな。

問題

TopCoder Statistics - Problem Statement

以下の条件を満たす文字列を求めよ。ただし, 解が複数ある場合は辞書順最小のものを求めよ。

• 文字列の長さは N
• 文字列は 'a', 'b' のみで構成される
• 配列 x が与えられる。長さ i+1 の部分文字列で,「 同じ文字が i+1 回連続で続く」というもの(constant と呼ぶ)がちょうど x[i] 個ある。

解法

配列 x のインデックスが大きいものから考えると, 「長さ i+1 の constant があれば 長さ j+1 の constant は i-j+1 個ある(j <= i)」 が成り立つので, それぞれの長さの constant の個数を一意に定めることができます。

後は辞書順最小にするパートです。明らかに答えは 'a' の constant と 'b' の constant が交互に並んだような形になります。これはなるべく前半に多く 'a' を入れて なるべく少ない 'b' を入れておくのが良いです。

class BearPasswordLexic {
public:
    string findPassword(vector <int> x) {
        int N = x.size();
        if (x[0] != N) return "";
        vector<int> cnt;
        for (int i = N-1; i >= 0; i--) {
            if (x[i]) {
                for (int j = 0; j < x[i]; j++) {
                    cnt.push_back(i+1);
                }
                for (int j = 0; j <= i; j++) {
                    x[j] -= (i-j+1) * x[i];
                    if (x[j] < 0) return "";
                }
            }
        }
        int l = 0, r = cnt.size()-1;
        int now = 0;
        string ans;
        while (l <= r) {
            if (!now) {
                for (int i = 0; i < cnt[l]; i++) {
                    ans += 'a';
                }
                l++;
            } else {
                for (int i = 0; i < cnt[r]; i++) {
                    ans += 'b';
                }
                r--;
            }
            now ^= 1;
        }
        return ans;
    }
};

あ, "return the lexicographically smallest of them" だったのか(勝手に "return the any of them" にしてた)

— マヨ子@大天使クサハエル (@mayoko_) 2016年7月19日

仕方ないね(白目)