AtCoder

ABC277 D問題(Takahashi’s Solitaire)を解く

AtCoder_ABC277_D

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になります。

カードに書かれている整数0123456
枚数2013021
  • 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 を解いていきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA