Cổ phiếu VNI
Đề bài
Bình mua bán cổ phiếu VNI trên thị trường chứng khoán. Giả sử giá của một cổ phiếu VNI trong vòng $N$ ngày lần lượt là $A_1, A_2, \ldots, A_N$. Biết rằng mỗi ngày Bình chỉ thực hiện một trong những hoạt động sau:
- Mua một cổ phiếu VNI;
- Bán số lượng cổ phiếu VNI bất kì mà Bình đang sở hữu;
- Không thực hiện bất kì giao dịch nào.
Yêu cầu: Bình thực hiện mua bán cổ phiếu VNI như thế nào để thu được lợi nhuận lớn nhất nếu anh ấy tham gia mua bán bắt đầu từ ngày thứ $T$ cho trước?
Dữ liệu vào:
- Dòng đầu tiên gồm số nguyên dương $N$ $(N \le 10^5)$ là số ngày biết giá cổ phiếu;
- Dòng thứ hai gồm $N$ số nguyên dương $A_1, A_2, \ldots, A_N$ tương ứng là giá của một cổ phiếu VNI trong từng ngày $(A_i \le 10^9;\ 1 \le i \le N)$;
- Dòng thứ ba gồm một số nguyên dương $Q$ là số lượng truy vấn $(Q \le 10^5)$;
- $Q$ dòng sau, mỗi dòng gồm một số nguyên dương $T$ $(T \le N)$ thể hiện cho ngày đầu tiên mà Bình tham gia việc mua bán cổ phiếu VNI.
Kết quả: $Q$ dòng, mỗi dòng gồm một số nguyên duy nhất là lợi nhuận lớn nhất mà Bình thu được ở mỗi truy vấn tương ứng.
Ràng buộc:
- Có 50% số test ứng với 50% số điểm của bài thoả mãn: $N \le 1000;\ Q = 1$;
- 30% số test khác ứng với 30% số điểm của bài thoả mãn: $N \le 10^5;\ Q = 1$;
- 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.
4
1 2 5 4
2
1
37
0Giải thích:
- Bình bắt đầu tham gia mua bán VNI vào ngày 1: ngày 1 mua 1 VNI với giá 1; ngày 2 mua 1 VNI với giá 2; ngày 3 bán 2 VNI với giá 5; ngày 4 không mua hay bán. Lợi nhuận thu được là $-1 - 2 + 2 \times 5 = 7$.
- Bình bắt đầu tham gia mua bán VNI vào ngày 3: Bình không mua bán VNI vào ngày 3 và ngày 4. Lợi nhuận thu được là 0.
Lời mở đầu
Bài này có 2 lớp khó: tìm ra cách mua bán tốt nhất cho một ngày bắt đầu $T$, rồi trả lời $10^5$ truy vấn thật nhanh. Mình sẽ đi đúng lộ trình của chương quy hoạch động: vét cạn mọi cách giao dịch → QHĐ theo "số cổ phiếu đang giữ" → nhận xét để còn $O(N)$ mỗi truy vấn → QHĐ trên hậu tố để trả lời mỗi truy vấn trong $O(1)$. Mỗi cách đều chạy thật trên bộ test của CLUE để các bạn thấy nó ăn được subtask nào.
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 OJLộ 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$ | $A_i$ lớn nhất | Đáp án lớn nhất |
|---|---|---|---|---|
| 1–10 | 2 … 14 | 1 | 20 | 81 |
| 11–50 | 1.000 | 1 | 500.032.748 | 423.662.542.621 |
| 51–80 | 100.000 | 1 | 500.032.768 | 43.387.518.487.901 |
| 81–100 | 100.000 | 100.000 | 500.032.768 | 43.986.491.391.147 |
- 100 test khớp 3 subtask của đề: test 1–50 có $Q = 1$, $N \le 1000$ (trong đó 10 test đầu $N \le 14$); test 51–80 có $Q = 1$, $N = 10^5$; test 81–100 có $N = Q = 10^5$, ngày $T$ trải từ 1 đến $N$.
- Đáp án lớn tới khoảng $4{,}4 \cdot 10^{13}$ (lớn nhất là 43.986.491.391.147) – vượt xa
int, bắt buộc dùnglong long. Riêng tíchcnt * a[i]cũng phải tính bằnglong long. - Có test đáp án bằng 0 (giá chỉ giảm từ ngày $T$ trở đi) – lúc đó tốt nhất là không giao dịch.
Ba subtask và số test đúng của từng cách (chạy thật):
| Subtask | Điều kiện | Các test | Cách 1 đệ quy | Cách 2 QHĐ số cổ phiếu | Cách 3 $O(N)$ / truy vấn | Cách 4 $O(1)$ / truy vấn |
|---|---|---|---|---|---|---|
| 1 (50%) | $N \le 1000,\ Q = 1$ | 1 – 50 | 12/50 | 50/50 | 50/50 | 50/50 |
| 2 (30%) | $N \le 10^5,\ Q = 1$ | 51 – 80 | 0/30 | 0/30 | 30/30 | 30/30 |
| 3 (20%) | $N, Q \le 10^5$ | 81 – 100 | 0/20 | 0/20 | 0/20 | 20/20 |
(Số test đúng của bản C++, chạy thật với giới hạn 1 giây/test.)
Ý tưởngMỗi cổ phiếu bán ở giá cao nhất phía sau
Xét riêng một cổ phiếu mua ở ngày $i$ với giá $A_i$. Sớm muộn gì nó cũng được bán ở một ngày $j > i$ nào đó, giá $A_j$ không thể vượt quá
nên cổ phiếu này lãi nhiều nhất $M[i] - A_i$. Mỗi ngày mua tối đa 1 cổ phiếu, vậy tổng lãi không thể vượt $\sum_{i \ge T} (M[i] - A_i)$. Và ta đạt được đúng con số đó: ngày nào $A_i < M[i]$ thì mua 1 cổ phiếu; ngày nào giá bằng đúng $M[i]$ (một "đỉnh" – không có ngày nào phía sau đắt hơn) thì bán sạch số đang giữ. Mọi cổ phiếu mua giữa 2 đỉnh liên tiếp đều có cùng $M[i]$ bằng giá của đỉnh sau, nên đều được bán đúng giá cao nhất của nó.
Em nhập giá các ngày và các ngày bắt đầu $T$, rồi bấm Tiếp để xem bảng $M$, lãi từng ngày và $f$ được điền từ phải sang trái, sau đó trả lời từng truy vấn kèm kế hoạch mua bán cụ thể:
Cách 1Đệ quy thử mọi cách giao dịch
Chưa cần nhận xét gì: mỗi ngày có 3 lựa chọn (mua 1, bán hết, không làm gì), cứ thử hết. Hàm Try(i, cnt, money) đang ở ngày $i$, giữ $cnt$ cổ phiếu, lãi hiện tại $money$. (Bán "một phần" không bao giờ tốt hơn bán hết hoặc giữ hết ở ngày đó, nên chỉ cần 3 lựa chọn này – đây cũng chính là kế hoạch tối ưu ở phần ý tưởng.)
Kết quả chạy thật: bản C++ đúng 12/100 test, quá thời gian ở các test 11–41, 43–47, 49–100; test đúng chạy lâu nhất 0,065 s. $3^{14} \approx 4{,}8$ triệu nhánh vẫn kịp, nhưng $N = 1000$ thì $3^{1000}$ – không bao giờ xong (2 test may mắn qua được là vì ngày $T$ chỉ cách ngày cuối khoảng 10 ngày). Bản Python (chỉ chạy test 1–20) đúng 10/20 test, quá thời gian ở các test 11–20; test đúng chạy lâu nhất 0,022 s.
Cách 2QHĐ theo ngày và số cổ phiếu đang giữ (subtask 1)
Ở cách 1, hai nhánh cùng đến ngày $i$ với cùng số cổ phiếu $k$ thì nhánh nào lãi ít hơn có thể bỏ. Vậy trạng thái chỉ cần $(i, k)$:
- không giao dịch: $nd[k] \leftarrow dp[k]$;
- mua 1: $nd[k] \leftarrow dp[k-1] - A_i$;
- bán hết: $nd[0] \leftarrow dp[k]$ $+ k \cdot A_i$.
- Giá trị
NEGđánh dấu trạng thái "không thể xảy ra". ChọnLLONG_MIN / 4để trừ thêm vài giá vẫn không tràn số. - Sau ngày thứ $c$ (tính từ $T$) chỉ giữ được tối đa $c$ cổ phiếu, nên vòng $k$ chỉ chạy tới $c$.
- Kết thúc in $dp[0]$: giữ lại cổ phiếu đến cuối không có lợi gì (bán ngày cuối còn hơn).
Kết quả chạy thật: bản C++ đúng 50/100 test, quá thời gian ở các test 51–100; test đúng chạy lâu nhất 0,005 s. $N = 1000$ chỉ khoảng $5 \cdot 10^5$ phép tính; nhưng $N = 10^5$ là $5 \cdot 10^9$ – quá thời gian. Bản Python (chạy test 1–60) đúng 50/60 test, quá thời gian ở các test 51–60; test đúng chạy lâu nhất 0,128 s.
Cách 3Max hậu tố – O(N) mỗi truy vấn (subtask 1, 2)
Dùng nhận xét ở phần ý tưởng: đi ngược từ ngày $N$ về ngày $T$, giữ $mx$ là giá cao nhất từ ngày đang xét trở đi, cộng dồn $mx - A_i$.
Kết quả chạy thật: bản C++ đúng 80/100 test, quá thời gian ở các test 81–100; test đúng chạy lâu nhất 0,012 s. Với $Q = 1$ thì quá nhanh, nhưng subtask 3 có $Q = N = 10^5$: $10^{10}$ phép tính – quá thời gian. Bản Python đúng 80/100 test, quá thời gian ở các test 81–100; test đúng chạy lâu nhất 0,038 s.
Cách 4QHĐ trên hậu tố – O(1) mỗi truy vấn (full điểm)
Để ý: kết quả của cách 3 với ngày bắt đầu $T$ chính là tổng các số hạng $M[i] - A_i$ với $i \ge T$, mà $M[i]$ không phụ thuộc $T$. Nên ta tính sẵn $f[i]$ cho mọi $i$ trong một lượt đi ngược, rồi trả lời mỗi truy vấn bằng $f[T]$.
Kết quả chạy thật: bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0,024 s. Bản Python đúng 100/100 test; test đúng chạy lâu nhất 0,088 s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất (test đúng) | Ghi chú |
|---|---|---|---|---|
| 1. Đệ quy 3 lựa chọn | C++ | 12/100 | 0,065 s | Quá thời gian ở test 11–41, 43–47, 49–100 |
| Python (test 1–20) | 10/20 | 0,022 s | Quá thời gian ở test 11–20 | |
| 2. QHĐ dp[ngày][số cổ phiếu] | C++ | 50/100 | 0,005 s | Quá thời gian ở test 51–100 |
| Python (test 1–60) | 50/60 | 0,128 s | Quá thời gian ở test 51–60 | |
| 3. Max hậu tố, O(N) mỗi truy vấn | C++ | 80/100 | 0,012 s | Quá thời gian ở test 81–100 |
| Python | 80/100 | 0,038 s | Quá thời gian ở test 81–100 | |
| 4. QHĐ hậu tố f[i], O(1) mỗi truy vấn | C++ | 100/100 | 0,024 s | Full điểm |
| Python | 100/100 | 0,088 s | Full điểm |
long long – đáp án vượt $4 \cdot 10^{13}$.