ABC207のC問題 Many Segments をすんなりと解く

ABC207のC問題を解説します。

atcoder.jp

問題の概要

区間が 個あたえられて、共通部分を含む2つの区間の組み合わせを求める問題です。

難しいポイント

区間といっても、開区間、閉区間の表現があり、2つの区間で共通している区間を含むか含まないかを、どうやって実装するかが難しいところかと思います。
サンプルにあると ]の共通部分 をどうやって判定するかです。
って2も3も含まないのにどういう区間と思ったら、少数の世界をイメージすると2.1、2.2、2.3みたいな区間ということがわかります。

解き方の方針

Nが最大で2000なので全ての組み合わせを考えても、 で全通り調べても問題ないオーダーです。
2つの区間に共通区間があるかないかを判定して、共通区間があればカウントします。
tで条件分岐して、端の数字が含まれない場合は、端の数字に0.1を足したり、引いたりします。

実装

実装は以下のようになりました。
get_rangeなんていうメソッドを作らないで、読み込むときにtで条件分岐して端の数字に0.1を足したり引いたりすれば良いと思います。

from itertools import combinations
N = int(input())
r_list = []
for _ in range(N):
    t, l, r = map(int, input().split())
    r_list.append([t, l, r])


def get_range(r):
    if r[0] == 1:
        return [r[1], r[2]]
    if r[0] == 2:
        return [r[1], r[2] - 0.1]
    if r[0] == 3:
        return [r[1] + 0.1, r[2]]
    return [r[1] + 0.1, r[2] - 0.1]


def hikaku(r1, r2) -> bool:
    r1_range = get_range(r1)
    r2_range = get_range(r2)
    if r1_range[1] >= r2_range[0] and r1_range[0] < r2_range[1]:
        return True
    if r2_range[1] >= r1_range[0] and r2_range[0] < r1_range[1]:
        return True
    return False


c_list = combinations(range(N), 2)
ans = 0
for c in c_list:
    if hikaku(r_list[c[0]], r_list[c[1]]):
        ans += 1
print(ans)