AGC032A - Limited Insertion 解説
AGC二週連続でなんもわからんかったので腹いせのメモ
問題文
すぬけ君は空の数列 を持っています。
すぬけ君は に対して 回操作を行います。
回目の操作では を満たす整数 を選び、 の先頭から 番目に を挿入することができます。
長さ の数列 が与えられます。 回の操作後に が と一致することがあるかどうかを判定し、可能ならばそれを達成する操作手順の一例を示してください。
問題リンクhttps://atcoder.jp/contests/agc032/tasks/agc032_a
与えられる数列が構築可能か判定してください。構築できるならその手順を示してください。という問題。
「 に要素を追加して にする操作」を一つの関数 とみると、 が入力されたときに が出力される関数 を見つけてくださいという問題に言い換えられる。
じゃあこの 関数 を探したい気持ちになるのだけど、そもそも存在するかわからないし実際に構築するのは難しそう。
難しそうなので他の方法を考えてみる。まず 関数 がどんな関数なのか考えてみると、関数 が存在するとき
- というただ一つの入力に対して、 というただ一つの出力が得られる
このことから
「値域 の各元 に対して、 で に写されるような定義域 の元 がちょうど一つ存在する」 https://ja.wikipedia.org/wiki/%E9%80%86%E5%86%99%E5%83%8F より
という条件を満たしており、関数 の逆関数 がありそうなことがわかる。
ここで言う 関数 の逆関数 とは数列 を入力したときに数列 が返ってくる関数のこと。これを 関数 と書く。
ここで関数 はどのようなものかを考えると 関数 の逆なので、
「 から要素を削除して にする操作」だとわかる。つまり、
すぬけ君は数列 を持っています。 すぬけ君は に対して 回操作を行います。
回目の操作では を満たす整数 を選び、 の先頭から 番目の を削除することができます。
長さ の数列 が与えられます。 回の操作後に が空の数列 と一致することがあるかどうかを判定し、可能ならばそれを達成する操作手順の一例を示してください。
という問題を解けば、求めた操作の手順の逆が元の問題の答えになる。
この操作(関数 )を求めるのは実際にシミュレートすればいいだけなので元の問題の操作手順を求めるよりも簡単。
関数 の存在を仮定して 関数 を求めてみる。
具体的には -indexd で
- .となる の中で が最も大きいものを削除する
- . の操作を から要素が削除できなくなるまで繰り返す
の操作をすればいい。数列から要素を取り除けるならば は常に数列の長さと等しいので特に気にしなくていい
一番後ろにあるものを削除しなけばいけないのは、例えば
という数列があったときに を取り除いてしまうと
となり、 をどうやっても取り除けなくなるから。
このように削除できるもので一番後ろ以外を削除してしまうと、空にできる数列であっても空にできなくなってしまう。
逆に の操作を繰り返しても数列 を空にできないならば 関数 は存在せず、また関数 も存在しない。
このシミュレートには かかるので でこの問題を解くことができた。
から を構築できますかという問題で、 から を構築できますかという問題を考えるのは定石っぽい。
#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; } }