JunKobayashi https://blog.hatena.ne.jp/JunKobayashi/ JunKobayashi's Diary https://junkobayashi.hatenablog.com/ ABCのF問題 ABC本番で敗北した問題 動的計画法 dpテーブルの次元を落とす ↓問題のページ↓ F - Diversity 動的計画法を利用するのだが、本番当時の自分ではまず見えてこない（しかし説明を受ければ理解できない要素は何一つない）手法を使う必要があったため、同様の問題に出くわした際にしっかり討伐できるよう本記事で固めておく。 まずは本問の解法の本筋を記す。問われているのは「最適となるように購入した時の満足度」のみであり、どの色の商品を購入したのかは全くもって不要な情報であるため、連想配列を使うなどして登場する商品を色で分類しておき、色\(i\)の商品が\(A_i\)個存在するものとし、それらの価格と効用を\((P_0, U_0), (P_1, U_1), \do… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fjunkobayashi.hatenablog.com%2Fentry%2F2024%2F12%2F10%2F222313" title="ABC383 F - Diversity - JunKobayashi&#39;s Diary" 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 2024-12-10 22:23:13 rich https://junkobayashi.hatenablog.com/entry/2024/12/10/222313 1.0 100%