AtCoder が提供しているABC（AtCoder Beginner Contest）277 のD問題をC++とPythonで解いてみました。ABC277は、2022年11月12日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Takahashi’s Solitaire（Difficulty : 873）
問題はリンク先をご覧ください。
ABC277 D問題 Takahashi’s Solitaire
連想配列を使ってカードの数字を記憶して、まとめて処理をします。AtCoder Problems による Difficulty は、873 でした。
解答案
入力例1の場合を考えます。カードに書かれている整数は0から6になります。
| カードに書かれている整数 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 枚数 | 2 | 0 | 1 | 3 | 0 | 2 | 1 |
- 2から取り出した場合、2と3のカードをすべてテーブルの上に置きます。残りは、16です。
- 5から取り出した場合、5と6と0のカードをすべてテーブルの上に置きます。残りは、11です。
残りを最小値にするには、書かれている整数が連続している区間にある整数×枚数が最大になっている必要があります。また、M-1から0をまたいで、1以降の整数も連続していると考えます。
C++ プログラム例（ABC277D）
それぞれの整数が何枚あるかカウントします。0からMのレンジが広いため、map を使います。また、0と連続する区間を簡単に処理するため、0以降とM以降を同一の枚数が入るようにします（17行目）。すべての整数の合計を変数 total に格納しておきます。
整数が連続する区間にある整数×枚数の最大値を求めます（25－35行目）。すべての整数が連続している場合、最大値が total の2倍になることに注意します（37ー39行目）。total から最大値を引いた値を出力します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n;
ll m;
cin >> n >> m;
map<ll, ll> b;
ll total = 0;
for (int i = 0; i < n; ++i) {
ll a;
cin >> a;
++b[a];
++b[a + m];
total += a;
}
ll result = 0;
ll sum = 0;
int prev = -100;
for (auto e : b) {
if (prev + 1 == e.first) {
sum += (e.first % m) * e.second;
prev = e.first;
} else {
if (e.first >= m) {
break;
}
sum = (e.first % m) * e.second;
prev = e.first;
}
result = max(result, sum);
}
if (result > total) {
result = total;
}
cout << total - result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC277D）
Python の default dict は、C++ の map と異なり、キーの大きさ順に取り出すことができません。このため、default dict のキーをリスト k に格納して、k をソートして、この値を使い、値を取り出しました。変数 sum は、組込み関数と名前が被っているため、変数名を s に変更しました。
基本的な考え方はC++と同じです。
"""AtCoder Beginner Contest 277 D"""
from collections import defaultdict
n, m = map(int, input().split())
a = list(map(int, input().split()))
total = sum(a)
b = defaultdict(int)
kt = set()
for i in range(n):
b[a[i]] += 1
b[a[i] + m] += 1
kt.add(a[i])
k = []
for i in kt:
k.append(i)
k.append(i + m)
k.sort()
result = 0
s = 0
prev = -100
for e in k:
if prev + 1 == e:
s += (e % m) * b[e]
prev = e
else:
if e >= m:
break
s = (e % m) * b[e]
prev = e
result = max(result, s)
result = min(result, total)
print(total - result)こちらも「AC」と判定されました。
最後に
コンテストでは、「今のわたしには難しく感じました」とのコメントが残っていました。改めて挑戦すると解くことができました。進歩を感じるとうれしく感じます。
引き続き ABC の問題を紹介していきます。
