# ABC288 E Wish List 解説

本記事では、Toyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288）のE問題(500点)"[Wish List](https://atcoder.jp/contests/abc288/tasks/abc288_e)"の自分の思考の過程について説明します。
本記事の方向性については[初回記事](https://hackmd.io/@carrot46/r1kru7Z6s)を参照してください。

目次
- [問題概要](#問題概要)
- [最初に考えたこと](#最初に考えたこと)
- [$X$以外の商品を買う例はあるか？](#span-idMathJax-Element-319-Frame-classmjx-chtml-MathJax_CHTML-tabindex0-stylefont-size-113-position-relative-data-mathmlX-rolepresentationXXX以外の商品を買う例はあるか？)
- [買う順番に依存するか？](#買う順番に依存するか？)
- [$C_j$が最小となる$j$を固定して考える](#span-idMathJax-Element-347-Frame-classmjx-chtml-MathJax_CHTML-tabindex0-stylefont-size-113-position-relative-data-mathmlCj-rolepresentationCjCjC_jが最小となるspan-idMathJax-Element-348-Frame-classmjx-chtml-MathJax_CHTML-tabindex0-stylefont-size-113-position-relative-data-mathmlj-rolepresentationjjjを固定して考える)
- [選べる$C_j$の条件](#選べるspan-idMathJax-Element-360-Frame-classmjx-chtml-MathJax_CHTML-tabindex0-stylefont-size-113-position-relative-data-mathmlCj-rolepresentationCjCjC_jの条件)
- [思考の過程のまとめ](#思考の過程のまとめ)

## 問題概要

$N$ 個の商品について、買う場合の定価 $A_i$ 円と、必ず買わなければならない商品の集合 $X$ が与えられる。
現在売れ残っている商品のうち番号が $j$ 番目に小さい商品を買う場合、定価に加えて $C_j$ 円払う。
$X$を買うための合計費用の最小値を求めよ。

制約 : $1 \leq N \leq 5000, \, 1 \leq A_i, C_i \leq 10^9$

## 最初に考えたこと

この段階でアルゴリズムはあまり意識せず[^aim]、今回のように「様々な操作が考えられる中で最小値は何か？」というタイプの問題では、**操作の本質を見抜く**ことを最優先に行っています。
つまり、操作の性質について整理していけば、最終的に解ける形になるのではないか、という考え方です。

[^aim]: 実際のコンテスト中は、多分$O(N^2)$のDPだろうと推測していましたが、DPを意識した考察は行なわずに操作の性質について考察しました
<!--
[^目標]: [公式解説](https://atcoder.jp/contests/abc288/editorial/5659)における式(1),(2)のような形を得ることが目標となる
-->

今回は、**操作が複雑となる可能性**を考えて、その**理由を特定**することから始めました。
コンテストでは、問題文やサンプルを読んでいる最中に気になった次の2点について考えました。

### $X$以外の商品を買う例はあるか？

元の問題文の末尾には、次の一文があります。

> なお、高橋君は欲しい商品ではない商品を購入することもできます。

ここで、$X$以外の商品を買う場合があるのか？それはどんな場合か？という疑問が生じます。
この際に重要なのは、「なぜ$X$以外の商品を買うのか」という**理由を特定する**ことです。

$X$以外の商品を買う例は入力例1にありますが、ここではより単純な例として、「$C_1$が他の$C_j$と比べて非常に小さく、$X$に1が含まれない」場合を考えます。
もし商品1を買わないならば、操作の性質から$C_1$は絶対に使われない[^操作の性質]ため、$C_j$ ($=C_1$より非常に大きい) を払わなければなりません。
それならば、商品1を買ってでも$C_1$を活用した方が良いです。

[^操作の性質]: 商品1が売れ残っているので、必ず$j\geq 2$になる

この例を通して理由を考察すると、次のようになります。

- $X$以外の商品も買うことで、ある商品を買う際に使える$C_j$の種類が増える場合がある

### 買う順番に依存するか？

どの要素を買うかだけでなく、商品を買う順番にも自由度があり、合計費用に影響を及ぼすことがあります。
例えば、$C_1$が各$A_i$や他の$C_j$と比べて非常に小さい場合を考えると、商品を1から**昇順に**買うのが最適です。
一方で、$C_1$が一番大きく、$C_2, C_3, \dots$と段々小さくなる場合では、商品を$N$から**降順に**買うのが最適です。
また、$C_2$が一番小さい場合は、商品1を取っておいて、商品$2, 3, \dots$と買うことも考えられます。

これらの例から、買う順番も考えなければならない理由は次のようになります。

- 買う順序を選べば、費用に加算される$C_j$をある程度選べる

以上をまとめると、「**$X$以外の商品**を買い、**買う順序**を選ぶと、**値の小さい$C_j$を多く使えて**お得になりうる」ということになります。
以降ではこの性質について、より厳密に理解していきます。

## $C_j$が最小となる$j$を固定して考える

先ほど、複雑な操作を考えることで、より値の小さい$C_j$を使える場合があることを確認しました。
ここで値の小さい$C_j$とありますが、可能ならば最小の$C_j$を選びたいです。
具体的な例として、**$C_3$ が最小**ならばどうなるか考えます[^最小]。

[^最小]: $C_1$や$C_N$が最小だと特殊な例となりかねないので避ける

商品1や商品2は、どのような状況でも番号が1番目または2番目に小さいため、$C_3$円加算で買うことは不可能です。
商品3は、最初の操作で買うことで$C_3$円加算で買えます。

では、商品番号が4以上の場合はどうでしょうか。
この場合、**自身より番号が小さい商品の内、最終的に買わないものが2個以下**$\cdots(*)$ならば、$C_3$円加算で買えることが分かります。
具体的には、自身より番号が小さいものがちょうど2つ売れ残っているタイミングで商品を買えば良いです。

ここまでの考察は1つの商品のみに注目した考察ですが、$(*)$の条件を満たすものが**複数ある場合に全て$C_3$円加算で買えるか**、という点も確認します。
すると、$C_3$ 円加算できる商品が複数ある場合は、番号の小さいものから昇順に買えば、全て$C_3$円加算で買えることが分かります。

## 選べる$C_j$の条件

$C$の中で$C_3$が最小の場合、$(*)$の条件を満たす番号が4以上の全ての商品は、$C_3$円加算で買えることが分かりました。
この条件の考え方を基に、商品番号 $i$ を買う時に扱える$C_j$について考え直すと、次のように言い換えることができます。

- 商品 $i$ を買う場合、**最終的に買わない番号 $i$ 未満の商品が $k$ 個**ならば、$C_{k + 1}, C_{k + 2}, \dots, C_i$ から1つ選んで加算した金額で購入できる。つまり、$A_i + \min(C_{k + 1}, C_{k + 2}, \dots, C_i)$ 円で買える。

(2023/02/10 0:30追記　言い換えの際、次のように「買いたいタイミングが同時に来る」ケースも考慮する必要があります :
$X=(1, 3), A=(1, 10^9, 1), C=(1, 10^9, 1)$ の時、商品1, 3いずれも初期状態の時点で買わなければなりません。このような場合は、番号が大きいものから降順に購入すればよいです。)

したがって、商品 $i$ を買う場合の値段は、**最終的に買わない番号 $i$ 未満の商品の個数**のみ(高々$N$通り)によって決まります。

ここまで性質を整理すれば、後は解くアルゴリズムを考えるだけです[^整理後]。
商品1から順番に買うか買わないかを決める動的計画法で、最終的に買わない商品の個数を現在の状態として持てば、[公式解説](https://atcoder.jp/contests/abc288/editorial/5659)にあるように$O(N^2)$時間で解くことができます。
動的計画法の構築については公式解説にもあるため省略します。

[^整理後]: だけと言っていますが、当然慣れるまでは難しいです

## 思考の過程のまとめ

最初に考えていたように、合計費用を最小とするために、$X$以外の購入や購入順序など、複雑な操作を考えなければならない問題でした。
しかしながら、**複雑な操作を考えなければならない理由**を考えると、選べる$C_j$の自由度が問題であると分かります。
そこで、選ぶ$C_j$として明らかに最適であるものとして、**$C_j$ が最小となる $j$ を固定**して考えたところ、自身より番号が小さい商品のうち最終的に買わないものの個数が重要であるという**操作の性質**が見えました。
その操作の性質に基づくと、複雑な操作でありながら実は各商品について**高々$N$通り**のパターンだけ考えればよいことが分かり、動的計画法で解くことが出来ます。

今回は、「様々な操作が考えられる中で最適値はどうなるか」という問題で、私が考えたことを説明しました。
今回のように単純な例から考えを広げる方法は、考察を進めるだけでなく、問題設定に慣れることや、誤読の防止(気付き)にもつながるため、とても重要だと考えています。
本記事がABCの400-600点問題で詰まっている人の参考になれば幸いです。