###### tags: `HUPC2021`

# [A: サイコロつっつき](https://onlinejudge.u-aizu.ac.jp/beta/room.html#HUPC2021Day2/problems/A) 解説
###### 原案: `ngng628` | 解説: `ngng628`

貪欲法を考えましょう。

出目が $1$ のサイコロは $1$ 度のつっつきで出目を最大で $5$ にすることができます。出目が $2,3,4,5$ のサイコロは $1$ 度のつっつきで出目を最大で $6$ にすることができます。出目が $6$ のサイコロはこれ以上出目を大きくすることができません。

よって、次の方針で操作を行うのが最適です。

- 操作回数が $K$ を超えるまたは全てのサイコロの出目が $6$ になるまで、出目が小さいサイコロから順に次の操作を繰り返す。
- 出目が $1$ なら、出目を $5$ にする。
- 出目が $2,3,4,5$ なら、出目を $6$ にする。

具体的な実装方法は様々ですが、出目が $1$ のサイコロは、出目を $5$ にした後、操作ができるならもう一度つっついて $6$ にすることを忘れないように注意してください。

実装例1 (C++):

// 優先度付きキューによる実装
# include <bits/stdc++.h>
using namespace std;
using MinHeap = priority_queue<int, vector<int>, greater<int>>;

int main() {
   // 1. 入力
   int N, K;
   cin >> N >> K;
   MinHeap heap;
   for (int _i = 0; _i < N; ++_i) {
      int a;
      cin >> a;
      heap.push(a);
   }

   // 2. 操作を行う
   for (int _i = 0; _i < K; ++_i) {
      int a = heap.top();
      heap.pop();
      if (a == 1) heap.push(5);
      else heap.push(6);
   }

   // 3. 総和を求める
   int ans = 0;
   for (int _i = 0; _i < N; ++_i) {
      ans += heap.top();
      heap.pop();
   }

   // 4. 答えの出力
   cout << ans << '\n';
}

実装例2 (Python)

# 線形な探索による実装
# 1. 入力
n, k = map(int, input().split())
a = list(map(int, input().split()))

# 2. 操作を行う
cnt = 0
for d in range(1, 6):
   for i in range(n):
      if a[i] == d and cnt < k:
         a[i] = 5 if d == 1 else 6
         cnt += 1

# 3. 答えの出力
print(sum(a))

<!--
この方針の正当性を確かめましょう。

サイコロの出目は $6$ 以上にはできません。$1$ 回の操作で増加させることができる量は $4$ 以下です。

サイコロの出目は $6$ 以上にはできません。また、どの出目についても操作後の出目の大きさの増加量を $4$ 以上にすることはできません。
|出目|次の出目|最大の増加量|
|:--:|:---:|:----:|
|1|5|4|
|2|6|4|
|3|6|3|
|4|6|2|
|5|6|1|
|6|6|0|

|出目|次の出目|増加量|
|:--:|:---:|:----:|
|1|3|2|
|2|6|4|
|3|10000000|9999997|
|6|6|0|
|10000000|10000000|0|

さて、$K = 1$ のとき貪欲法が正しいことは明らかです。$K=n$ のときも貪欲法が正しいことを仮定します。$K=n+1$ のとき、 -->