Phân tích: Juice

Trong bài toán này, chúng ta cần tìm bộ \((A^*, B^*, C^*)\) tốt nhất sao cho có số lượng tối đa các bộ ba \((A, B, C)\) trong đầu vào thỏa mãn:

Dễ dàng nhận thấy rằng chúng ta chỉ cần xem xét các giá trị nguyên \(A^*, B^*, C^*\). Thực tế, \(C^*\) có thể là một trong các giá trị \(C\) từ đầu vào, tương tự với \(A^*\) và \(B^*\) -- nếu không, chúng ta có thể giảm giá trị đó cho đến khi nó chạm tới một giá trị của khách hàng đã được thỏa mãn.

Vì vậy, chúng ta có tối đa \(5000\) giá trị ứng viên cho \(C^*\) (hoặc \(10000\) nếu bạn không muốn sử dụng quan sát trên). Chúng ta thử từng giá trị đó. Bài toán có thể được hình ảnh hóa trên một lưới 2 chiều.

Với một giá trị \(C^*\) cố định, ta biết \(A^* + B^* \le 10000 - C^*\). Ta lọc bỏ mọi bộ dữ liệu có \(C > C^*\) hoặc \(A + B > 10000 - C^*\), rồi xem các điểm còn lại như các điểm trong mặt phẳng 2 chiều, với \(A, B\) là tọa độ của chúng. Đối với giải pháp tốt nhất \((A^*, B^*)\), chúng ta có thể thử tất cả các điểm nguyên (\(10001 - C^*\) điểm) trên đường thẳng \(A^* + B^* = 10000 - C^*\). Với mỗi điểm, chúng ta cần biết nhanh chóng có bao nhiêu điểm đầu vào bị điểm đó bao phủ, tức là nằm trong hình chữ nhật song song với các trục giữa gốc tọa độ và điểm đó.

Bước cuối cùng phải được tính toán đủ nhanh để đáp ứng giới hạn thời gian của cuộc thi. Giả sử chúng ta di chuyển điểm \((A^*, B^*)\) từ phía trên bên trái xuống phía dưới bên phải. Tại một bước nhất định, chúng ta đang ở \((A', B')\), với \(Q\) điểm bị nó bao phủ. Trong bước tiếp theo, chúng ta ở \((A' + 1, B' - 1)\), số lượng điểm bị bao phủ bởi điểm mới có thể được tính là:

trong đó \(V_A\) là bộ đếm các điểm trên đường thẳng đứng thứ \(A\), và \(H_B\) là số lượng điểm trên đường nằm ngang thứ \(B\). \(Q'\) có thể được tính trong thời gian hằng số nếu chúng ta tính toán trước các bộ đếm.

Cách cài đặt từ giám khảo:

int T, n, ans;
int A[5000], B[5000], C[5000], H[10001], V[10001];

int main() {
  cin>>T;
  for (int t=1; t<=T; t++) {
    cin>>n;
    for(int i=0; i<n; ++i) cin>>A[i]>>B[i]>>C[i];

    int ans = 0;
    for (int CC=0; CC<=10000; ++CC) {
      memset(H, 0, sizeof(H));
      memset(V, 0, sizeof(V));
      for (int i=0; i<n; ++i)
        if (C[i]<=CC && A[i]+B[i]+CC<=10000)
        { V[A[i]]++; H[B[i]]++; }
      int Q = 0;
      for (int AA=-1; AA<10000-CC; ++AA) {
        Q = Q + V[AA+1] - H[10000-CC-AA];
        ans >?= Q;
      }
    }

    cout<<"Case #"<<t<<": "<<ans<<endl;
  }
  return 0;
}

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