競技プログラミング用 知識集積所
ABC425B - Find Permutation 2
最終更新：
sport_programming
-
view
問題
必要知識
A問題レベルのものは省略
別解の場合
考え方
Aの中の-1を好きな数に書き換えて、1からNまでが1回ずつ登場する数列にできればよい。
これは、人間が自分でやるならどうするか考えて、それをそのままコードに落とし込めばよい。
つまり、以下の方法で4回forループを回せばよい。
（その際、記録に必要なvectorは適宜用意する）
これは、人間が自分でやるならどうするか考えて、それをそのままコードに落とし込めばよい。
つまり、以下の方法で4回forループを回せばよい。
（その際、記録に必要なvectorは適宜用意する）
まず1回目。
数列を全部見て、-1がどこにあるか、-1以外の数は何が何回登場するかカウントする。
数列を全部見て、-1がどこにあるか、-1以外の数は何が何回登場するかカウントする。
2回目。
カウントの一覧を見て、一度も登場していない数を調べる。
カウントの一覧を見て、一度も登場していない数を調べる。
3回目。
Aの中の-1の位置の記録を見て、一度も登場していない数でAのその位置を埋めていく。
これは、-1を見つけるたびに好き勝手に入れる数を決めていく貪欲法※で問題ない。
その際、埋めるのに使った数について、登場回数を更新しておく。
元々入っている数にダブりがあった場合は未使用の数が余るが、特にコード上問題にならないので気にしなくてよい。
Aの中の-1の位置の記録を見て、一度も登場していない数でAのその位置を埋めていく。
これは、-1を見つけるたびに好き勝手に入れる数を決めていく貪欲法※で問題ない。
その際、埋めるのに使った数について、登場回数を更新しておく。
元々入っている数にダブりがあった場合は未使用の数が余るが、特にコード上問題にならないので気にしなくてよい。
4回目。
各数の登場回数の記録を見て、全てが1回ずつ登場しているか確認する。
各数の登場回数の記録を見て、全てが1回ずつ登場しているか確認する。
4回目のforループで問題なければ、"Yes"を出力してAの中身を出力する。
問題があれば、"No"を出力する。
問題があれば、"No"を出力する。
解答例
注意点
別解
順列全探索※を用いてもよい。
つまり、1からNまでの順列を全パターン用意して、1つ1つ条件を満たすか確認してもよい。
計算量がO(N*N!)になるので、N=10なら間に合うが、N=11でギリギリ、N=12はもう無理。
しかし、B問題なのでこの解法でも間に合う制約にしてくれてある。
解答例
つまり、1からNまでの順列を全パターン用意して、1つ1つ条件を満たすか確認してもよい。
計算量がO(N*N!)になるので、N=10なら間に合うが、N=11でギリギリ、N=12はもう無理。
しかし、B問題なのでこの解法でも間に合う制約にしてくれてある。
解答例
