問題文

\(1\) から \(N\) までの番号が付いた \(N\) 個の区間が与えられます。区間 \(i\) は、

• \(t_i = 1\) なら \([l_i,r_i]\)
• \(t_i = 2\) なら \([l_i,r_i)\)
• \(t_i = 3\) なら \((l_i,r_i]\)
• \(t_i = 4\) なら \((l_i,r_i)\)

です。

\(1 \leq i < j \leq N\) を満たす整数の組 \((i,j)\) のうち、区間 \(i\) と区間 \(j\) が共通部分を持つようなものは幾つありますか？

制約

• \(2 \leq N \leq 2000\)
• \(1 \leq t_i \leq 4\)
• \(1 \leq l_i < r_i <10^9\)
• 入力は全て整数

概要

• 二重for文によって、条件をみたすものの個数を数え上げる。
• 区間同士が共通部分を持つことの判定は、できるだけ少ない場合分けで済むように工夫する。

STEP1　二重for文による数え上げ

整数の組 \((i,j)\) のうち、条件をみたすものの個数を求める 数え上げ ジャンルの問題です。 今回は \(N \leq 2000\) なので、二重for文による全探索を行っても実行時間制限に間に合います。

(二重for文による全探索の実装例)

int answer = 0;

for (int i = 0; i < N; i++) {
	for (int j = i + 1; j < N; j++) {

		//区間 i と区間 j が共通部分を持っていれば、 answer に 1 を加える
	}
}

cout << answer << endl;

STEP2　区間同士が共通部分を持つかの判定

区間 \(i\) と 区間 \(j\) がいつ共通部分を持つか調べましょう。 6つの値 \(t_i,l_i,r_i,t_j,l_j,r_j\) を見ながら場合分けを行います。 場合分けの方法によっては実装が複雑になってしまうので、できる限りシンプルな場合分けを考えます。 公式解説では区間の幅を0.5だけ変化させる賢い方法が紹介されていましたが、この解説ではそれが思いつかなかった場合の方法を紹介します。

区間 同士が共通部分を 持たない 条件を考えます。 大雑把には次の2通りの状況が考えられます。

• 区間 \(i\) が 区間 \(j\) よりも左にある。
• 区間 \(j\) が 区間 \(i\) よりも右にある。

2-1 　区間 \(i\) が区間 \(j\) よりも左にある。

\(r_i,l_j\)の値に注目することで、さらに3通りの可能性にわけられます。

• \(r_i < l_j\) である。
• \(r_i = l_j\) かつ、区間 \(i\) の右側の括弧が開いている。
• \(r_i = l_j\) かつ、区間 \(j\) の左側の括弧が開いている。

2-2　区間 \(i\) が区間 \(j\) よりも右にある。

こちらも3通りの可能性にわけられます。

• \(r_j < l_i\) である。
• \(r_j = l_i\) かつ、区間 \(j\) の右側の括弧が開いている。
• \(r_j = l_i\) かつ、区間 \(i\) の左側の括弧が開いている。

( 注意: 開いた括弧とは (,)、閉じた括弧とは[,]のことを指します。)

以上に列挙した6通りの可能性をすべて取り除き、残った場合について answer に 1 を加えればよいです。

(for文の内部の実装例)

	if (r[i] < l[j]) { continue; }

	if (r[i] == l[j]) {
		if (t[i] == 2 || t[i] == 4) { continue; }
		if (t[j] == 3 || t[j] == 4) { continue; }
	}

	if (r[j] < l[i]) { continue; }

	if (r[j] == l[i]) {
		if (t[j] == 2 || t[j] == 4) { continue; }
		if (t[i] == 3 || t[i] == 4) { continue; }
	}

	answer++;

プログラム全体での計算量は \(O(N^2)\) で、実行時間制限に間に合います。

実装例(C++)

https://atcoder.jp/contests/abc207/submissions/23893568

余談

この問題では、場合分けの数を減らすために2つの工夫を行いました。

1. 区間同士が重なっている状況ではなく、重なっていない状況を考える。

   • 区間が重なっている状況は、「片方の区間がもう一方の区間を含んでいる場合」「区間同士が千鳥式に重なっている場合」など考慮すべきものが多く、場合分けが複雑になりがちです。余事象をとり、区間同士が重なっていない状況を考えることで、場合分けがシンプルになりました。

2. \(t\) を基準に場合分けを行うのではなく、 \(l,r\)を基準に場合分けを行う。

   • 場合分けをする際の基本として、影響力の大きなものから順番に決める という考え方があります。この問題の場合、\(l,r\) は区間の位置を決める一方で、\(t\) の値は区間が閉じてるか開いているかにしか影響しません。そこで、\(l,r\) の値に基づいておおよその場合分けを行った後、コーナーケースについてのみ \(t\) の値を見ることで、余計な場合分けを避けることができました。

この問題に限らず様々な場面において、シンプルでわかりやすい実装 を行うことはとても大事なので、コンテスト中だけではなく過去問を解く際にも心がけるとよいでしょう(自戒をこめて)