คำอธิบายวิธีทำพร้อม code สำหรับข้อ toi20_tour

สรุปโจทย์

ที่จังหวัดนครปฐม มีการแข่งขัน shopping โดยจะมีจำนวนโซนร้านค้า ทั้งหมด $L$ โซน แต่ละโซนจะมีร้านค้า $N_i$ ร้าน แต่ละร้านจะมีสินค้าแค่ 1 ประเภท เป็น “ตุ๊กตาน้องส้มโอหวาน” หรือ “ตุ๊กตาน้องข้าวสารขาว”
กติกาในการแข่งขันของคู่รักคนแรกจะเริ่ม shopping จากร้านค้าที่ 1 ซึ่งอยู่ในโซนที่ 1 จากนั้น จะไป shopping ต่อไปยังร้านค้าที่อยู่ในโซนถัดไป (โซนที่ 2) เพียง 1 ร้านเท่านั้น (สามารถเข้า shopping ได้เพียง 1 ร้านต่อ 1 โซนเท่านั้น) จากนั้นจะต้องเดินทางจากร้านดังกล่าวไป shopping ยังร้านถัดไปในโซนถัดไปเรื่อย ๆ จนกว่าจะถึงร้านค้าสุดท้ายในโซนที่ $L$ โดยการ shopping จะต้อง shopping ภายใต้เส้นทางที่จัดสรรให้เท่านั้น
คู่รักที่จะได้รับรางวัลในการแข่งขัน shopping ในครั้งนี้คือคู่รักที่สามารถทําให้ค่าความต่างใจ $D = (F − F')^2 + (G − G')^2$ $($$F$ $=$ จำนวนตุ๊กตาน้องส้มโอหวานที่คู่รักคนแรกได้รับมา, $F'$ $=$ จำนวนตุ๊กตาน้องส้มโอหวานที่คู่รักคนที่สองได้รับมา, $S$ $=$ จำนวนตุ๊กตาน้องข้าวสารขาวที่คู่รักคนแรกได้รับมา, $S'$ $=$ จำนวนตุ๊กตาน้องข้าวสารขาวที่คู่รักคนที่สองได้รับมา$)$ มีค่าที่น้อยที่สุด เพราะถือว่าคู่รักทั้งคู่มีใจตรงกันมาก แต่อย่างไรก็ตามหากค่าความต่างใจ ดังกล่าวมีค่าเป็น $0$ กรรมการจะทําการตรวจสอบเส้นทาง shopping ของคู่รักทั้งคู่ หากพบว่า คู่รักทั้งคู่ใช้เส้นทางรูปแบบเดียวกัน 100% ในการ shopping การแข่งขันดังกล่าวถือว่าไม่สุจริต และจะไม่อนุญาตให้รับรางวัลในกรณีนี้

สิ่งที่ต้องทำ

เขียนโค้ดที่จะคำนวณว่า ค่าความต่างใจที่น้อยที่สุดจะมีค่าเท่าใด

ขอบเขตข้อมูล

$N$ หมายถึง จํานวนร้านค้าทั้งหมด และ $4 \leq N ≤ 200,000$
$M$ หมายถึง จํานวนเส้นทาง และ $3 ≤ M ≤ 300,000$
$L$ หมายถึง จํานวนโซน และ $3 ≤ L ≤ 10$
$n_i$ หมายถึง จำนวนร้านในแต่ละโซน และ

• $\sum_{i = 1} ^ {L} n_i = N$
• $\prod_{i = 1} ^ {L} n_i \leq 10^6$
• $n_1 = n_l = 1$

ข้อสังเกต

• $\prod_{i = 1} ^ {L} n_i \leq 10^6$
• สูตรคำนวณ “ค่าความต่างใจ” $: D = (F − F')^2 + (G − G')^2$ ค่อนข้างคล้ายกับสูตรคำนวณ Euclidean Distance $: D = \sqrt{(x_2 − x_1)^2 + (y_2 − y_1)^2}$

วิธีทำ

เราจะทำการ Brute Force เพื่อหาทุกๆคู่อันดับ $(F, G)$ ที่เป็นไปได้ (เราสามารถทำการ Brute Force ได้เพราะว่า ผลคูณของจำนวนร้านทั้งหมดในแต่ละโซน จะมีค่าไม่เกิน $10^6$) และเมื่อเราหาออกมาแล้ว เราจะใช้อัลกอริทึมที่ชื่อว่า “Closest Pair of Points” ซึ่งจริงๆแล้วใช้หาระยะที่สั้นที่สุดระหว่างจุดสองจุด แต่เนื่องจากสูตรคำนวณค่าความต่างใจเหมือนกับสูตรคำนวณ Euclidean Distance (ต่างกันแค่สูตรคำนวณ Euclidean Distance จะมีการใส่เครื่องหมาย Square Root $(\sqrt)$) เราจึงสามารถใช้อัลกอริทึมดังกล่าวเพื่อหาคู่อันดับ $(F, G)$ 2 คู่ที่เมื่อคำนวณ “ค่าความต่างใจ” ออกมาแล้ว จะมีค่าน้อยที่สุด

Summary

• ใช้การ Brute Force ในการหาคู่อันดับ $(F, G)$ ทั้งหมด
• ใช้อัลกอริทึม Closest Pair of Points ในการหา “ค่าความต่างใจ” ที่น้อยที่สุด

Solution Code:

#include <bits/stdc++.h> 

#define int long long 

using namespace std; 

const int N = 1e1 + 5; 

int n, m, l, z[N]; 
vector <pair <int, int>> p; 
vector <tuple <int, int, int>> adj[200005]; 

void dfs(int u, int x, int y) { 
	for (auto [s, w, v] : adj[u]) { 
		if (v == n) { 
			p.emplace_back((s == 1 ? make_pair(x + w, y) : make_pair(x, y + w))); continue; 
		} 
		if (s == 1) dfs(v, x + w, y); 
		else dfs(v, x, y + w); 
	} 
} 
int dis(pair <int, int> a, pair <int, int> b) { // ใช้คำนวณ ค่าความต่างใจ / euclidean distance 
	return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second); 
} 

int cpop(int l, int r){ 
	if (r - l + 1 <= 3) { 
		int ans = 1e18; 
		for (int i = l; i < r; i++) { 
			for (int j = i + 1; j <= r; j++) { 
				ans = min(ans, dis(p[i], p[j])); 
			} 
		} 
		return ans; 
	} 
	int mid = (l + r) / 2; 
	int left = cpop(l, mid), right = cpop(mid, r); 
	int mn = min(left, right); 
	int xm = p[mid].first; 
	vector <pair <int, int>> pts; 
	for (int i = l; i <= r; i++) { 
		if ((p[i].first - xm) * (p[i].first - xm) < mn) pts.emplace_back(p[i]); 
	} 
	sort(pts.begin(), pts.end(), [](const pair <int, int> &a, const pair <int, int> &b){ 
		return a.second < b.second;
	}); 
	for (int i = 0; i < pts.size(); i++) { 
		for (int j = i + 1; j < pts.size() && dis(pts[i], pts[j]) < mn; j++) { 
			mn = min(mn, dis(pts[i], pts[j])); 
		} 
	} 
	return mn; 
} 

int32_t main(){ 
	cin.tie(NULL)->sync_with_stdio(false); // input 
	cin >> n >> m >> l; 
	for (int i = 1; i <= l; i++) cin >> z[i]; 
	for (int i = 1; i <= m; i++) { 
		int u, v, s, w; cin >> u >> v >> s >> w; 
		adj[u].emplace_back(s, w, v); 
	} 
	// brute force calculations 
	dfs(1, 0, 0); 
	// closest pair of points algorithm 
	sort(p.begin(), p.end()); 
	cout << cpop(0, p.size() - 1); 
}

Total Time Complexity:

กำหนดให้ $x = \prod_{i = 1} ^ {L}$ (จำนวนคู่อันดับ $(F, G)$ ที่หาออกมาได้)

• Brute Force: $O(x)$
• Closest Pair of Points: $O(x$ $log$ $x)$
• Total: $O(x + x$ $log$ $x)$

หากมีข้อสงสัย comment ไว้ใต้ post ได้เลยนะครับ 🙇‍♂️🙇‍♂️
ศึกษาโจทย์เพิ่มเติมได้ที่ Fast X Fourier