初めに
初稿です。見づらかったら申し訳ないです。
自分は競技プログラミング初心者で、今年の一月から始めました。なので、分からないところも沢山あります。
意見あればコメントよろしくお願いします。
そもそもこの解法自体が間違ってたらごめんなさい。本当に。ホンマに。その場合はなんかどうにかします。なんかこういう考え方いいよね～ぐらいに思ってください。
問題の概要
N人の生徒に対し、それぞれの生徒が嫌いな数字にならずに、0~N-1を一回ずつ割り振るとき、どのような割り振り方が存在するか一つ挙げよ。なければ-1を出力せよ。
自分の解法
N=1のとき、その生徒の嫌いな数字が0のとき、-1を出力し、それ以外は0を出力すれば良いので、Nが2以上の時を考えます。
まずリストに、何の数字が嫌いかと何番目の生徒(何番目に出力する生徒)かという二つの情報を一緒に記憶します。
次に、何の数字が嫌いかという部分でこのリストを昇順にソートします。次に、このリストに、その生徒に割り振る数字をN-1,N-2,...,1,0と順番に入れます。ここで、今割り振られた数字と生徒の嫌いな数字が被るのは高々一つのみです。もし、無ければ、そのまま生徒の順番に注意して出力しましょう。
下が何故高々一回かのイメージ図です。(N=8の時のとある例であり、●が生徒の嫌いな数字で、星がその生徒に割り振られた数字です。)(手書き&直撮りで見にくかったら申し訳ないです。)
もし、一回被ったときは次の操作を一回行えばよいです。
その割り振られた数字が嫌いな数字と被った生徒の割り振られた数字と、その被った生徒と嫌いな数字が異なる生徒いずれか一人の割り振られた数字を交換する。
ここで、被った生徒と嫌いな数字が異なる生徒がいない、言い換えれば、生徒の嫌いな数字が全て一致し、かつその数字が0以上N-1以下である場合、必ず誰かしらは、嫌いな数字と当たってしまうので-1を出力します。
それ以外は順番に注意して出力しましょう。
このコードでAC通りました。
私のコード下部の二つのwhile文は、被った生徒と嫌いな数字が異なる生徒を探すものです。ここは、全ての生徒について、調べればよいのでこれにこだわる必要はありません
計算量は最初のソートがネックとなりO(NlogN)で十分高速です。