AtCoder が提供しているABC（AtCoder Beginner Contest）329 のD問題をC++とPythonで解いてみました。ABC329は、2023年11月18日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Election Quick Report（Difficulty : 263）
問題はリンク先をご覧ください。
ABC329 D問題 Election Quick Report
読み取った投票により最多得票者の情報を更新します。AtCoder Problems による Difficulty は 263 でした。
解答案
C++ プログラム例（ABC329D）
投票は1票しか入りません。このため、最多得票者は、もともとの最多得票者か最新の投票がされた人かのどちらかになります。
- 最多得票者を result に格納します。初期値は範囲外の0にしておきます。
- 得票数を配列 count で管理します。
- 投票によって最多得票者が入れ替わった場合は、result を更新します（17ー18行目）。
- 得票数が同じになった場合は、番号が小さい人が最多得票者となります（19ー20行目）。
以下が、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<int> count(n + 1, 0);
int result = 0;
for (int i = 0; i < m; ++i) {
++count[a[i]];
if (count[result] < count[a[i]]) {
result = a[i];
} else if (count[result] == count[a[i]]) {
result = min(result, a[i]);
}
cout << result << endl;
}
return 0;
}Python プログラム例（ABC329D）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 329 D"""
n, m = map(int, input().split())
a = list(map(int, input().split()))
count = [0] * (n + 1)
result = 0
for i in range(m):
count[a[i]] += 1
if count[result] < count[a[i]]:
result = a[i]
elif count[result] == count[a[i]]:
result = min(result, a[i])
print(result)こちらも「AC」と判定されました。
最後に
コンテストABC329は、D問題まで取り組みやすい難易度でした。わたしは、D問題までしか解けず、時間は52:06でした（C問題のWA2回のペナルティ込み）。わたしのレート（900弱）であれば、30分程度でD問題まで解けているようです。解くスピードも上げなければならないと痛感しました。
引き続き ABC の問題を紹介していきます。
