Phân tích

Gọi các chỉ số thưởng của một lá bài \(c\) là c.card_draw, c.score và c.turns. Gọi c.index là chỉ số (bắt đầu từ 0) của lá bài theo thứ tự xuất hiện trong dữ liệu đầu vào.

Dựa trên các ràng buộc của bài toán, chúng ta có thể phân loại một lá bài \(c\) thành:

• Lá bài T: nếu c.turns > 0.
• Lá bài C₀: nếu c.turns = 0 và c.card_draw = 0.
• Lá bài C₁: nếu c.turns = 0 và c.card_draw = 1.
• Lá bài C₂: nếu c.turns = 0 và c.card_draw = 2.

Gọi \(T[i]\) là lá bài T thứ \(i\) trong dãy tất cả các lá bài T được sắp xếp theo chỉ số. Chúng ta định nghĩa \(C_0[i]\), \(C_1[i]\) và \(C_2[i]\) một cách tương tự.

Quan sát quan trọng đầu tiên là việc đánh một lá bài T bất cứ khi nào có trong tay không bao giờ gây hại. Chúng ta không bao giờ mất lượt hay mất điểm, và chúng ta có thể rút thêm các lá bài mới bằng cách làm như vậy.

Xét một chuỗi các lá bài được đánh bất kỳ. Có hai quan sát cần thực hiện:

1. Vì các lá bài \(C_0\) không thêm lượt hay thêm bài vào tay, chúng ta có thể trì hoãn việc đánh chúng cho đến khi không còn lá bài nào khác muốn đánh. Do đó, bất kỳ chuỗi đánh bài hợp lệ nào cũng có thể biến đổi thành một chuỗi khác có tất cả các lá bài \(C_0\) ở cuối cùng. Tổng điểm vẫn giữ nguyên.
2. Giả sử có hai lá bài \(C_1\) là \(a\) và \(b\) sao cho ta đánh \(a\) trước \(b\), nhưng b.index < a.index. Vì b.index < a.index, ta đã có cả hai lá bài trong tay khi đánh lá \(a\). Do đó, ta có thể đánh lá \(b\) trước và lá \(a\) sau. Chuỗi kết quả vẫn hợp lệ vì \(a\) và \(b\) có cùng thưởng rút bài (1 lá) và thưởng lượt (0 lượt). Hơn nữa, điểm số vẫn giữ nguyên. Điều tương tự cũng đúng với hai lá bài \(C_2\).

Quan sát thứ nhất cho thấy ta không cần quan tâm đến các lá bài \(C_0\) cho đến tận cuối cùng, khi ta có thể dùng các lượt còn lại cho bất kỳ lá \(C_0\) nào đã rút được. Rõ ràng, ta nên sắp xếp các lá \(C_0\) trong tay theo thứ tự giảm dần của điểm thưởng và đánh nhiều nhất có thể.

Quan sát thứ hai cho thấy ta có thể biến đổi bất kỳ chuỗi đánh bài tối ưu nào thành một chuỗi khác mà các lá bài cùng loại được sắp xếp theo chỉ số. Điều này có nghĩa là ta có thể đánh các lá bài \(C_1\) (và \(C_2\)) theo thứ tự tăng dần của chỉ số.

Vì vậy, bất cứ khi nào có nhiều hơn một lá bài \(C_1\) (hoặc \(C_2\)) trong tay, ta luôn có thể xem xét lá bài có chỉ số nhỏ nhất và chọn đánh nó ngay bây giờ hoặc không bao giờ đánh nó.

Cách cài đặt

Những quan sát này dẫn chúng ta đến việc xây dựng một đồ thị có hướng không chu trình (DAG) có trọng số. Một nút đại diện cho một trạng thái của trò chơi và được xác định bởi các thuộc tính:

• hand: số lượng lá bài đã rút.
• turns: số lượt đi còn lại.
• t: \(T[t]\) là lá bài T đầu tiên chưa được đánh.
• c1: \(C_1[c1]\) là lá bài \(C_1\) đầu tiên mà ta chưa quyết định có đánh hay không.
• c2: \(C_2[c2]\) là lá bài \(C_2\) đầu tiên mà ta chưa quyết định có đánh hay không.

Một cạnh đại diện cho một bước chuyển hợp lệ và trọng số của cạnh là số điểm tăng thêm. Với mỗi nút (hand, turns, t, c1, c2), ta thêm các cạnh theo quy tắc:

1. Nếu có lá bài T trong tay (T[t].index < hand), ta có thể đánh nó. Trọng số: T[t].score. Trạng thái mới: (min(N+M, hand + T[t].card_draw), min(N+M, turns + T[t].turns - 1), t + 1, c1, c2).
2. Nếu có lá bài \(C_1\) trong tay (C1[c1].index < hand), ta có thể đánh nó. Trọng số: C1[c1].score. Trạng thái mới: (min(N+M, hand + 1), turns - 1, t, c1 + 1, c2).
3. Nếu có lá bài \(C_1\) trong tay, ta có thể bỏ qua nó. Trọng số: 0. Trạng thái mới: (hand, turns, t, c1 + 1, c2).
4. Nếu có lá bài \(C_2\) trong tay (C2[c2].index < hand), ta có thể đánh nó. Trọng số: C2[c2].score. Trạng thái mới: (min(N+M, hand + 2), turns - 1, t, c1, c2 + 1).
5. Nếu có lá bài \(C_2\) trong tay, ta có thể bỏ qua nó. Trọng số: 0. Trạng thái mới: (hand, turns, t, c1, c2 + 1).
6. Luôn có thể kết thúc trò chơi bằng cách dùng các lượt còn lại cho các lá \(C_0\) tốt nhất đã rút được (tham lam).

Độ phức tạp

Đáp án là đường đi dài nhất trong đồ thị. Số lượng nút là \(O((N+M)^5)\), nên độ phức tạp thời gian là \(O((N+M)^5)\). Trong thực tế, thời gian chạy rất nhanh vì phần lớn các trạng thái không thể đạt tới. Bạn có thể tăng tốc bằng cách ưu tiên đánh lá bài T ngay khi có thể.

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