Phân tích: Space Emergency

Trong bài toán này, bạn có một chuỗi các cạnh cần đi qua và bạn có tùy chọn rút ngắn tối đa \(L\) cạnh bằng cách giảm thời gian di chuyển đi một nửa. Có một điểm mấu chốt: việc rút ngắn (xây dựng trạm tăng tốc) mất một khoảng thời gian \(t\) để có hiệu lực.

May mắn thay, tất cả các trạm tăng tốc đều mất cùng một lượng thời gian để xây dựng, vì vậy chúng ta có thể chia các cạnh thành ba loại:

1. Các cạnh mà soái hạm sẽ đi qua trước khi bất kỳ trạm tăng tốc nào có thể được xây dựng xong.
2. Cạnh mà trạm tăng tốc sẽ hoàn thành trong khi soái hạm đang di chuyển trên cạnh đó.
3. Các cạnh mà trạm tăng tốc có thể được xây dựng xong trước khi soái hạm tới đó.

Nhóm 2 chỉ có tối đa một thành viên, vì chúng ta biết chính xác soái hạm sẽ ở đâu khi các trạm tăng tốc hoàn thành việc xây dựng (tại thời điểm \(t\)).

Bây giờ chúng ta có thể quyết định mức độ hữu ích của việc xây dựng trạm tăng tốc trên mỗi cạnh. Chúng ta không bao giờ muốn xây dựng trạm tăng tốc trên nhóm 1, vì chúng sẽ không giúp ích gì. Đối với mỗi cạnh trong nhóm 3, lợi ích mang lại là độ dài / 2. Đối với cạnh trong nhóm 2, lợi ích là (khoảng cách còn lại của cạnh tính từ vị trí soái hạm khi trạm tăng tốc hoàn thành) / 2.

Chúng ta chọn \(L\) cạnh có lợi nhất để xây dựng; nếu không có đủ \(L\) cạnh mang lại lợi ích (lợi ích > 0), chúng ta sẽ dừng lại khi đã xây dựng trên tất cả các cạnh có lợi. Sau đó, chúng ta tính tổng lợi ích, trừ nó khỏi tổng thời gian để đi hết toàn bộ quãng đường với tốc độ bình thường (\(0,5\) parsec/giờ, tức là thời gian bằng \(2 \times\) quãng đường), và đó chính là kết quả!

Cách chỉ định các cạnh trong bài toán này có tính chu kỳ: nếu đầu vào rất lớn, sẽ có rất nhiều cạnh có cùng độ dài. Một giải pháp thông minh có thể tận dụng tính chất chu kỳ này để chạy rất nhanh, nhưng các giới hạn đề bài đủ nhỏ để điều này không thực sự cần thiết; thực tế chúng tôi chỉ định đầu vào theo cách này để làm cho tệp dữ liệu đầu vào nhỏ hơn, chứ không phải để kiểm tra kỹ năng cụ thể đó.

Dựa trên phân tích chính thức của Google Code Jam.