hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング C匹のムカデがいる。 各ムカデはF本の足がある。 あるムカデには同じ色の靴下を履かせたい。N種類の靴下があり、それぞれ数がわかっている。 全て1つの瓶に入っていて、ランダムに取り出していく。 全てのムカデに同色の靴下を履かせるときに、取り出す靴下の最大数は？ 全部取り出しても履かせられないなら-1 解説 貪欲法で解く。 まず、F本に満たない種類の靴下は全て先に出しておこう。 F本以上の種類の靴下はF-1本取り出しておく。 これで、どのムカデも完成していない状態で最大数取り出せる本数を取り出した。 ここから、残っている本数が多い順に靴下を取っていく。 基本はF本一気に取り出すことで、1種類完成さ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2019%2F04%2F30%2F120554" title="CentipedeSocks [SRM757 Div1 Easy] - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2019-04-30 12:05:54 rich https://blog.hamayanhamayan.com/entry/2019/04/30/120554 1.0 100%