Số may mắn 2
Đề bài
Để khởi động cho một buổi học căng thẳng, giờ sinh hoạt 15 phút đầu mỗi buổi học của lớp 10 Tin K30 các bạn đã tổ chức trò chơi tạo hứng thú trong học tập. Người đứng ra tổ chức trò chơi là Thái An, bạn là học sinh giỏi và đam mê Tin học của lớp. Hội thi Tin học trẻ toàn quốc vừa qua Thái An cũng mang về cho mình một giải thưởng cá nhân. Trò chơi có tên "Tìm số may mắn" như sau: đầu tiên Thái An sử dụng máy tính sinh ra một dãy $A$ gồm $n$ số nguyên $a_1, a_2, \ldots, a_n$. Sau đó thực hiện $Q$ lần chơi tìm các số may mắn, mỗi lần chơi máy tính sẽ đưa ra số nguyên $x$, Thái An định nghĩa số may mắn là số lần xuất hiện của $x$ trong dãy $A$ nói trên.
Yêu cầu: gồm $Q$ lần chơi, mỗi lần chơi là một số nguyên $x$, bạn hãy tìm số may mắn trong mỗi lần chơi tương ứng.
Dữ liệu: vào từ file LUCKY.INP
- Dòng 1: một số nguyên duy nhất $n$ $(1 \le n \le 10^5)$.
- Dòng 2: dãy số $A$ gồm $n$ số nguyên $a_1, a_2, \ldots, a_n$ $(|a_i| \le 10^9)$.
- Dòng 3: số nguyên dương $Q$ $(Q \le 10^5)$.
- $Q$ dòng tiếp theo, mỗi dòng chứa một số nguyên $x$ $(|x| \le 10^9)$.
Các số trên cùng một dòng ghi cách nhau bởi dấu cách.
Kết quả: ghi ra file LUCKY.OUT gồm $Q$ dòng, mỗi dòng là một số may mắn với số $x$ tương ứng.
Ràng buộc:
- Có 40% test tương ứng 40% điểm của bài toán thỏa mãn $Q = 1,\ n \le 10^3$.
- Có 30% test tương ứng 30% điểm của bài toán thỏa mãn $Q \le 10^3,\ n \le 10^3$.
- Có 30% test cuối cùng tương ứng 30% điểm của bài không có ràng buộc gì thêm.
Giải thích ví dụ: số 5 xuất hiện 0 lần trong dãy, số 2 xuất hiện 2 lần, số 1 xuất hiện 1 lần.
Lưu ý: đề gốc đọc/ghi file LUCKY.INP / LUCKY.OUT; khi nộp trên CLUE OJ hay Codeforces thì hệ thống dùng bàn phím/màn hình (stdin/stdout). Code bên dưới của mình chạy được cả hai kiểu.
6
1 2 2 3 4 6
3
5
2
10
2
1Lời mở đầu
Đây là bài "nhập môn" kinh điển của chủ đề Map / Set: đếm xem một giá trị xuất hiện bao nhiêu lần, trả lời thật nhiều câu hỏi. Mình sẽ đi từ cách ai cũng nghĩ ra (duyệt cả dãy cho mỗi câu hỏi) để các bạn thấy vì sao nó chỉ ăn 70% điểm, rồi tới cách dùng map – một "cuốn sổ đếm" tra cứu cực nhanh, và cuối cùng là một cách không cần map mà vẫn full điểm.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
| Test | n | Q | max |số| | Thuộc |
|---|---|---|---|---|
| 1–8 | 2 – 1.000 | 1 – 1 | 4.873 | Subtask 1 |
| 9–14 | 3 – 1.000 | 9 – 1.000 | 992.874 | Subtask 2 |
| 15–20 | 5.919 – 100.000 | 20.593 – 100.000 | 999.971.982 | Subtask 3 |
Bộ test có 20 test, chia đúng tỉ lệ 40% – 30% – 30% như đề. Vài điều mình rút ra khi xem dữ liệu:
- 18/20 test có số âm trong dãy, nên đừng dùng mảng đếm
dem[a[i]]theo chỉ số (vừa âm, vừa lên tới $10^9$). - Khoảng 50% câu hỏi có đáp án 0 (số $x$ không hề có trong dãy) – code phải xử lý tốt trường hợp "không tìm thấy".
- Một số xuất hiện nhiều nhất cũng chỉ 14 lần trong một test, nên đáp án luôn vừa kiểu
int. - Ở subtask 3, $n \cdot Q$ lên tới $10^{10}$: đây là chỗ cách đếm "thủ công" sẽ gục.
| Subtask | Điều kiện | Test | Cách 1 duyệt | Cách 2 map | Cách 3 sort |
|---|---|---|---|---|---|
| 1 (40%) | $Q = 1,\ n \le 10^3$ | 1–8 | ✔ | ✔ | ✔ |
| 2 (30%) | $Q \le 10^3,\ n \le 10^3$ | 9–14 | ✔ | ✔ | ✔ |
| 3 (30%) | $n, Q \le 10^5$ | 15–20 | 3/6 test | ✔ | ✔ |
70–85%Cách 1: mỗi câu hỏi duyệt lại cả dãy
Cách tự nhiên nhất: với mỗi số $x$ được hỏi, đi từ đầu đến cuối dãy và đếm xem có bao nhiêu phần tử bằng $x$. Mỗi câu hỏi tốn $n$ phép so sánh, tổng cộng $n \cdot Q$ phép.
- Dòng
if (fopen("LUCKY.INP", "r")): nếu trong thư mục có fileLUCKY.INPthì chuyển việc đọc/ghi sang file, còn không (khi nộp lên OJ) thì vẫn đọc bàn phím như bình thường. - Biến
cntphải được gán lại bằng 0 ở đầu mỗi câu hỏi, nếu khai báo ngoài vòngwhilemà quên reset thì đáp án sẽ cộng dồn sai.
Kết quả chạy thật (mình đo thời gian CPU, giới hạn 1 giây): bản C++ đúng 17/20 test. Toàn bộ subtask 1 và 2 chạy dưới 0.01 giây. Ở subtask 3, các test 15–17 có $n \cdot Q$ từ $4.5 \cdot 10^8$ đến $1.35 \cdot 10^9$ mà vẫn qua (test 16 mất 0.66 giây) – vòng lặp so sánh quá đơn giản nên trình biên dịch tối ưu rất tốt, nhưng đây là "ăn may", máy chấm chậm hơn một chút là quá giờ. Còn test 18–20 có $n = Q = 10^5$ ($10^{10}$ phép so sánh) thì chắc chắn quá thời gian. Bản Python đúng 14/20 test (hết subtask 1, 2) và quá thời gian từ test 15. Vậy cách này chắc chắn được 70% điểm, có thể nhiều hơn một chút tuỳ máy chấm.
Ý tưởngĐếm trước một lần, tra cứu nhiều lần
Điểm yếu của cách 1 là cùng một dãy số mà mỗi câu hỏi lại đếm lại từ đầu. Thay vào đó, mình đếm trước tất cả các giá trị một lần duy nhất rồi ghi vào một "cuốn sổ": giá trị nào → xuất hiện mấy lần. Khi có câu hỏi $x$, chỉ việc mở sổ ra tra.
Nếu $a_i$ nhỏ (ví dụ $0 \le a_i \le 10^6$) thì cuốn sổ chính là mảng đếm dem[a[i]]++. Nhưng ở bài này $|a_i| \le 10^9$ và có cả số âm, không thể khai báo mảng 2 tỉ phần tử. Đó là lúc dùng map<int, int>:
map<int, int> cnt; hoạt động như một mảng mà chỉ số là bất kỳ số nguyên nào (âm, lớn tuỳ ý), và chỉ những chỉ số thực sự được dùng mới tốn bộ nhớ. cnt[v]++ tăng bộ đếm của $v$ (chưa có thì tự tạo bằng 0 rồi tăng), cnt.find(x) tìm $x$ trong $O(\log n)$. Các khoá trong map luôn được giữ tăng dần.Em nhập dãy và các câu hỏi rồi bấm Tiếp để xem cuốn sổ map được ghi và được tra như thế nào:
100%Cách 2: dùng map để đếm
- Vòng đọc dãy: mỗi số $v$ đọc vào làm
cnt[v]++. Sau vòng này,mapchứa đúng các giá trị khác nhau của dãy cùng số lần xuất hiện. - Khi trả lời, mình dùng
cnt.find(x)thay chocnt[x]. Viếtcout << cnt[x]cũng ra đúng 0, nhưng toán tử[]sẽ tạo thêm khoá $x$ vào map – với $10^5$ câu hỏi toàn số lạ thì map phình ra gấp đôi.findchỉ tìm, không thêm. it->secondlà phần giá trị (số lần xuất hiện) của phần tử màittrỏ tới;it->firstlà khoá.
Kết quả chạy thật: đúng 20/20 test, thời gian CPU lớn nhất chỉ 0.15 giây. Bản Python dùng dict cũng đúng 20/20 test, chậm nhất 0.16 giây. Mình có thể đổi map thành unordered_map (bảng băm, tra cứu trung bình $O(1)$), nhưng với $10^5$ phần tử thì map đã quá đủ nhanh.
100%Cách 3: sắp xếp + tìm kiếm nhị phân
Không dùng map cũng full điểm được! Sau khi sắp xếp tăng dần, các số bằng $x$ sẽ nằm liền nhau thành một đoạn. Hai hàm có sẵn trong C++ tìm 2 đầu đoạn đó bằng tìm kiếm nhị phân:
lower_bound(a, a + n, x): vị trí đầu tiên có giá trị $\ge x$.upper_bound(a, a + n, x): vị trí đầu tiên có giá trị $> x$.
Số phần tử bằng $x$ chính là r - l. Nếu $x$ không có trong dãy thì hai vị trí trùng nhau và hiệu bằng 0.
Kết quả chạy thật: đúng 20/20 test, thời gian CPU lớn nhất 0.07 giây; bản Python dùng bisect cũng 20/20 test, chậm nhất 0.28 giây. Cách này hữu ích khi các bạn chưa quen map, và cũng là nền tảng cho rất nhiều bài "đếm số phần tử trong đoạn $[L, R]$" sau này.
map): 20/20, tối đa 0.15 s. Cách 3 (sort + lower_bound/upper_bound): 20/20, tối đa 0.07 s. Bản Python của cách 2 và cách 3 cũng đều full điểm.
Nhận xét
Đăng nhận xét