AtCoder が提供しているABC（AtCoder Beginner Contest）323 のC問題をC++とPythonで解いてみました。ABC323は、2023年10月7日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 World Tour Finals（Difficulty : 357）
問題はリンク先をご覧ください。
各プレイヤーが解けなかった問題から処理していきます。AtCoder Problems による Difficulty は、357 でした。※2023年10月15日 Difficulty を追記しました。
解答案
1からN（最大値100）までのプレイヤーに対して、プレイヤーの数字がボーナス点として与えられます。問題の点数 Ai は、100の倍数となるため、同じ点数になるプレイヤーはいません。このため、この問題は解きやすくなっています。
- 最初に、それぞれのプレイヤーの点数を求める。
- プレイヤーの最高点を求める。最高点のプレイヤーは一人となります。
- それぞれのプレイヤーの解けていない問題から高い点数の問題を選び、最高点を超えるまでその点数を加えていきます。
C++ プログラム例（ABC323C）
以下は、プログラムの補足です。
- それぞれのプレイヤー score と最高点 max_score を求めます（17ー27行目）。
- 自分が最高点の場合、0 を出力します（30ー33行目）。
- 解けていない問題の点数を優先度付きキューに格納します。
- キューから高い点数順に取り出し、最高点を超えるまで加えていきます（44ー52行目）。
最終的なC＋＋プログラムは、以下となります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> a(m);
for (int i = 0; i < m; ++i) {
cin >> a[i];
}
vector<string> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
vector<int> score(n, 0);
int max_score = -1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (s[i][j] == 'o') {
score[i] += a[j];
}
}
score[i] += i + 1;
max_score = max(max_score, score[i]);
}
for (int i = 0; i < n; ++i) {
if (score[i] == max_score) {
cout << 0 << endl;
continue;
}
priority_queue<int> bonus;
for (int j = 0; j < m; ++j) {
if (s[i][j] == 'x') {
bonus.push(a[j]);
}
}
int bonus_score = score[i];
int result = 0;
while (1) {
bonus_score += bonus.top();
bonus.pop();
++result;
if (bonus_score > max_score) {
cout << result << endl;
break;
}
}
}
return 0;
}上記のプログラムでは、優先度付きキューを使いました。C++ では、multiset でも同じことができます。以下は、multiset を使ったプログラムです。コンテナに関係する行の背景色を変更しておきます。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> a(m);
for (int i = 0; i < m; ++i) {
cin >> a[i];
}
vector<string> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
vector<int> score(n, 0);
int max_score = -1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (s[i][j] == 'o') {
score[i] += a[j];
}
}
score[i] += i + 1;
max_score = max(max_score, score[i]);
}
for (int i = 0; i < n; ++i) {
if (score[i] == max_score) {
cout << 0 << endl;
continue;
}
multiset<int> bonus;
for (int j = 0; j < m; ++j) {
if (s[i][j] == 'x') {
bonus.insert(a[j]);
}
}
int bonus_score = score[i];
auto it = bonus.rbegin();
int result = 0;
while (1) {
bonus_score += *it;
++result;
if (bonus_score > max_score) {
cout << result << endl;
break;
}
++it;
}
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC323C）
Python 版も基本的な考え方は同じです。
heapq モジュールを import することにより、優先度付きキューを使うことができます。heapq が提供するキューは、最小値を取り出します。今回の場合、最大値を取り出したいため、マイナスをつけた値を push して、pop した値にマイナスをつけています（26、31行目）。
"""AtCoder Beginner Contest 323 C"""
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
s = [input() for i in range(n)]
score = [0] * n
max_score = -1
for i in range(n):
for j in range(m):
if s[i][j] == 'o':
score[i] += a[j]
score[i] += i
max_score = max(max_score, score[i])
for i in range(n):
if score[i] == max_score:
print(0)
continue
que = []
heapq.heapify(que)
for j in range(m):
if s[i][j] == 'x':
heapq.heappush(que, -a[j])
bonus_score = score[i]
result = 0
while True:
bonus_score += -heapq.heappop(que)
result += 1
if bonus_score > max_score:
print(result)
breakこちらも「AC」と判定されました。
最後に
バーチャルコンテストで解いたときは、最初 set を使っていてWA判定となっていました。Priority_queue を使ってうまく動いた後に、set では要素が重複している場合に動かないことに気づきました。このようなミスは減らしていきたいです。
引き続き ABC の問題を紹介していきます。
