Autumn Contest 2020 AC6
Đề bài
Bạn có một nền đất cần lát gạch có kích thước $1 \times N$ (gồm $N$ viên gạch hình vuông kích thước $1 \times 1$). Trên đó có những ô còn nguyên vẹn và những ô đã hỏng. Ta có $M$ ô gạch bị hỏng và các ô gạch bị hỏng được ký hiệu là #, các ô gạch nguyên vẹn được ký hiệu là .. Ta có 3 loại gạch men như sau:
- Loại 1: gạch men kích thước $1 \times 1$, chỉ được sử dụng để lát ô còn nguyên vẹn (
.) và độ thẩm mỹ khi lát 1 viên gạch loại 1 là $G_1$. Ngoài ra, ta chỉ có tối đa $K$ viên gạch loại 1. - Loại 2: gạch men kích thước $1 \times 2$, chỉ được sử dụng để lát 2 ô còn nguyên vẹn và liên tiếp với nhau (
..) và độ thẩm mỹ khi lát 1 viên gạch loại 2 là $G_2$. Các viên gạch loại 2 không giới hạn số lượng. - Loại 3: gạch men kích thước $1 \times 3$, chỉ được sử dụng để lát 3 ô gạch liên tục, trong đó ô chính giữa là ô gạch bị hỏng, và 2 viên bên cạnh là 2 ô nguyên vẹn (
.#.). Các viên gạch loại 3 không giới hạn số lượng. Độ thẩm mỹ khi lát 1 viên gạch loại 3 là $G_3$.
Bạn hãy tìm cách lát nền gạch sao cho độ thẩm mỹ là lớn nhất. Ta không được phép lát những viên gạch đặt chồng lên nhau, cũng không được phép chia nhỏ các viên gạch của các loại thành những phần nhỏ hơn. Biết rằng không bắt buộc phải lát toàn bộ $N$ ô gạch. Với mỗi ô gạch bị hỏng sau khi lát (vẫn còn hỏng, không được lát), độ thẩm mỹ sẽ giảm mất một lượng là $D$. Độ thẩm mỹ sẽ không thay đổi với các ô gạch còn nguyên vẹn nhưng không được lát.
Dữ liệu vào:
- Dòng đầu tiên gồm một số nguyên dương $T$ $(1 \le T \le 40)$ là số lượng bộ dữ liệu.
- $T$ bộ dữ liệu tiếp theo, mỗi bộ gồm: dòng 1 là 7 số nguyên $N, M, K, D, G_1, G_2, G_3$; dòng 2 là một chuỗi chỉ gồm các ký tự
.và#thể hiện trạng thái nền gạch, trong đó số ký tự#là $M$.
Dữ liệu ra: với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên là độ thẩm mỹ lớn nhất khi lát nền gạch.
Giới hạn: bài chia làm 2 Dataset: Small $M = 0$; Large $0 \le M \le 50$. Trong mọi Dataset: $1 \le K \le N \le 100\,000$, $0 \le D, G_1, G_2, G_3 \le 100$. Thời gian 1 giây / Dataset, bộ nhớ 512 MB / Dataset.
5
5 1 2 4 5 6 1
..#..
1 0 4 5 100 3 2
.
2 0 1 100 1 100 2
..
2 2 1 100 1 100 2
##
20 3 10 30 5 3 9
..#.....#...#.......12
100
100
-200
77Giải thích:
- Bộ 1 (
..#.., $K = 2$, $D = 4$, $G_1 = 5$, $G_2 = 6$, $G_3 = 1$): dùng 1 viên loại 2 lát ô 1, 2 và 2 viên loại 1 lát ô 4, 5. Ô 3 hỏng không được lát nên tổng là $6 + 2 \cdot 5 - 4 = 12$. - Bộ 2: chỉ có 1 ô nguyên vẹn, lát 1 viên loại 1 được 100.
- Bộ 3: chỉ có tối đa 1 viên loại 1 nên không lát được cả 2 ô bằng loại 1; dùng 1 viên loại 2 được 100.
- Bộ 4: nền gồm 2 ô hỏng, không lát được gì, độ thẩm mỹ là $-200$.
- Bộ 5: dùng để kiểm tra cách làm của bạn có đúng hay không.
Lời mở đầu
Bài này có 3 loại gạch, một giới hạn số viên loại 1 và các ô hỏng bị phạt – nghe thì rối, nhưng nếu tách từng phần ra thì rất gọn. Mình sẽ đi theo đúng 2 Dataset của đề: giải Small ($M = 0$) bằng một công thức đếm, rồi giải Large bằng QHĐ trên bảng $f[i][j]$ (vị trí, số viên loại 1 đã dùng), và cuối cùng là một cách QHĐ thông minh hơn chỉ chạy trên các ô hỏng – không phụ thuộc vào $K$.
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 chỉ có 2 file, mình tách từng bộ dữ liệu ra để thống kê:
| File test | Số bộ $T$ | $N$ | $M$ lớn nhất | Số bộ $M = 0$ | $K$ | $\sum N \cdot (K + 1)$ |
|---|---|---|---|---|---|---|
| 1 | 20 | 1.909 – 100.000 | 0 | 20 | 4 – 92 | 55.545.360 |
| 2 | 40 | 481 – 100.000 | 50 | 20 | 0 – 98 | 114.017.299 |
- File 1 (Small): 20 bộ, đều có $M = 0$ đúng như đề.
- File 2 (Large): 40 bộ, trong đó 20 bộ cuối chép y nguyên 20 bộ của file 1; 20 bộ đầu có $M$ từ 2 tới 50.
- Điều bất thường: mọi bộ đều có $K \le 98$ (nhỏ hơn rất nhiều so với giới hạn $K \le N = 100\,000$ của đề), và bộ thứ 1 của file 2 có $K = 0$ (trái với $1 \le K$). Vì $K$ nhỏ nên cột cuối $\sum N \cdot (K + 1)$ – số trạng thái của cách 2 – chỉ cỡ $10^8$ cho mỗi file, C++ chạy kịp trong 1 giây.
Kết quả chạy thật của các cách bên dưới (C++), tính cả theo file và theo từng bộ dữ liệu:
| Dataset | File | Cách 1 công thức $M = 0$ | Cách 2 QHĐ $O(N \cdot K)$ | Cách 3 QHĐ trên ô hỏng |
|---|---|---|---|---|
| Small ($M = 0$) | 1 | Đúng (20/20 bộ) | Đúng (20/20 bộ) | Đúng (20/20 bộ) |
| Large ($M \le 50$) | 2 | Sai (20/40 bộ) | Đúng (40/40 bộ) | Đúng (40/40 bộ) |
Ý tưởngQHĐ: xét ô cuối cùng
Gọi $f[i][j]$ = độ thẩm mỹ lớn nhất khi đã quyết định xong $i$ ô đầu tiên và đã dùng đúng $j$ viên loại 1. Nhìn vào ô thứ $i$, nó chỉ có thể là:
- không lát: $f[i-1][j]$, nếu ô $i$ hỏng thì trừ thêm $D$;
- ô $i$ là
., lát loại 1: $f[i-1][j-1] + G_1$ (cần $j \ge 1$); - ô $i-1, i$ là
.., lát loại 2: $f[i-2][j] + G_2$; - ô $i-2, i-1, i$ là
.#., lát loại 3: $f[i-3][j] + G_3$.
Em nhập nền gạch rồi bấm Tiếp để xem bảng $f$ được điền theo từng cột $i$: ô vàng là ô đang tính, các ô màu là các ô nó lấy giá trị (xanh lá: không lát, tím: loại 1, cam: loại 2, hồng: loại 3). Bước cuối truy vết lại cách lát tốt nhất:
Cách 1Small dataset ($M = 0$) – một công thức
Khi không có ô hỏng, nền là $N$ ô . liên tiếp, gạch loại 3 không dùng được. Giả sử dùng $x$ viên loại 1: đặt hết chúng ở cuối nền, phần đầu còn $N - x$ ô liên tiếp lát được $\lfloor (N - x)/2 \rfloor$ viên loại 2. Ta thử mọi $x$ từ 0 tới $\min(K, N)$:
min(K, N): không thể dùng nhiều viên loại 1 hơn số ô – nhớ là test ví dụ có $K > N$.- Code này bỏ qua hoàn toàn chuỗi
s, nên khi có ô hỏng thì sai.
Kết quả chạy thật: Bản C++ đúng 1/2 test, sai ở test 2; test đúng chạy lâu nhất 0.01s (file 1 đúng, file 2 sai – đúng 20/40 bộ, chính là 20 bộ $M = 0$ chép từ file 1). Bản Python đúng 1/2 test, sai ở test 2; test đúng chạy lâu nhất 0.02s.
Cách 2QHĐ $f[i][j]$ – đúng cả 2 file
Cài đặt công thức ở phần ý tưởng. Hàng $i$ chỉ dùng tới hàng $i-1, i-2, i-3$, nên ta chỉ giữ 4 hàng và đánh số hàng theo i % 4 (mảng lăn) – bộ nhớ $O(K)$ thay vì $O(N \cdot K)$.
NEG = INT_MIN / 2đánh dấu trạng thái không đạt được (ví dụ $f[0][j]$ với $j > 0$). Chia 2 để cộng/trừ thêm vài trăm không bị tràn số.- Ô hỏng chỉ có một lựa chọn là "không lát" ($-D$); gạch loại 3 được xét tại ô cuối của mẫu
.#.. - Số trạng thái là $N \cdot (K + 1)$. Trong bộ test $K < 100$ nên tổng cộng chỉ $\approx 169,6$ triệu trạng thái → chạy nhanh.
Kết quả chạy thật: Bản C++ đúng 2/2 test; test đúng chạy lâu nhất 0.31s. Bản Python đúng 0/2 test, quá thời gian ở test 1–2 (tách từng bộ thì bản Python chỉ 41/60 bộ chạy dưới 1 giây, lâu nhất 2,16 giây cho một bộ).
Cách 3QHĐ trên các ô hỏng – không phụ thuộc $K$
Ý tưởng là tách bài toán làm hai tầng:
Tầng 1 – mỗi ô hỏng: hoặc được lát bằng gạch loại 3 (được $G_3$, "ăn" thêm ô . ở hai bên), hoặc bị bỏ (mất $D$). Khi đã quyết định xong cho cả $M$ ô hỏng, các ô . còn lại tạo thành các đoạn liên tiếp, ta lát chúng bằng loại 1 và loại 2.
Tầng 2 – lát các đoạn .: giá trị tốt nhất chỉ phụ thuộc vào tổng số ô $P$ và số đoạn có độ dài lẻ $O$:
- Nếu chỉ dùng loại 2: mỗi đoạn dài $L$ được $\lfloor L/2 \rfloor$ viên, tổng cộng $(P - O)/2$ viên, thừa đúng $O$ ô lẻ.
- Dùng $x \le O$ viên loại 1: đặt vào $O$ ô thừa đó, không mất viên loại 2 nào.
- Dùng $x > O$ viên loại 1: phần thừa $x - O$ viên phải "phá" bớt $\lceil (x - O)/2 \rceil$ viên loại 2.
Gọi $X = \min(K, P)$. Hàm $g(x) = x \cdot G_1 + \text{số viên loại 2} \cdot G_2$ tăng trên $[0, O]$, còn sau $O$ thì cứ 2 bước lại cộng thêm cùng một lượng $2G_1 - G_2$ (lúc lên lúc xuống theo nhịp 2). Vì vậy giá trị lớn nhất nằm ở một trong các điểm $x \in \{0,\ \min(O, X),\ X,\ X - 1\}$ – chỉ cần thử 4 giá trị. Đó là hàm F(P, O).
QHĐ trên ô hỏng: gọi $gap_j$ là số ô . giữa ô hỏng $j-1$ và ô hỏng $j$. Duyệt các ô hỏng từ trái sang phải với trạng thái $(u, t, o)$: ô hỏng trước có dùng loại 3 không ($u$), đã dùng $t$ viên loại 3, đã có $o$ đoạn lẻ. Ô hỏng $j$ chọn $v \in \{0, 1\}$, đoạn bên trái nó còn $gap_j - u - v$ ô (phải $\ge 0$, nếu âm nghĩa là không đủ ô . để lát loại 3). Cuối cùng:
$$\text{đáp án} = \max_{(u, t, o)} \Big( t \cdot G_3 - (M - t) \cdot D + F\big(N - M - 2t,\ o'\big) \Big).$$
Có tối đa $2 \cdot 51 \cdot 52$ trạng thái cho mỗi ô hỏng, nên phần QHĐ chỉ $O(M^3)$, cộng $O(N)$ để đọc chuỗi.
if(!ok[u][t][o]) continue;); các trạng thái không đạt được bị bỏ qua cho đỡ dài. Hàm F được tính gộp 1 bước (xem khung cam).- Mảng
ok[u][t][o]chỉ cần lưu đạt được hay không (kiểuchar), vì giá trị cuối cùng được tính hoàn toàn từ $t$ và $o$. - Khi $M = 0$: vòng QHĐ không chạy, đáp án là $F(N, N \bmod 2)$ – chính là cách 1.
- Mình đã đối chiếu cách 2 và cách 3 với một chương trình vét cạn trên 6000 bộ ngẫu nhiên nhỏ ($N \le 14$, có cả $K = 0$): tất cả trùng khớp.
Kết quả chạy thật: Bản C++ đúng 2/2 test; test đúng chạy lâu nhất 0.01s. Bản Python đúng 2/2 test; test đúng chạy lâu nhất 0.24s. Full điểm, và chạy tức thì kể cả khi $K$ lớn.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất | Ghi chú |
|---|---|---|---|---|
| 1. Công thức cho $M = 0$ | C++ | 1/2 | 0.01s | Chỉ đúng Small dataset |
| Python | 1/2 | 0.02s | Chỉ đúng Small dataset | |
| 2. QHĐ $f[i][j]$ | C++ | 2/2 | 0.31s | Đúng cả 2 file nhờ $K < 100$ trong test |
| Python | 0/2 | > 1s | Quá thời gian cả 2 file | |
| 3. QHĐ trên ô hỏng | C++ | 2/2 | 0.01s | Full, không phụ thuộc $K$ |
| Python | 2/2 | 0.24s | Full |
.) bằng công thức – mới chắc chắn qua. Đây là một kỹ thuật rất hay: QHĐ trên những phần tử đặc biệt thay vì trên toàn bộ dãy.
Nhận xét
Đăng nhận xét