2. APIO 2025 - Permutation Game
Alice và Bob là bạn thời thơ ấu và rất thích các trò chơi trí tuệ. Hôm nay, họ chơi một trò chơi mới trên đồ thị.
Bộ trò chơi gồm một đồ thị liên thông có \(m\) đỉnh, đánh số từ \(0\) đến \(m-1\), và \(e\) cạnh, đánh số từ \(0\) đến \(e-1\). Cạnh thứ \(i\) nối hai đỉnh \(u[i]\) và \(v[i]\).
Bộ trò chơi còn có một hoán vị \(p[0],p[1],\ldots,p[n-1]\) độ dài \(n\), trong đó \(m\le n\). Điểm của \(p\) là số chỉ số \(i\) thỏa mãn \(p[i]=i\).
Trò chơi kéo dài tối đa \(10^{100}\) lượt. Trong mỗi lượt:
- Nếu Alice quyết định kết thúc, trò chơi dừng lại.
- Nếu không, Alice chọn \(m\) chỉ số phân biệt \(t[0],t[1],\ldots,t[m-1]\), với \(0\le t[i]<n\). Không yêu cầu \(t[0]<t[1]<\cdots<t[m-1]\).
- Bob chọn một cạnh có chỉ số \(j\), \(0\le j<e\), rồi hoán đổi \(p[t[u[j]]]\) và \(p[t[v[j]]]\).
Alice muốn tối đa hóa điểm cuối cùng của hoán vị, còn Bob muốn tối thiểu hóa nó. Điểm tối ưu là điểm cuối cùng nếu cả hai cùng chơi tối ưu.
Bạn cần xác định chính xác điểm tối ưu, sau đó chơi với Bob đủ số lượt để đạt điểm ít nhất bằng điểm tối ưu. Chiến lược của Alice phải đúng với mọi cách đi của Bob, kể cả khi Bob không đi tối ưu.
Chi tiết cài đặt
Bạn cần cài đặt hàm:
int Alice(int m, int e, std::vector<int> u, std::vector<int> v,
int n, std::vector<int> p)
m: số đỉnh của đồ thị.e: số cạnh của đồ thị.u,v: hai mảng độ dài \(e\) mô tả các cạnh.n: độ dài hoán vị.p: hoán vị ban đầu, có độ dài \(n\).- Hàm được gọi đúng một lần và phải trả về điểm tối ưu của trò chơi.
Trong hàm này, bạn có thể gọi:
int Bob(std::vector<int> t)
tphải có đúng \(m\) phần tử phân biệt, mỗi phần tử thuộc \([0,n-1]\).- Hàm trả về chỉ số cạnh \(j\) duy nhất thỏa mãn \(0\le j<e\); trình chấm đồng thời thực hiện phép hoán đổi tương ứng.
- Có thể gọi hàm nhiều lần.
Ví dụ
Xét lời gọi:
Alice(5, 6, [4, 0, 3, 1, 4, 2], [2, 2, 0, 2, 0, 3],
10, [8, 2, 7, 6, 1, 5, 0, 9, 3, 4])
Đồ thị tương ứng:
Ban đầu, \(p=[8,2,7,6,1,5,0,9,3,4]\). Có thể chứng minh điểm tối ưu là \(1\).
Giả sử Alice thực hiện bốn lượt minh họa sau:
t truyền cho Bob |
Giá trị Bob trả về |
Hai chỉ số của p |
p sau phép đổi |
|---|---|---|---|
[3, 1, 5, 2, 0] |
5 | 5, 2 | [8, 2, 5, 6, 1, 7, 0, 9, 3, 4] |
[9, 3, 7, 2, 1] |
0 | 1, 7 | [8, 9, 5, 6, 1, 7, 0, 2, 3, 4] |
[5, 6, 7, 8, 9] |
1 | 5, 7 | [8, 9, 5, 6, 1, 2, 0, 7, 3, 4] |
[7, 5, 2, 3, 6] |
3 | 5, 2 | [8, 9, 2, 6, 1, 5, 0, 7, 3, 4] |
Các lượt trên chỉ để minh họa, Alice và Bob không nhất thiết đi tối ưu. Alice cũng có thể dừng ngay từ đầu vì điểm ban đầu đã bằng \(1\).
Sau bốn lượt, điểm thực tế là \(3\) vì \(p[2]=2\), \(p[5]=5\), \(p[7]=7\). Tuy vậy, Alice() vẫn phải trả về điểm tối ưu \(1\). Trả về \(3\) sẽ bị chấm sai.
Ràng buộc
- \(2\le m\le 400\).
- \(m-1\le e\le 400\).
- \(0\le u[i],v[i]<m\).
- \(m\le n\le 400\).
- \(0\le p[i]<n\).
- Đồ thị liên thông, không có khuyên và không có cạnh trùng.
- \(p\) là một hoán vị: \(p[i]\ne p[j]\) với mọi \(i\ne j\).
Phân nhóm
- 6 điểm: \(m=2\).
- 6 điểm: \(e>m\).
- 10 điểm: \(e=m-1\).
- 24 điểm: \(e=m=3\).
- 24 điểm: \(e=m=4\).
- 30 điểm: \(e=m\).
Mỗi subtask có thể cho điểm thành phần. Gọi \(k\) là số lượt, tức số lần gọi Bob(), và gọi \(r\) là giá trị lớn nhất của \(k/n\) trên tất cả các test trong subtask. Điểm subtask được nhân với hệ số:
| Điều kiện | Hệ số |
|---|---|
| \(r\ge 12\) | \(0\) |
| \(3<r<12\) | \(1-\log_{10}(r-2)\) |
| \(r\le 3\) | \(1\) |
Do đó, dùng không quá \(3n\) lượt sẽ nhận trọn điểm subtask. Dùng từ \(12n\) lượt trở lên sẽ nhận \(0\) điểm và được hiển thị là kết quả sai.
Trình chấm mẫu
Trình chấm mẫu đọc:
m e
u[0] v[0]
u[1] v[1]
...
u[e-1] v[e-1]
n
p[0] p[1] ... p[n-1]Trình chấm mẫu in lần lượt hoán vị cuối, giá trị Alice() trả về, điểm thực tế của hoán vị cuối và số lượt đã dùng.
Bạn có thể tải trình chấm mẫu và tệp tiêu đề ở phần đính kèm.
Nguồn: APIO 2025, bài 2 - Permutation Game.
