Trò Chơi Alice-Bob

Hướng tiếp cận

Bài toán trò chơi có chiến lược tối ưu. Mấu chốt là quan sát rằng mỗi vị trí được chọn đúng một lần, và ở mỗi vị trí người chơi chỉ cần đổi sang chữ cái có lợi nhất cho mình.

Nhận xét quan trọng

1. Vì mỗi vị trí chỉ được "chỉnh" một lần và có thể đổi sang bất kỳ chữ cái nào khác giá trị hiện tại, người đi vị trí $i$ luôn có thể chọn:
   • Alice (muốn nhỏ): chữ $\mathtt{\text{a}}$ — trừ khi $s_i=\mathtt{\text{a}}$, lúc đó chọn $\mathtt{\text{b}}$.
   • Bob (muốn lớn): chữ $\mathtt{\text{z}}$ — trừ khi $s_i=\mathtt{\text{z}}$, lúc đó chọn $\mathtt{\text{y}}$.
2. Ai đi vị trí nào? Vì hai bên có thể chọn vị trí, nhưng nội dung mỗi vị trí cuối cùng chỉ phụ thuộc người cuối cùng đặt nó (mỗi vị trí $1$ lượt) — và quan trọng hơn, Alice luôn có thể "chiếm" vị trí $1$ trước, sau đó Bob chiếm vị trí $2$, v.v. Vì lần lượt từ trái sang phải là thứ tự từ điển, không bên nào có lý do bỏ qua vị trí trái nhất chưa chỉnh để Bob/Alice chỉnh ngược ý mình.
3. Kết quả: vị trí $i$ (1-indexed) được chỉnh bởi Alice nếu $i$ lẻ, bởi Bob nếu $i$ chẵn.

Thuật toán

Duyệt từng ký tự của $s$:

• Nếu chỉ số (1-indexed) lẻ: thay $s_i$ bằng $\mathtt{\text{a}}$ (hoặc $\mathtt{\text{b}}$ nếu $s_i$ đã là $\mathtt{\text{a}}$).
• Nếu chỉ số chẵn: thay bằng $\mathtt{\text{z}}$ (hoặc $\mathtt{\text{y}}$ nếu $s_i$ đã là $\mathtt{\text{z}}$).

In xâu kết quả.

Độ phức tạp

• Thời gian: $O(|s|)$ cho mỗi test.
• Bộ nhớ: $O(|s|)$.