7K12 blog

猫でも分かるアルゴリズム解説

AGC018 B - Sports Festival

f:id:tkr987:20210627015720p:plain
https://atcoder.jp/contests/agc018/submissions/23809861

  • 最大の状態から減らすには何を減らせばよいか考える
  • 最大の状態から始めて小さくするには「最大の要素を取り除くしかない」という貪欲
  • 数字を変化させるには「少なくとも貪欲するしかない」なら貪欲が想定解となることが多い
  • 最左が採用されるので最左のスポーツだけ見て操作していけば良いと考察できる

f:id:tkr987:20210627022145p:plain
仮に全てのスポーツを採用した場合、これは答えとしては最大になる。図のような入力があったとき全てのスポーツを採用するとans=3となるが、そこからans=2にするには少なくともスポーツ2を削除する必要がある。スポーツ2を削除するとスポーツ5が3人いてans=3なので更にスポーツ5も削除してみる。このように、現状態で(最左のスポーツの中で)最も多いスポーツを削除するという操作を誰かのスポーツ候補がなくなるまで続けていったときの最小値が答えとなる。

感想: 全く気づかなかったが、言われてみれば「それをするしかない」ので、そういうときは迷わず自信を持つのが大事そう