AtCoder が提供しているABC（AtCoder Beginner Contest）355 D問題をC++とPythonで解いてみました。ABC355は、2024年5月25日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Intersecting Intervals（Difficulty : 735）
問題の詳細は、リンク先をご覧ください。
ABC355 D問題 Intersecting Intervals
共通部分を持たない区間の組の数を求めます。AtCoder Problems による Difficulty は 735 でした。
解答案
共通部分を持たない区間の組の数を求めることができれば、問題を解くことができます。
C++ プログラム例（ABC355D）
左端と右端をまとめて、配列に格納してソートして、小さい順に処理します。
- 次の整数が左端の場合、その時点で右端が来ている区間の数（finished）が、その区間と共通部分を持たないことになります。
- 次の整数が右端の場合、右端が来ている区間の数（finished）を増やします。
$n$ 個の区間から2つを選ぶ組み合わせの数は、$n \times (n – 1) / 2$ から共通部分を持たない区間の組の数（変数 result）を引いた値を出力します（30行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ll n;
cin >> n;
vector<pair<int, int>> event;
for (int i = 0; i < n; ++i) {
int L, R;
cin >> L >> R;
event.push_back(make_pair(L, 0));
event.push_back(make_pair(R, 1));
}
sort(event.begin(), event.end());
ll result = 0;
ll finished = 0;
for (auto e : event) {
if (e.second == 0) {
result += finished;
} else {
++finished;
}
}
cout << n * (n - 1) / 2 - result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC355D）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 355 D"""
n = int(input())
event = []
for i in range(n):
L, R = map(int, input().split())
event.append((L, 0))
event.append((R, 1))
event.sort()
result = 0
finished = 0
for e in event:
if e[1] == 0:
result += finished
else:
finished += 1
print(n * (n - 1) // 2 - result)こちらも「AC」と判定されました。
最後に
この問題はコンテストで解くことができませんでした。今回のコンテストはE問題以降の難易度が高く、D問題が解けないことで大きくレートを下げました。過度に気にせず、コンテストを楽しもうと考えています。
引き続き ABC の問題を紹介していきます。
