Phân tích

Các trường hợp đặc biệt

Tập dữ liệu nhỏ có thể được giải quyết bằng phương pháp duyệt vét cạn. Với các thuật toán như tìm kiếm theo chiều rộng (BFS), người ta có thể tìm thấy tất cả các điểm bị kích hoạt.

Một trường hợp khác chúng ta có thể sử dụng BFS là khi hai vector độ dời cùng phương. Trong trường hợp này, tất cả các điểm cần xem xét nằm trên một đường thẳng, và sẽ không có quá 1.000.000 điểm trên bất kỳ đường thẳng nào.

Trường hợp tổng quát

Thú vị là đối với trường hợp tổng quát, khi hai vector không cùng phương, người ta có thể sử dụng một chương trình ngắn hơn với cấu trúc dữ liệu đơn giản hơn. Ở đây chúng tôi giới thiệu một giải pháp chỉ liên quan đến các phép cộng vector. Đây không phải là giải pháp hiệu quả nhất, nhưng nó đủ tốt cho mục đích của chúng ta.

Lưu ý: Đây không phải là lần đầu tiên chúng ta gặp một lưới số nguyên hai chiều mà việc đổi hệ tọa độ tỏ ra hữu ích. Có thể xem hình minh họa tương tự trong phần phân tích Bài D của Vòng thi trực tuyến 3.

Gọi \([x, y]\) là các điểm trong hệ tọa độ thông thường, và \((a, b)\) là các điểm trong hệ tọa độ mới. Giả sử hai vector độ dời là \(V_1 = [\delta_{x1}, \delta_{y1}]\), \(V_2 = [\delta_{x2}, \delta_{y2}]\). Giả sử quả bóng đầu tiên trúng vị trí \(P = [x_0, y_0]\). Các điểm trong hệ tọa độ mới được cho bởi:

Bài toán là tìm xem, từ \((0, 0)\), có bao nhiêu điểm sẽ bị trúng bằng cách lặp lại việc cộng \((1, 0)\) hoặc \((0, 1)\).

Không khó để chứng minh, sử dụng \((*)\) và thực tế là hai vector không cùng phương, rằng đối với bất kỳ điểm \((a, b)\) nào bên trong căn phòng, các số \(a\) và \(b\) bị giới hạn bởi một đại lượng \(Q\), trong đó \(Q\) là kích thước của căn phòng nhân với giá trị tối đa của các \(\delta\). Với các giới hạn trong bài toán của chúng ta, \(Q \le 2 \times 10^7\).

Đối với bất kỳ \(a\) cố định nào, dễ thấy rằng có một dãy liên tiếp các số \(b\) sao cho \((a, b)\) bị trúng. Nói cách khác, có các số \(b_a\) và \(b'_a\) sao cho \((a, b)\) bị trúng khi và chỉ khi \(b_a \le b \le b'_a\). Điều này là do, nếu chúng ta gọi \(b_a\) và \(b'_a\) lần lượt là \(b\) nhỏ nhất và lớn nhất bị trúng, thì theo tính lồi, \((a, b)\) nằm trong phòng với mọi \(b\) nằm giữa \(b_a\) và \(b'_a\). Khi chúng ta đã trúng \((a, b_a)\), chúng ta tiếp tục cộng \((0, 1)\) và nhận được tất cả các điểm khác. Rõ ràng là \((a, b'_a)\) là điểm cuối cùng còn ở trong phòng, và \((a, b'_a + 1)\) nằm ngoài phòng.

Sẽ là đủ tốt nếu chúng ta có thể lặp qua \(a = 0, 1, 2, \dots\) (tối đa \(Q\)), và tính nhanh \(b_a\) và \(b'_a\) cho mỗi \(a\). Lưu ý rằng, theo định nghĩa, \((a, b_a - 1)\) không bị trúng. Để trúng \((a, b_a)\), bước cuối cùng phải là từ \((a - 1, b_a)\). Vì vậy:

Để tìm \(b_a\), chúng ta có thể đơn giản bắt đầu từ \(b_{a-1}\) và tiếp tục tăng cho đến khi trúng một điểm bên trong phòng. Lưu ý rằng đối với một giá trị \(a\) đơn lẻ, việc này có thể mất nhiều thời gian. Tuy nhiên, các \(b_a\) là đơn điệu, vì vậy tổng chi phí không vượt quá \(Q\).

Khi đã tìm thấy \(b_a\), chúng ta có thể sử dụng tìm kiếm nhị phân để tìm \(b'_a\). Mặc dù tìm kiếm nhị phân đơn giản và đủ nhanh, một cách tiếp cận khác dường như "ngây ngô" hơn nhưng thực tế lại hoạt động nhanh hơn. Tương tự như cách chúng ta lấy \(b_a\) từ \(b_{a-1}\), chúng ta cũng có thể lấy \(b'_a\) từ \(b'_{a-1}\). Ở đây các \(b'_a\) không đơn điệu, vì vậy chúng ta cần thử cả tăng và giảm. Tuy nhiên, dựa trên hình dạng chữ nhật của căn phòng, hướng sẽ không thay đổi quá một lần. Tổng chi phí vẫn là \(O(Q)\).

Cài đặt

Mã mẫu cho trường hợp không cùng phương:

int T, W, H;
int x, y, dx1, dx2, dy1, dy2;

bool inside(int a, int b) {
  int xx = x + a*dx1 + b*dx2;
  int yy = y + a*dy1 + b*dy2;
  if(xx<0 || xx>=W) return false;
  if(yy<0 || yy>=H) return false;
  return true;
}

long long play() {
  long long ans=0;
  int b1=0; int b2=1000001;
  for(int a=0; ; a++) {
    while(!inside(a, b1)) {
      b1++;
      if(b1>b2) return ans;
    }
    if(inside(a, b2)) {
      while(inside(a, b2)) b2++;
      b2--;
    } else {
      while(!inside(a, b2)) b2--;
    }
    ans+=(b2-b1+1);
  }
  return 0;
}

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