7K12 blog

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

F - Many Slimes

f:id:tkr987:20200204000145p:plain

https://atcoder.jp/contests/abc140/submissions/9876531

「第X世代のスライム数は第X-1世代までのスライム合計に等しい」ということに気づいたら、あとは貪欲にスライムを割り当てれば良さそうと判断することが大切(ここの証明は難しいので勘に頼るしかなさそう…><)。

なお、multisetは O(\log{N})と暗記すること。multiset.erase(値)だと値の要素が全て消えてしまうが、multiset.erase(it)だと*itの要素を1つだけ減らすことが出来るというSTLテクニックは学びになった。multiset.lower_boundするなりして検索した要素を1つ取り出して、ついでに取り出した要素を削除しておくという操作が O(log{N})で可能ということになる。multisetとかいうSTL便利すぎて草。 \log{N}は定数(脳死)。

f:id:tkr987:20200204003342p:plain

ただし、注意点が1つある。それは、第X世代の次の世代のスライムは「残りの集合の完璧な最大値でなくても良い」ということ。例えば、第3世代は3匹目の「7」が無理なので次の候補「5」で構築する。残ってしまった「7」は第4世代で第1世代に繋げることが可能。よって、構築はYesになる。ここはノーミスで気付くのは難しいかもしれない…。