D - Various Sushi (abc116_d)

Quiz

https://atcoder.jp/contests/abc116/tasks/abc116_d

Submit

https://atcoder.jp/contests/abc116/submissions/4062082

補足

• コンテスト中に頑張ったけれど解けなかった問題
• 落ちついてやってみると、コンテスト中よりシンプルなコードになった
  • 実装が長すぎる場合、方針を疑った方がいいかも

解き方

• 美味しさ順にソートして上からK個食べる
• この時、どのネタをいくつ食べたかをmapで保存しておく
• 食べた集合Sa
• 食べていない集合NotSa
• どちらも美味しさ順に並んでいるとする
• Saを1つ削り、NotSaから1つ持ってくる。持ってくるのは、ネタを増やす＆その中で1番美味しいもの
• サーチ方向
  • Saは後ろから
  • NotSaは前から
  • この順で見ていけば戻ることはない
  • O(N)
• priority queueは使わなかった。AC

Rainbow Fox 日本の食べ物寿司クッションぬいぐるみミニナップピロー (egg-sushi-pillow)