AtCoder が提供しているABC（AtCoder Beginner Contest）354 C問題をC++とPythonで解いてみました。ABC354は、2024年5月18日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 AtCoder Magics（Difficulty : 441）
問題の詳細は、リンク先をご覧ください。
強い順にカードをソートして、コストを比較しながら処理します。AtCoder Problems による Difficulty は 441 でした。
解答案
以下の考えでカードを処理します。
- (カードの強さ、カードのコスト）の組で降順にソートします。
- 1枚目のカードは、一番強いためコストの逆転が発生しません。したがって、弱いカードとなりません。1枚目のカードのコストを「最小コスト」として記憶しておきます。
- 2枚目以降のカードは、以下のように処理します。
- そのカードのコストが「最小コスト」より高い場合は、そのカードより前に処理した強いカードとコストが逆転しているカードがあることを意味します。このため、弱いカードとなります。
- そのカードのコストが「最小コスト」より安い場合は、そのカードより前に処理した強いカードとコストの逆転が発生していません。したがって、弱いカードではありません。
- カードを処理した後、処理したカードのコストで「最小コスト」を更新します。
C++ プログラム例（ABC354C）
(カードの強さ、カードのコスト）を配列 p に格納します。カードの強さはすべて異なるため、カードの強さとインデックス（最終的な出力で必要）を連想配列で紐づけます。
配列 p をソートして、上で述べた処理を行い、弱いカードではないカードのインデックスを配列 result に格納します（23行目）。「最小コスト」は、25行目で更新しています。
最後の配列 result の要素数とソートした要素を出力して終了します。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<pair<int, int>> p(n);
map<int, int> a2i;
for (int i = 0; i < n; ++i) {
int a, c;
cin >> a >> c;
p[i] = make_pair(a, c);
a2i[a] = i + 1;
}
sort(p.begin(), p.end(), greater<pair<int, int>>());
vector<int> result;
result.push_back(a2i[p[0].first]);
int min_cost = p[0].second;
for (int i = 1; i < n; ++i) {
if (min_cost > p[i].second) {
result.push_back(a2i[p[i].first]);
}
min_cost = min(min_cost, p[i].second);
}
sort(result.begin(), result.end());
cout << result.size() << endl;
for (int i = 0; i < result.size(); ++i) {
cout << result[i] << " \n"[i == result.size() - 1];
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC354C）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 354 C"""
n = int(input())
p = [(0, 0)] * n
a2i = {}
for i in range(n):
a, c = map(int, input().split())
p[i] = (a, c)
a2i[a] = i + 1
p.sort(reverse=True)
result = []
result.append(a2i[p[0][0]])
min_cost = p[0][1]
for i in range(1, n):
if min_cost > p[i][1]:
result.append(a2i[p[i][0]])
min_cost = min(min_cost, p[i][1])
result.sort()
print(len(result))
print(*result)こちらも「AC」と判定されました。
最後に
この問題は、しっかりと考えを整理すれば、それほど難しくないと感じました。一方、コンテストでは、D問題の後に取り組みACまでに時間がかかりました（ACは96分18秒でした）。
速く解くことも意識していますが、うまくいっていません。
引き続き ABC の問題を紹介していきます。
