phyllo_algo https://blog.hatena.ne.jp/phyllo_algo/ れどこだ目指すよ！　(；`・ω・） https://phyllo-algo.hatenadiary.org/ その他 問題 無限に長い一直線上に箱が並んでおり、-100のところに赤玉がR個、0のところに緑玉がG個、100のところに青玉がB個ある。 1回の操作で、一つの玉を左右どちらかに移すことができるが、同じ箱に違う色の玉をいれる状態を作ってはいけない。 すべての箱に玉が1つ以下の状態にするまでの最小操作回数を答える。 考え方 greedyにやろうと考えると、Gが300個の時、どちらにはみ出した方がよいか？を考えないといけない。 (RかBの少ないほうに寄せた方がよい) 効率的に計算するには、動的計画法が使える。 まず、同じ色の玉を隙間をあけず、伸ばすように広げた場合が最適だとわかる。 また、R,G,Bは広がっ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fphyllo-algo.hatenadiary.org%2Fentry%2F20150203%2F1422981117" title="ABC#004 D.マーブル - れどこだ目指すよ！　(；`・ω・）" 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 2015-02-03 01:31:57 rich https://phyllo-algo.hatenadiary.org/entry/20150203/1422981117 1.0 100%