tags: HUPC2021

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))