AGC032A - Limited Insertion 解説

AGC二週連続でなんもわからんかったので腹いせのメモ

問題文

すぬけ君は空の数列  a を持っています。
すぬけ君は  a  に対して  N  回操作を行います。
 i 回目の操作では  { 1 } { \leq } { j } { \leq} { i } を満たす整数  j  を選び、 a  の先頭から  j  番目に  j  を挿入することができます。
長さ  N の数列  b  が与えられます。 a  回の操作後に  {a} b と一致することがあるかどうかを判定し、可能ならばそれを達成する操作手順の一例を示してください。
問題リンクhttps://atcoder.jp/contests/agc032/tasks/agc032_a

与えられる数列が構築可能か判定してください。構築できるならその手順を示してください。という問題。
 a に要素を追加して b にする操作」を一つの関数  f とみると、  a が入力されたときに  b が出力される関数  f を見つけてくださいという問題に言い換えられる。
じゃあこの 関数  f を探したい気持ちになるのだけど、そもそも存在するかわからないし実際に構築するのは難しそう。
難しそうなので他の方法を考えてみる。まず 関数  f がどんな関数なのか考えてみると、関数  f が存在するとき

  •  a というただ一つの入力に対して、 b というただ一つの出力が得られる

このことから

「値域  Y  の各元  y  に対して、 f  で  y  に写されるような定義域  X  の元  x  がちょうど一つ存在する」 https://ja.wikipedia.org/wiki/%E9%80%86%E5%86%99%E5%83%8F より

という条件を満たしており、関数  f 逆関数 がありそうなことがわかる。
ここで言う 関数  f 逆関数 とは数列  b を入力したときに数列  a が返ってくる関数のこと。これを 関数  f^{-1} と書く。
ここで関数  f^{-1} はどのようなものかを考えると 関数  f の逆なので、
 b から要素を削除して  a にする操作」だとわかる。つまり、

すぬけ君は数列  b  を持っています。 すぬけ君は  b に対して  N 回操作を行います。
 i  回目の操作では  { 1 } { \leq } { j } {\leq} {N}{-}{i}{+}{1} を満たす整数  j  を選び、 b  の先頭から  j  番目の  j  を削除することができます。
長さ  N の数列  b  が与えられます。 N  回の操作後に  b が空の数列  a   と一致することがあるかどうかを判定し、可能ならばそれを達成する操作手順の一例を示してください。

という問題を解けば、求めた操作の手順の逆が元の問題の答えになる。
この操作(関数  f^{-1} )を求めるのは実際にシミュレートすればいいだけなので元の問題の操作手順を求めるよりも簡単。
関数  f の存在を仮定して 関数  f^{-1} を求めてみる。 具体的には  1-indexd で

  •  1 . {b_j } {=} {j} となる  j の中で j が最も大きいものを削除する
  •  2 . 1 の操作を  b から要素が削除できなくなるまで繰り返す

 {1}, {2} の操作をすればいい。数列から要素を取り除けるならば N-i+1 は常に数列の長さと等しいので特に気にしなくていい 一番後ろにあるものを削除しなけばいけないのは、例えば
 {b}  :  {1}, {2}, {3}
という数列があったときに  1 を取り除いてしまうと
 {b}  :  {2}, {3}
となり、 2 をどうやっても取り除けなくなるから。
このように削除できるもので一番後ろ以外を削除してしまうと、空にできる数列であっても空にできなくなってしまう。
逆に  {1}, {2} の操作を繰り返しても数列  b を空にできないならば 関数  f^{-1} は存在せず、また関数  f も存在しない。
このシミュレートには  O(N^{2}) かかるので  O(N^{2}) でこの問題を解くことができた。

 a から  b を構築できますかという問題で、  b から  a を構築できますかという問題を考えるのは定石っぽい。

#include<iostream>
#include<list>
using namespace std;

int main(){
    int N;
    cin >> N;
    list<int> B;

    for(int i=0;i<N;i++){
        int b;
        cin >> b;
        B.emplace_back(b);
    }

    list<int> ans;

    while(!B.empty()){
        int idx = B.size();
        for(auto b = B.rbegin(); b != B.rend(); b++){
            if(*b == idx){
                ans.emplace_front(*b);
                B.erase(next(B.begin(),idx-1));
                break;
            }
            idx--;
        }
        if(idx == 0) break;
    }

    if(ans.size() != N) cout << -1 << endl;
    else{
        for(auto b : ans) cout << b << endl;
    }
}