Skip to content

Instantly share code, notes, and snippets.

@FF256grhy

FF256grhy/yukicoder_241.txt

Created November 11, 2019 15:43
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save FF256grhy/f2ba81498a4c7e43957cec4dc647a786 to your computer and use it in GitHub Desktop.
Save FF256grhy/f2ba81498a4c7e43957cec4dc647a786 to your computer and use it in GitHub Desktop.
Download ZIP
yukicoder No. 241 解説
Raw
yukicoder_241.txt
yukicoder No. 241 解説
＊問題文
No.241 出席番号(1) - yukicoder
https://yukicoder.me/problems/no/241
O(N) で解けることに言及している人が見当たらなかったので一応書いておきます。
＊解法
生徒 i に番号 i を割り当てた場合に嫌いな数が割り当てられてしまう生徒をリストアップする。
・リストが空の場合　　　　　　：そのままでＯＫ
・リストのサイズが２以上の場合：リスト内で割り当てをローテーションすればＯＫ
・リストのサイズが１の場合　　：その生徒（＝番号）を x とおき、以下のように場合分けする
　　・番号 x が嫌いではない生徒が存在する場合：その生徒と番号を交換すればＯＫ
　　・全員が番号 x を嫌いな場合　　　　　　　：割り当ては不可能（x は生徒を表す数でもあるので、x < N であることに注意）
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment