Hướng dẫn giải của Chạy Trên Vòng Tròn

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Bò Chạy

Hướng tiếp cận

Bài toán là cây AND/OR: FJ (OR node) chọn B hoặc T để đảm bảo thắng, Bessie (AND node) cần cả hai lựa chọn đều dẫn đến thắng. Giải đệ quy từ trên xuống với short-circuit evaluation ngẫu nhiên để tối ưu hóa thực tế.

Nhận xét quan trọng

Cấu trúc cây AND/OR với chiều sâu $N \leq 14$ : tại mỗi vòng, FJ chọn (OR), Bessie phản ứng (AND). Tổng số nút cây là $O (4^{N})$ nhưng short-circuit cắt tỉa rất mạnh.
FJ muốn chiến lược từ điển nhỏ nhất: thử B trước (vì B < T). Nếu B đảm bảo thắng thì chọn B; ngược lại thử T.
Công thức cập nhật vị trí: $R \leftarrow (R \times (1 + X_{t o p}) + X_{b o t}) mod M$ . Dùng __int128 để tránh tràn số khi $R$ và $X$ lên tới $10^{9}$ .
Ngẫu nhiên hóa thứ tự kiểm tra lựa chọn của Bessie giúp tăng tốc tìm kiếm (nếu một lựa chọn thua, trả về sớm).

Thuật toán

Đọc $N$ , $M$ , $K$ , chuỗi nước đi của Bessie, và 8 giá trị lá bài mỗi vòng.
Định nghĩa check_fj(round, R, fj): kiểm tra nếu FJ chọn fj (0=T, 1=B), thì với mọi lựa chọn của Bessie, kết quả đều thắng (AND). Nếu là vòng cuối kiểm tra winning(R_new), ngược lại đệ quy can_win(round+1, R_new).
Định nghĩa can_win(round, R): thử B trước (fj=1), nếu check_fj trả về true thì thắng; ngược lại thử T.
Mô phỏng thực tế: tại vòng $i$ , thử B trước; nếu check_fj(i, R, 1) thì ghi 'B', theo dõi nước đi thực của Bessie để cập nhật $R$ ; ngược lại ghi 'T'.
In chuỗi nước đi của FJ.

Độ phức tạp

Thời gian: $O (2^{N})$ trong trường hợp xấu nhất (cây AND/OR đầy đủ), nhưng short-circuit cắt tỉa mạnh trong thực tế
Bộ nhớ: $O (N)$ (chiều sâu đệ quy)

Bình luận

Không có bình luận tại thời điểm này.