ABC361 B問題（Intersection of Cuboids）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）361 B問題をC++とPythonで解いてみました。ABC361は、2024年7月6日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

B問題 Intersection of Cuboids（Difficulty : 299）

問題の詳細は、リンク先をご覧ください。

ABC361 B問題 Intersection of Cuboids

1次元の考察を3次元に拡張します。AtCoder Problems による Difficulty は 299 でした。

解答案

$x$ 軸だけを取り出して考えます。制約から $0 \leqq a < d \leqq 1000$、$0 \leqq g < j \leqq 1000$ であることがわかります。$[a, d]$ と $[g, j]$ の共通部分の長さがないとは、$j \leqq a$ または、$d \leqq g$ であることと同値になります。

$x$ 軸の考察を $y$ 軸と $z$ 軸に拡張します。3辺のうち、ひとつでも共通部分がなくなれば、直方体の共通部分の体積が0になります。

C++ プログラム例（ABC361B）

$x, y, z$ 軸の条件を確認して、ひとつでも共通部分の条件を満たさなければ、結論は “No” となります。

小文字の ’l’ は、’1′ と見間違いやすいです。このため、この文字だけ大文字の ‘L’ にしています。

以下が、C++プログラムです。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int a, b, c, d, e, f;
	cin >> a >> b >> c >> d >> e >> f;
	int g, h, i, j, k, L;
	cin >> g >> h >> i >> j >> k >> L;

	bool result = true;
	if ((j <= a)||(d <= g)) {
		result = false;
	}
	if ((k <= b)||(e <= h)) {
		result = false;
	}
	if ((L <= c)||(f <= i)) {
		result = false;
	}

	if (result) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC361B）

Python版も基本的な考え方は同じです。以下がプログラムです。

"""AtCoder Beginner Contest 361 B"""
a, b, c, d, e, f = map(int, input().split())
g, h, i, j, k, L = map(int, input().split())

result = True
if j <= a or d <= g:
    result = False
if k <= b or e <= h:
    result = False
if L <= c or f <= i:
    result = False

print("Yes" if result else "No")

どちらも「AC」と判定されました。

最後に

ABC321E問題やABC343E問題など、3次元の直方体を扱う問題は、自分の実力では難しいという印象がありましたが、この問題は制約が易しくなっていて解くことができました。

引き続き ABC の問題を紹介していきます。