SRM695 Div1 Easy "BearPasswordLexic"

問題

TopCoder Statistics - Problem Statement

解法

最終的に使用するconstantの長さとその数について、実は一意に定まる。
以下を見て欲しい。

constantの長さ | 1  2  3  4
数             | 11 8  5  2
↓
constants 4 を1回使うと残るのは
↓
constantの長さ | 1  2  3  4
数             | 7  5  3  1
↓
constants 4 をもう1回使うと残るのは
↓
constantの長さ | 1  2  3  4
数             | 3  2  1  0
↓
constants 3 を1回使うと残るのは
↓
constantの長さ | 1  2  3  4
数             | 0  0  0  0

ってことは、
constant 4 を 2回
constant 3 を 1回
使うんだね！☆（ゝω・）vｷｬﾋﾟ

で、辞書順に最小にしなければならないので、まず a を使うべきであろう。
そして、aを使う時はconstantの長さが長いほど良いので、最大のものを使うようにする。
次は b を使わなければならない。
そして、bを使う時はconstantの長さが短いほど良いので、最小のものを使うようにする。

constant 4 を 2回
constant 3 を 1回

だと、答えは"aaaabbbaaaa"となる。

ソースコード

class BearPasswordLexic {
    public:
    string findPassword(vector<int> x) {
        int n = x.size();

        // ここで、ｘ[0]=nでなければ失敗
        if (x[0] != n) return "";

        // 使用するconstantとその数を計算する
        int constants[55];
        memset(constants, 0, sizeof(constants));
        for (int k = 0; k < n; k++) {
            for (int i = n - 1; i >= 0; i--) {
                if (x[i] != 0) {
                    constants[i]++;
                    for (int j = i; j >= 0; j--) {
                        x[j] -= i - j + 1;
                    }
                    break;
                }
            }
        }

        // ここで、全て0になっていなければ失敗
        for (int i = 0; i < n; i++) {
            if (x[i] != 0) return "";
        }

        // aからスタート
        string answer = "";
        bool curA = true;
        while (true) {
              if (curA) {
                  // aだったら一番大きいconstantを使用する
                  int id = -1;
                  for (int i = n - 1; i >= 0; i--) {
                      if (constants[i] != 0) {
                          id = i;
                          constants[i]--;
                          break;
                      }
                  }
                  if (id == -1) return answer;
                  for (int i = 0; i <= id; i++) {
                      answer += "a";
                  }
              } else {
                  // bだったら一番小さいconstantを使用する
                  int id = -1;
                  for (int i = 0; i < n; i++) {
                      if (constants[i] != 0) {
                          id = i;
                          constants[i]--;
                          break;
                      }
                  }
                  if (id == -1) return answer;
                  for (int i = 0; i <= id; i++) {
                      answer += "b";
                  }
              }
              // ab入れ替え
              curA = !curA;
        }
    }
};