SRM695 div1 easy BearPasswordLexic

考えたこと

• 辞書順最小と言われたので'a'を置けるなら置くみたいなのを書きたくなる
• 連続している'a'が多すぎて与えられた条件を満たせないときは'b'を置くしか無い
• {6,3,0,0,0,0} とかが与えられると "aabbaa" をつくれるけど上の規則だけだと "aabaab" ができてだめ
• 後ろの方を見たときに足りなくなるようなことがあったらそのときも'a'を置けない
• 足りなくなるのはどんなときか？
• 辞書順最小を無視して条件を満たせるように最適な並べ方をしても足りなければ'a'を置いちゃだめな気がする
• 条件を満たしていれば前のと同じものを置くを繰り返すと最適になる気がした
• あと最終的にできた文字列が条件を満たしてなければ構成が不可能そうなので-1
• sampleが通ったので出すと落ちた
• 後ろの方について最適な並べ方をするパートが境界とかいろいろ複雑でかなり実装が怪しい
• いくらやっても手元でさらにつくったケースを通せないので諦める
  -----解説を見た-----
• x[i] >= 0 を満たす最大のiを探す
• i文字連続する部分列が絶対に必要
• i文字連続するのをつくるとx[0],…,x[i-1]も自然にできる
• 自然にできた分でxが足りなくなったら-1
• -1でない場合v[i]文字連続する部分列の集合みたいになる
• aaaaabbbaaaabb みたいに交互にa,bを並べる

実装が怪しかったら方針転換をすることをいい加減覚えて

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

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

    VI v;
    int idx = n-1;
    while(idx >= 0) {
      while(idx > 0 && x[idx] == 0) idx--;
      if(x[idx] == 0) break;
      v.PB(idx);
      int cnt = 1;
      for(int i=idx; i>=0; --i) {
        x[i] -= cnt++;
        if(x[i] < 0) return "";
      }
    }

    sort(ALL(v));

    int l=0, r=v.size()-1;
    bool turn = true;
    string ans = "";
    while(l<=r) {
      if(turn) ans += string(v[r--]+1, 'a');
      else ans += string(v[l++]+1, 'b');
      turn = !turn;
    }

    if(ans.size() != n) return {};
    return ans;
  }
};