<h2>問題</h2>
問題はこちら。
<a href="https://atcoder.jp/contests/abc246/tasks/abc246_c" target="_blank" rel="nofollow noopener noreferrer">AtCoder Beginner Contest 246 C</a>
<h2>考えたこと</h2>
「高橋君がすべての商品を買うために支払う合計金額の最小値」は「クーポンが最大限有効に使われたときに支払う金額」であるので「クーポンを最大限有効に使う方法」を考えた。
クーポンが適用されたとき値引きされる最大値は<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>X</mi></mrow><annotation encoding="application/x-tex">X</annotation></semantics></math>X円であるから毎回のクーポンの適用でできる限り<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>X</mi></mrow><annotation encoding="application/x-tex">X</annotation></semantics></math>X円値引きされるようにクーポンを使いたい。逆にクーポンを適用しても<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>X</mi></mrow><annotation encoding="application/x-tex">X</annotation></semantics></math>X円より小さな値引きになる場合を考えると、それはクーポンを適用する商品の値段が<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>X</mi></mrow><annotation encoding="application/x-tex">X</annotation></semantics></math>X円より小さな場合である。この場合の値引き額は<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>X</mi></mrow><annotation encoding="application/x-tex">X</annotation></semantics></math>X円より小さく、その商品の値段ちょうど分引かれることになりその商品の値段は<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0</mn></mrow><annotation encoding="application/x-tex">0</annotation></semantics></math>0円となる。
最大限クーポンの額だけ値引きされる場合を「無駄にならない場合」と呼び、クーポンの額を無駄にしてしまう場合を「無駄になる場合」と呼ぶことにする。
答えを導くには
<ol>
<li>まず「無駄にならない場合」のクーポンの適用を最大回数行う。</li>
<li>1で残ったクーポンを商品に適用するときは「無駄になる場合」の適用となる。「無駄になる場合」の適用でも無駄を小さくするために値段が大きな商品から順に適用する。</li>
<li>クーポン適用後の商品の値段を合計する。とよいと考えられる。</li>
</ol>
<h2>実装する</h2>
<pre><code class="language-ts">import * as fs from &#x27;fs&#x27;;

const main = (stdin: string): void =&gt; {
 // 入力の受け取り。
 const [_a, _b] = stdin.split(&#x27;\n&#x27;);
 let [N, K, X] = _a.split(&#x27; &#x27;).map(x =&gt; BigInt(x));
 const A = _b.split(&#x27; &#x27;).map(x =&gt; BigInt(x));
 
 
 const a = [];
 for (let i = 0; i &lt; N; i++) {
 // Qはクーポンを無駄にせず適用できる最大回数
 const Q = A[i] / X;
 if (Q &lt;= K) {
 a.push(A[i] - Q * X);
 K -= Q;
 } else {
 // クーポンが足りずK回までしか適用できない場合
 a.push(A[i] - K * X);
 K -= K;
 }
 };


 const ans = a.sort((a, b) =&gt; a &lt; b ? 1 : -1)
 // ソートして前から順にK枚のクーポンを適用していくが適用された商品の
 // 値段は0になるのでKより前の要素は切り捨ててから合計する
 .slice(Number(K)) 
 .reduce((a, b) =&gt; a + b, 0n)

 console.log(Number(ans)); 
};

main(fs.readFileSync(&#x27;/dev/stdin&#x27;, &#x27;utf-8&#x27;));
</code></pre>
<h2>まとめ</h2>
まず初めに一枚のクーポンの額面を全額値引きできる場合の最大となる値引きの仕方を考えることがポイントだと思う。「条件が変わるギリギリの操作をして後で少し調整することで最適化するパターン」

AtCoder Beginner Contest 246 C問題を解く