好き!!!!!でも A 問題としてはかなり難しいね。
問題概要
数列 が空の状態から出発して以下の操作を
回行った結果が数列
と一致するようにできるかどうか判定せよ。
回目の操作においては
以上
以下の整数
を一つ選んで、数列の
番目に
を挿入する
制約
考えたこと
面白そう!!!
とりあえず様子を観察してみる。
操作を (1, 1, 3, 2) とすると
(1) (1, 1) (1, 1, 3) (1, 2, 1, 3)
という風になる。ここで最終状態を見ると、
- 最後に挿入されたのは 1 (1 番目に挿入) か、2 (2 番目に挿入) かのいずれか
であることは直ちにわかる。 が操作された直後には、
となっているからだ。さらに言うと、もしここで (1, 2, 1, 3) に対して直前に操作されたのが
だったと仮定すると前回は
- (2, 1, 3)
ということになってしまう。この「先頭の 2」はどう頑張っても決して実現できない。一般に
>
となることは絶対にありえない
ということに注意する。 が挿入された時点ではそれは
番目にあって、その後
番目へと移動していく。
そのことを考えると、
(1, 1, 2, 4, 3, 6, 3, 2, 9, 4)
のような数列では
が直前の操作の候補であるが、9 以外に操作された可能性はありえない。なぜなら、例えば 4 に操作していたとすると直前には
ということになってしまう。これらは決して実現できない。
以上から、
数列
が与えられたときに、直前の操作は一意に復元できる
それは
となる最大の
である
ということがわかった。あとは操作を巻き戻しながら、途中で詰まったら「不可能」と判定すればよい。
#include <iostream> #include <vector> using namespace std; int N; vector<int> a; void solve() { vector<int> res; for (int i = 0; i < N; ++i) { int pivot = -1; for (int j = (int)a.size()-1; j >= 0; --j) { if (a[j] == j) { pivot = j; break; } } if (pivot == -1) { cout << -1 << endl; return; } res.push_back(pivot + 1); a.erase(a.begin() + pivot); } reverse(res.begin(), res.end()); for (auto v : res) cout << v << endl; } int main() { cin >> N; a.resize(N); for (int i = 0; i < N; ++i) cin >> a[i] , --a[i]; solve(); }