Phân tích

Câu hỏi nhanh nào, các tay lái cừ khôi! Thoạt nhìn bài toán có vẻ khá phức tạp. Ta nên làm gì?

Một chiến lược tự nhiên là tìm kiếm nhị phân tốc độ của Annie, nhưng rất khó kiểm tra trực tiếp một tốc độ có tránh vượt ngựa khác hay không. Chỉ từ đầu vào, ta không biết vị trí mỗi con tại mọi thời điểm vì các con ngựa có thể làm nhau chậm lại. Về lý thuyết, có thể tính lúc ngựa nhanh bắt kịp ngựa chậm, xác định chính xác quỹ đạo từng con, rồi kiểm tra tốc độ đã chọn có cắt quỹ đạo nào không. Với nhiều nhất hai con ở Test Set 1 thì khả thi, nhưng sẽ rất vất vả ở Test Set 2.

Ta tránh toàn bộ công việc đó bằng vài nhận xét. Để tối đa hóa tốc độ, ngựa của Annie nên tới đích đúng lúc con ngựa phía trước cô (gọi là A) tới nơi; không có lý do để chừa khoảng trống. Hoặc A tới đích mà không phải giảm tốc, và trực tiếp giới hạn tốc độ Annie; hoặc tại một lúc nào đó A bị con phía trước (gọi là 😎 làm chậm. Với B cũng vậy: hoặc nó không bao giờ phải giảm tốc và cuối cùng giới hạn Annie, hoặc lại bị con phía trước nữa làm chậm. Vì thế có một con ngựa giới hạn duy nhất trên đường quyết định Annie có thể tới đích nhanh đến đâu. Ta khẳng định chỉ con này quan trọng và có thể bỏ qua tất cả con khác.

Dễ thấy có thể bỏ qua các con ở phía đông của ngựa giới hạn: chúng sẽ tới và đi qua đích trước nó. Còn các con trung gian giữa Annie và ngựa giới hạn thì sao? Theo cách định nghĩa, mọi con trung gian sẽ bắt kịp ngựa giới hạn trước đích; nếu một con không bắt kịp thì chính nó mới là ngựa giới hạn.

Giả sử Annie chọn tốc độ khiến cô tới đích đúng lúc ngựa giới hạn. Chắc chắn không thể đi nhanh hơn. Hơn nữa, tốc độ này an toàn: Annie không thể vượt bất kỳ con trung gian nào. Nếu đủ nhanh để vượt một con trung gian, cô chắc chắn cũng đủ nhanh để vượt ngựa giới hạn, vì con trung gian ấy sẽ bắt kịp ngựa giới hạn — mâu thuẫn. Do đó không cần quan tâm các con trung gian hay tương tác giữa chúng.

Khi đã xác định ngựa giới hạn, chiến lược rất đơn giản: đi với đúng tốc độ khiến Annie tới đích cùng lúc với nó. Tốc độ này tính được trong thời gian hằng số. Ta có thể xác định trực tiếp con giới hạn bằng lập luận trên, nhưng ngay cả việc đó cũng thừa. Thay vào đó, lần lượt giả sử từng con là ngựa giới hạn và tính tốc độ nó áp đặt; lấy tốc độ nhỏ nhất. Nếu một con cho phép tốc độ lớn hơn con khác thì nó không thể là con giới hạn thật, vì tốc độ đó sẽ khiến Annie vượt con giới hạn thật.

Với con \(i\), thời gian tự nó cần để tới đích là

Tốc độ mà nó áp đặt cho Annie là \(D/t_i\). Vì thế có thể lấy \(t=\max_i t_i\) rồi trả về

Thuật toán chạy trong \(O(N)\) thời gian.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2017, Round 1B, bài Steed 2: Cruise Control.