Hướng dẫn giải của Trò chơi "Bộ ba"
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhậpTác giả: , , ,
Hiểu bài toán
Bài toán yêu cầu đếm số lượng các bộ ba chữ cái (3 ô khác nhau chứa 3 chữ cái khác nhau) nằm trên cùng một đường thẳng. Bảng kích thước N x N (N ≤ 100). Các chữ cái là duy nhất. Chúng ta cần kiểm tra tất cả các tổ hợp 3 chữ cái xem chúng có thẳng hàng không.
Các cách tiếp cận
Cách Brute Force
#include <bits/stdc++.h>
using namespace std;
struct Point {
int r, c;
};
bool collinear(Point a, Point b, Point c) {
// Tính diện tích tam giác bằng tích có hướng
// Diện tích = 0 thì 3 điểm thẳng hàng
return 1LL * (b.r - a.r) * (c.c - a.c) == 1LL * (b.c - a.c) * (c.r - a.r);
}
int main() {
int N;
cin >> N;
vector<Point> pts;
for (int i = 0; i < N; ++i) {
string s;
cin >> s;
for (int j = 0; j < N; ++j) {
if (s[j] != '.') {
pts.push_back({i, j});
}
}
}
int ans = 0;
int m = pts.size();
for (int i = 0; i < m; ++i) {
for (int j = i + 1; j < m; ++j) {
for (int k = j + 1; k < m; ++k) {
if (collinear(pts[i], pts[j], pts[k])) {
ans++;
}
}
}
}
cout << ans << endl;
return 0;
}
- Time Complexity: O(M^3), với M là số ô có chữ cái (M ≤ N^2). Trong trường hợp xấu nhất M ~ 10^4, độ phức tạp ~10^12, quá chậm.
- Space Complexity: O(M)
Phương pháp này lấy tất cả các ô có chữ cái lưu vào một danh sách, sau đó duyệt qua tất cả các tổ hợp 3 điểm (i, j, k) và kiểm tra xem chúng có thẳng hàng không bằng cách kiểm tra xem diện tích tam giác có bằng 0 không. Do N nhỏ (≤ 100), số lượng ô có chữ cái tối đa là 10,000. Việc duyệt 3 vòng lặp lồng nhau O(M^3) sẽ quá chậm cho M lớn.
Cách Tối ưu O(M^2)
#include <bits/stdc++.h>
using namespace std;
struct Point {
int r, c;
};
int main() {
int N;
cin >> N;
vector<Point> pts;
// Đánh dấu vị trí các chữ cái
bool has_char[105][105] = {0};
for (int i = 0; i < N; ++i) {
string s;
cin >> s;
for (int j = 0; j < N; ++j) {
if (s[j] != '.') {
pts.push_back({i, j});
has_char[i][j] = true;
}
}
}
long long ans = 0;
int m = pts.size();
for (int i = 0; i < m; ++i) {
for (int j = i + 1; j < m; ++j) {
// Tính vector từ pts[i] đến pts[j]
int dr = pts[j].r - pts[i].r;
int dc = pts[j].c - pts[i].c;
// Chuẩn hóa vector (Rút gọn ước chung) để dùng cho việc kiểm tra điểm thứ 3
// Tuy nhiên, ở đây ta chỉ cần kiểm tra các điểm nằm trên đường thẳng kéo dài từ pts[i] qua pts[j]
// Ta chỉ quan tâm đến các điểm nằm ở vị trí pts[k] sao cho pts[i], pts[j], pts[k] thẳng hàng.
// Để tránh đếm trùng, ta chỉ xét pts[k] nằm sau pts[j] theo hướng thẳng hàng.
// Tính bước nhảy
int g = __gcd(abs(dr), abs(dc));
dr /= g;
dc /= g;
// Kiểm tra điểm thứ 3
// Chỉ kiểm tra các điểm pts[k] mà k > j (tránh đếm trùng)
// Hoặc kiểm tra các điểm nằm trên đường thẳng nhưng chỉ đếm nếu pts[k] thỏa mãn một thứ tự nhất định.
// Cách dễ nhất: duyệt pts[k] với k > j, kiểm tra thẳng hàng.
// Nhưng để tối ưu O(M^2), ta có thể dùng map hoặc mảng đánh dấu.
// Tuy nhiên, với N=100, M tối đa 10000, O(M^2) ~ 10^8 là chấp nhận được.
// Nhưng cách dưới đây là O(M^3) active.
// Sử dụng map để đếm số điểm thẳng hàng với pts[i] và pts[j]
// Chỉ xét pts[k] với k > j để tránh đếm trùng.
}
}
// Thực tế, giải pháp O(M^2) đúng phải dùng map để đếm số điểm trên cùng một đường thẳng với pts[i] làm gốc.
// Hoặc đơn giản hơn: Với mỗi điểm i, tính tất cả các vector đến các điểm j > i.
// Nhóm các vector cùng phương (cùng hệ số góc) lại.
// Nếu có K điểm cùng phương với i, ta có thể chọn 2 điểm trong số đó để tạo thành 1 bộ ba.
// Để đảm bảo không đếm trùng, ta chỉ xét các bộ ba (i, j, k) với i < j < k.
// Code thực tế:
for (int i = 0; i < m; ++i) {
map<pair<int, int>, int> slope_count;
for (int j = i + 1; j < m; ++j) {
int dr = pts[j].r - pts[i].r;
int dc = pts[j].c - pts[i].c;
int g = __gcd(abs(dr), abs(dc));
dr /= g;
dc /= g;
// Chuẩn hóa hướng để (dr, dc) và (-dr, -dc) là 1
if (dr < 0 || (dr == 0 && dc < 0)) {
dr = -dr;
dc = -dc;
}
slope_count[{dr, dc}]++;
}
// Với mỗi hướng, nếu có k điểm cùng hướng, ta có thể tạo C(k, 2) bộ ba bắt đầu từ i
for (auto p : slope_count) {
int k = p.second;
ans += 1LL * k * (k - 1) / 2;
}
}
cout << ans << endl;
return 0;
}
- Time Complexity: O(M^2 log M) hoặc O(M^2) tùy thuộc vào cấu trúc dữ liệu. Với M ≤ 10000, M^2 = 10^8. Cần cẩn thận với constant factor.
- Space Complexity: O(M)
Cải tiến từ Brute Force. Thay vì duyệt O(M^3) để tìm điểm thứ 3, ta xét mỗi điểm i làm gốc. Với i, ta tính vector đến tất cả các điểm j > i. Các điểm j nào cùng phương (cùng hệ số góc) với i sẽ tạo thành các bộ ba thẳng hàng nếu đi qua i. Ta dùng map để đếm số lượng điểm cho mỗi phương. Với mỗi phương có k điểm, số bộ ba tạo thành là C(k, 2). Tổng cộng qua các điểm i, ta có thể đếm hết các bộ ba một cách hiệu quả.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(M^3), với M là số ô có chữ cái (M ≤ N^2). Trong trường hợp xấu nhất M ~ 10^4, độ phức tạp ~10^12, quá chậm. | O(M) | Brute Force |
| 2 | O(M^2 log M) hoặc O(M^2) tùy thuộc vào cấu trúc dữ liệu. Với M ≤ 10000, M^2 = 10^8. Cần cẩn thận với constant factor. | O(M) | Tối ưu O(M^2) |
Bài học kinh nghiệm
- Bài toán quy về bài toán đếm các bộ 3 điểm thẳng hàng trong tập hợp các điểm.
- Có thể tối ưu bằng cách xét từng điểm làm gốc và phân loại các điểm còn lại theo phương của vector.
Lỗi thường gặp
- Quên chuẩn hóa vector dẫn đến sai lệch khi so sánh phương.
- Đếm trùng các bộ ba nếu không áp dụng quy tắc thứ tự (ví dụ chỉ xét i < j < k).
- Sử dụng số nguyên nhỏ gây tràn số khi tính tích.
Bình luận