脳log[20230815]

2023年08月15日 (火) [AtCoder] 精進。ABC140-F「Many Slimes」(黄 diff)。問題はシンプルに見える。自身未満の体力のスライムしか生み出せないのだからできるだけ大きい体力のスライムからスタートして、できるだけ大きい体力のスライムを生み出すのが最善。■提出 #44614623 (WA×22)。S をソートして前から 2^k 個の要素が次の 2^k 個の要素より大きいことを k=0..N-1 について確認すればいいかと思ったが違った。多少の融通がきくようだ。■提出 #44621584 (AC / 1076 Byte / 1108 ms)。待ち行列を２本持つことでプライオリティキューを使わないでもいいかなとか考えてダメで、プライオリティキューでやろうとしてダメで、BIT でやった。難しい問題ではなかったはずだが回り道が多かった。■もっと短くてオーダーの優れた賢い解法があるらしい。たぶん最初に最大の要素に N 個の要素を生み出させて、その次の世代に N-1 個の要素を生み出させてとやるのかなと思ったけど、これも単純に前から貪欲にやるわけにはいかないみたい。たとえば最大の要素にはできるだけ大きな要素を生み出してほしいけど、N 番目に生み出された要素が次の世代を生み出すことはないので。