AtCoder が提供しているABC（AtCoder Beginner Contest）273 のC問題をC++とPythonで解いてみました。ABC273は、2022年10月15日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 (K+1)-th Largest Number（Difficulty : 370）
問題はリンク先をご覧ください。
ABC273 C問題 (K+1)-th Largest Number
それぞれの数がいくつあるか map を使って処理する問題です。AtCoder Problems による Difficulty は、370 でした。
解答案
問題を読んでも、何を出力するのかイメージがわきませんでした。入力例1に対応する出力例1の説明をみて、問題が理解できました。
入力：2 7 1 8 2 8
これを小さい数から並べなおします。
- 1（1個）より大きい数は、2、7、8 の3種類
- 2（2個）より大きい数は、7、8 の2種類
- 7（1個）より大きい数は、8 の1種類
- 8（2個）より大きい数は、0 種類
よって、K ＝ 0、1、2、3、4、5、6 について
- K = 0 となる数は、8の2個
- K = 1 となる数は、7の1個
- K = 2 となる数は、2の2個
- K = 3 となる数は、1の1個
- K は4以上となる数は、存在しない。
問題を解く方針を書きだします。
- N を読み込む。
- 数列を A を読みながら、各数字がいくつあるかカウントする。
- 各数字より大きい数字をカウントする。
- 各 K に対して、該当する数字の個数を出力する。
C++ プログラム例（ABC273C）
C++ の場合、map を使います。map は順序を保つため、この問題は解きやすくなりました。最終的な出力は、Vector<int> 型の K として格納します。map の個数を使えば、その数より大きい数が何種類あるか分かります（18行目）。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
map<int, int> m;
for (int i = 0; i < n; ++i) {
int a;
cin >> a;
++m[a];
}
vector<int> k(n, 0);
int t = 1;
for (auto it = m.begin(); it != m.end(); ++it) {
k[m.size() - t] = (*it).second;
++t;
}
for (int i = 0; i < n; ++i) {
cout << k[i] << endl;
}
return 0;
}2024年4月27日追記
結局、大きい数から順に頻度を出力すればよいことが分かりました。大きい順に頻度を出力して、N行になるまで0を出力します。こちらの方がすっきりと書けています。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
map<int, int> m;
for (int i = 0; i < n; ++i) {
int a;
cin >> a;
++m[a];
}
for (auto it = m.rbegin(); it != m.rend(); ++it) {
cout << (*it).second << endl;
}
for (int i = m.size(); i < n; ++i) {
cout << 0 << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC273C）
Python の辞書は、バージョン 3.7 から登録した順序を保つことが保証されました。小さい数字から登録するために、読み込んだリスト a を sort してから、辞書 m に登録しています。
C++ のロジックを流用しているため、Python らしい書き方になっていないかもしれません。
"""AtCoder Beginner Contest 273 C"""
n = int(input())
a = list(map(int, input().split()))
a.sort()
m = {}
for i in a:
if i in m:
m[i] += 1
else:
m[i] = 1
k = [0] * n
t = 1
for i in m.keys():
k[len(m) - t] = m[i]
t += 1
print(*k, sep="\n")Python 版も「AC」と判定されました。
2022年11月28日 結果のリスト出力を Python らしく修正しました。
最後に
この問題は、最初の出力例をみて問題が把握できました。
AtCoder では、例外的なケースを入力例とその出力例で気づかせるような工夫がしてある場合もあります。入力例と出力例を丁寧に読むと、正答率はあがると考えています。
引き続き ABC の問題を紹介していきます。
