Trò Chơi Bài (Platinum)

Lời giải: Trò Chơi Bài Hai Luật

Hướng tiếp cận

Bài toán yêu cầu tìm điểm tối đa khi người A có thể đổi từ "bài cao thắng" sang "bài thấp thắng" đúng một lần ở bất kỳ vòng nào.

Gọi điểm đổi luật là sau vòng $i$ (với $0\le i\le N$, $i=0$ nghĩa là đổi luật ngay từ đầu). Khi đó:

• $N$ vòng đầu (vòng 1 đến $i$): luật "bài cao thắng".
• $N-i$ vòng sau (vòng $i+1$ đến $N$): luật "bài thấp thắng".

Đáp án = ${max}_{0\le i\le N}(\text{prefix}[i]+\text{suffix}[i])$

trong đó:

• $\text{prefix}[i]$ = số điểm tối đa người A giành được trong $i$ vòng đầu với luật "bài cao thắng", dùng $i$ lá bài cao nhất của mình.
• $\text{suffix}[i]$ = số điểm tối đa người A giành được trong $N-i$ vòng cuối với luật "bài thấp thắng", dùng $N-i$ lá bài thấp nhất của mình.

Nhận xét quan trọng

1. Phân chia bài tối ưu: Trong đoạn "bài cao thắng", người A nên dùng $i$ lá bài lớn nhất; trong đoạn "bài thấp thắng", nên dùng $N-i$ lá bài nhỏ nhất. Đây là vì không có lý gì dùng một lá bài nhỏ để cố đánh bại ở đoạn cao-thắng khi đã có bài lớn hơn.

2. Tính prefix: Với $i$ vòng đầu (người B đánh $a_1,a_2,\dots ,a_i$) và $i$ lá bài lớn nhất của người A, dùng chiến lược tham lam: dùng lá bài nhỏ nhất lớn hơn lá của B (nếu có).

3. Tính suffix: Với $N-i$ vòng cuối (người B đánh $a_{i+1},\dots ,a_N$ theo thứ tự ngược) và $N-i$ lá bài nhỏ nhất của người A (theo thứ tự ngược), dùng chiến lược đối xứng.

Thuật toán

Để tính $\text{prefix}[]$ và $\text{suffix}[]$ hiệu quả, ta dùng Segment Tree trên không gian lá bài $[1.\mathrm{.2}N]$.

Cấu trúc nút Segment Tree:

• covers: số lá bài của người A trong đoạn này chưa được sử dụng (lá bài có thể "che" bài của B).
• coverables: số lá bài của người B trong đoạn này chưa được "che".
• points: số điểm đã ghi nhận trong đoạn này.

Kết hợp hai nút (trái $x$, phải $y$):

ep = min(x.coverables, y.covers)   // bài B phía trái được che bởi bài A phía phải
points = x.points + y.points + ep
covers = x.covers + y.covers - ep
coverables = x.coverables + y.coverables - ep

Tính prefix[i]:

• Lấy $i$ lá bài lớn nhất của người A (đây là những lá bài không thuộc dãy B, theo thứ tự giảm dần).
• Với $j=1,2,\dots ,N$: chèn lá bài $B[j]$ vào vị trí tương ứng trong segment tree (gắn coverables = 1), đồng thời chèn lá bài lớn thứ $j$ của người A (gắn covers = 1). Sau mỗi bước, $\text{prefix}[j]=\text{root.points}$.

Tính suffix[i]: Làm tương tự nhưng theo chiều ngược (vòng cuối trước, luật thấp thắng). Đổi biến: thay mỗi lá bài $v$ bằng $2N+1-v$ để quy về bài "thấp thắng" thành "cao thắng". Dùng lá bài nhỏ nhất của người A, xử lý từ vòng $N$ ngược về $1$.

Kết quả: ${max}_{i=0}^N(\text{prefix}[i]+\text{suffix}[N-i])$

Độ phức tạp

• Thời gian: $O(N\log N)$ — mỗi thao tác chèn vào segment tree mất $O(\log N)$, thực hiện $O(N)$ lần cho cả prefix và suffix.
• Bộ nhớ: $O(N)$.