AtCoder Grand Contest 032 A

atcoder.jp

問題文

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

制約

• 入力はすべて整数である。
• 
• 

出力

N回の操作後に a と b が一致するような操作手順が存在しないならば "-1" を出力せよ。存在するならば操作手順をN行に出力せよ。i行目ではi回目の操作で選んだ整数を出力せよ。考えられる操作手順が複数存在する場合は、そのうちのどれを出力してもよい。

解法

作成可能な数列Cがあるとする。その数列Cから1つずつ数字を取り除き、最終的に空の数列にすることができればよい。取り除くことができるのは (one based indexing)となる要素だけである。今、このような要素がの3つあるとする ( ) 。以外を取り除いた場合、 となるような状態(を取り除くことが出来る状態)が起こりえないのは明らかである。つまり、を満たすもののうち最もの大きいものを取り除く操作を数列が空になるまで行い、その操作を逆順に出力することで、答えを得ることが出来る。これはである。

C++で実装

#include <iostream>
#include <vector>
using namespace std;
#define MAX_N 100

bool is_ans = true;
int N;
vector<int> b;
vector<int> ans;

void read()
{
    int tmp;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> tmp;
        b.push_back(tmp);
    }
    return;
};
void solve()
{
    while (true)
    {
        is_ans = false;
        for (int i = b.size() - 1; i >= 0; i--)
        {
            if (b[i] == i + 1)
            {
                ans.push_back(i + 1);
                b.erase(b.begin() + i);
                is_ans = true;
                break;
            }
        }
        if (b.empty() == true)
        {
            is_ans = true;
            return;
        }
        if (b.empty() == false && is_ans == false)
        {
            return;
        }
    }
};
void print_ans()
{
    if (is_ans == true)
    {
        for (auto i = ans.rbegin(); i != ans.rend(); i++)
        {
            cout << *i << endl;
        }
    }
    else
    {
        cout << -1 << endl;
    }
}
int main()
{
    read();
    solve();
    print_ans();
    return 0;
}