🐥

AGC 032 | A - Limited Insertion

2020/11/19に公開

競プロ

tech

問題

考えたこと

空の数列の状態から可能性を考慮していくと以下のよに組み合わせが爆発する。

以下のように完成形から取り除くことを考える。

j番目にjを入れるのでとある数列から1つ前の状態を作ろうと思ったら、j番目のjしか取り除けない。さらに一番右以外のjを取り除くと取り除いたjより右にある数字が二度と取り除けなくなるので一番右のjを取り除く必要がある。

コード

実装Tips

配列 $a$ のi番目の要素はa.erase(a.begin() + i);で取り除ける

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll n;
  cin >> n;
  vector<ll> b(n);
  for (int i = 0; i < n; i++) {
    cin >> b[i];
  }
  vector<int> ans;
  for (int i = n; i >= 1; i--) {
    bool found = false;
    for (int j = i; j >= 1; j--) {
      if (b[j - 1] == j) {
        ans.insert(ans.begin(), j);
        b.erase(b.begin() + (j - 1));
        found = true;
        break;
      }
    }
    if (!found) {
      cout << -1 << endl;
      return 0;
    }
  }
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i] << endl;
  }
}

学んだこと

順番に考えて組み合わせが爆発するなら逆順に考える。

AGC 032 | A - Limited Insertion

問題

考えたこと

コード

学んだこと

参考

Discussion