LONG XAU
Đề bài
Bài 3. LONGXAU
Trong quá trình khám phá ngôi nhà, Long bất ngờ vào được phòng riêng của nhà toán học. Ở đây, cậu tìm được một bức thư mà nhà toán học gửi cho người yêu của mình. Tuy nhiên, bức thư được mã hoá nên cậu cần tìm cách để giải mã nó:
Bức thư là 1 xâu gồm $N$ kí tự. Mỗi kí tự có thể là kí tự 'a', 'b' hoặc '?'. Để giải mã, ta có thể thay thế những kí tự '?' trong xâu ban đầu thành kí tự 'a' hoặc kí tự 'b'. Giả sử chúng ta đã thay thế hết các kí tự '?', thì với mỗi cặp hai kí tự liền kề trong xâu ban đầu, chúng ta định nghĩa giá trị của cặp đó như sau:
'aa'= 0'ab'= 1'bb'= 0'ba'= −1
Tổng giá trị của một xâu là tổng giá trị của tất cả $N - 1$ cặp hai kí tự liền kề.
Yêu cầu: Trong tất cả các cách thay thế những kí tự '?' trong xâu ban đầu, hãy in ra tổng giá trị lớn nhất có thể, từ đó có thể giải được bức thư. Các bạn hãy giúp Long nhé!
Dữ liệu: Vào từ file LONGXAU.INP gồm:
- Dòng đầu tiên chứa một số nguyên $N$ $(1 \le N \le 10^6)$.
- Dòng tiếp theo chứa một xâu gồm $N$ kí tự, mỗi kí tự có thể là kí tự
'a','b'hoặc'?'.
Kết quả: Ghi ra file LONGXAU.OUT một số nguyên duy nhất là tổng giá trị lớn nhất có thể trong tất cả các cách thay thế.
Ràng buộc:
- 50% số điểm có $N \le 20$;
- 50% số điểm còn lại, không có ràng buộc gì thêm.
5
aabbb16
a?a?bb1if (fopen("LONGXAU.INP", "r")) { freopen(...); freopen(...); }: có file thì đọc/ghi file, không có file thì đọc bàn phím, in ra màn hình – nộp kiểu nào cũng chạy được.Lời mở đầu
Thoạt nhìn bài này giống bài "thử mọi cách điền dấu ?" – mà có tới hàng trăm nghìn dấu ? thì $2^q$ cách là không tưởng. Nhưng chỉ cần nhìn kỹ bảng giá trị 4 cặp là sẽ thấy một điều bất ngờ: tổng của cả xâu chỉ phụ thuộc vào ký tự đầu và ký tự cuối! Mình sẽ đi từ vét cạn (ăn 50%), qua quy hoạch động $O(N)$, tới lời giải tham lam chỉ vài dòng.
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ì?
Bộ test có 10 test (không chứa 2 ví dụ của đề):
| Test | N | Số dấu ? | Ký tự đầu | Ký tự cuối | Đáp án |
|---|---|---|---|---|---|
| 1 | 20 | 6 | ? | a | 0 |
| 2 | 20 | 6 | a | a | 0 |
| 3 | 20 | 5 | b | a | -1 |
| 4 | 20 | 5 | b | b | 0 |
| 5 | 20 | 8 | ? | b | 1 |
| 6 | 908.285 | 302.850 | b | b | 0 |
| 7 | 987.897 | 328.910 | b | a | -1 |
| 8 | 905.042 | 301.592 | b | ? | 0 |
| 9 | 988.142 | 329.391 | a | ? | 1 |
| 10 | 993.411 | 331.309 | a | a | 0 |
Đối chiếu với ràng buộc của đề: test 1–5 có $N = 20$ (subtask 1), test 6–10 có $N$ gần $10^6$ với khoảng một phần ba là dấu ? (subtask 2). Đáp án chỉ là −1, 0 hoặc 1 – để ý cột ký tự đầu/cuối, các bạn sẽ đoán ra quy luật ngay!
| Subtask | Đề ghi | Test | Cách 1 vét cạn | Cách 2 QHĐ | Cách 3 tham lam |
|---|---|---|---|---|---|
| 1 (50%) | $N \le 20$ | 1–5 | 5/5 | 5/5 | 5/5 |
| 2 (50%) | $N \le 10^6$ | 6–10 | 0/5 | 5/5 | 5/5 |
Ý tưởngTổng "rút gọn": chỉ còn đầu và cuối
Gán cho mỗi ký tự một "độ cao": $h(\texttt{a}) = 0$, $h(\texttt{b}) = 1$. Kiểm tra lại bảng giá trị:
| Cặp $xy$ | Giá trị đề cho | $h(y) - h(x)$ |
|---|---|---|
aa | 0 | 0 − 0 = 0 |
ab | 1 | 1 − 0 = 1 |
bb | 0 | 1 − 1 = 0 |
ba | −1 | 0 − 1 = −1 |
Khớp cả 4! Vậy giá trị cặp $(s_i, s_{i+1})$ chính là $h(s_{i+1}) - h(s_i)$, và khi cộng tất cả các cặp, các số hạng ở giữa triệt tiêu nhau:
$$\big(h(s_2) - h(s_1)\big) + \big(h(s_3) - h(s_2)\big) + \ldots + \big(h(s_N) - h(s_{N-1})\big) = h(s_N) - h(s_1).$$
b) và $h(s_1)$ nhỏ (ký tự đầu là a). Vậy: dấu ? ở đầu điền a, dấu ? ở cuối điền b, các dấu ? ở giữa điền gì cũng được. Đáp án $= [s_N \ne \texttt{a}] - [s_1 = \texttt{b}]$. Riêng $N = 1$ không có cặp nào nên đáp án là 0.Hiểu nôm na: đi dọc xâu, mỗi lần "leo" từ a lên b được +1, mỗi lần "tụt" từ b xuống a bị −1. Leo bao nhiêu lần thì cũng phải tụt gần bấy nhiêu lần – cuối cùng chỉ còn chênh lệch giữa độ cao điểm cuối và điểm đầu.
Em nhập xâu rồi bấm Tiếp để xem từng cặp góp vào tổng và "độ cao" thay đổi thế nào:
Cách 1Vét cạn mọi cách điền – Subtask 1
Với $N \le 20$ thì có tối đa $2^{20} \approx 10^6$ cách điền. Ta lưu vị trí các dấu ? vào mảng q, rồi đệ quy: dấu ? thứ k thử điền 'a' rồi thử 'b'. Khi điền xong hết (k == q.size()) thì tính tổng giá trị của xâu bằng hàm tinh() và cập nhật best.
bestkhởi tạoINT_MINvì đáp án có thể âm (ví dụ xâu bắt đầu bằngb, kết thúc bằngacho −1).- Hàm
tinh()đi qua $N - 1$ cặp liền kề, gặpabthì +1, gặpbathì −1, cònaa,bbkhông đổi. - Bản Python dùng
itertools.product('ab', repeat=len(q))để sinh mọi cách điền thay cho đệ quy.
Kết quả chạy thật: bản C++ đúng 5/10 test (sai ở test 6–10), test đúng lâu nhất 0.006s; bản Python đúng 5/10 test (quá thời gian ở test 6–10), test đúng lâu nhất 0.026s. Ở subtask 2 có tới khoảng $3 \cdot 10^5$ dấu ?: bản C++ đệ quy sâu chừng ấy tầng nên bị tràn ngăn xếp (lỗi chạy – RE) ngay lập tức; mà kể cả không tràn thì $2^{300000}$ cách cũng không bao giờ chạy xong.
Cách 2Quy hoạch động 2 trạng thái – Full điểm
Nếu chưa nhìn ra mẹo "rút gọn" thì vẫn có cách $O(N)$ rất tự nhiên: khi đi từ trái sang phải, giá trị của cặp tiếp theo chỉ phụ thuộc vào ký tự vừa chọn. Nên ta chỉ cần nhớ 2 số:
fa= tổng lớn nhất của đoạn $s_0..s_i$ nếu $s_i$ được chọn làa;fb= tổng lớn nhất nếu $s_i$ được chọn làb.
Chuyển sang ký tự $i + 1$: nếu nó được phép là a (tức là a hoặc ?) thì $fa' = \max(fa + 0,\ fb - 1)$; nếu được phép là b thì $fb' = \max(fa + 1,\ fb + 0)$. Ký tự không được phép thì gán "âm vô cùng" NEG.
Kết quả chạy thật: bản C++ đúng 10/10 test, test đúng lâu nhất 0.012s; bản Python đúng 10/10 test, test đúng lâu nhất 0.489s.
Cách 3Tham lam: chỉ nhìn đầu và cuối – Full điểm
Cài đặt đúng công thức ở phần ý tưởng: đáp án $= [s_{N-1} \ne \texttt{a}] - [s_0 = \texttt{b}]$ (đánh số từ 0). Ký tự cuối là b hoặc ? (điền b) thì được 1; ký tự đầu là b thì mất 1 (nếu là ? thì điền a, không mất gì).
- Nhớ trường hợp
n == 1: xâu"?"mà dùng công thức sẽ ra $1 - 0 = 1$ (vì coi dấu?vừa làbở cuối vừa làaở đầu) – sai, vì không có cặp nào nên đáp án phải là 0. - Thử lại với ví dụ 2
a?a?bb: đầu làa, cuối làb→ $1 - 0 = 1$. Đúng!
Kết quả chạy thật: bản C++ đúng 10/10 test, test đúng lâu nhất 0.007s; bản Python đúng 10/10 test, test đúng lâu nhất 0.033s. Thời gian gần như chỉ là thời gian đọc xâu $10^6$ ký tự.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Test đúng lâu nhất | Ghi chú |
|---|---|---|---|---|
| 1. Vét cạn $O(2^q \cdot N)$ | C++ | 5/10 | 0.006s | Test 6–10: đệ quy sâu ~3·10^5 tầng → tràn ngăn xếp (mà có chạy được thì 2^300000 cũng không bao giờ xong) |
| Python | 5/10 | 0.026s | Quá thời gian test 6–10 | |
| 2. QHĐ 2 trạng thái $O(N)$ | C++ | 10/10 | 0.012s | Full điểm |
| Python | 10/10 | 0.489s | Full điểm | |
| 3. Tham lam $O(N)$ đọc, $O(1)$ tính | C++ | 10/10 | 0.007s | Full điểm |
| Python | 10/10 | 0.033s | Full điểm |
Nhận xét
Đăng nhận xét