Explanation of Inclusion-Exclusion Logic for 1904A

Правка en2, от DokjaKim, 2026-10-07 16:41:59
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        long long a, b;
        cin >> a >> b;
        pair<long long, long long> k, q;
        cin >> k.first >> k.second;
        cin >> q.first >> q.second;
        set<pair<long long, long long>> w, e;
        vector<long long> x = {-a, -b, b, a};
        vector<long long> y1 = {b, a, a, b};
        vector<long long> y2 = {-b, -a, -a, -b};
        int count = 0;

        // for the king interceptions
        for (int i = 0; i < 4; i++) {
            w.insert({k.first + x[i], k.second + y1[i]});
        }
        for (int i = 0; i < 4; i++) {
            w.insert({k.first + x[i], k.second + y2[i]});
        }
        int countK = w.size();

        // for the queen interceptions
        for (int i = 0; i < 4; i++) {
            e.insert({q.first + x[i], q.second + y1[i]});
            w.insert({q.first + x[i], q.second + y1[i]});
        }
        for (int i = 0; i < 4; i++) {
            e.insert({q.first + x[i], q.second + y2[i]});
            w.insert({q.first + x[i], q.second + y2[i]});
        }
        int countQ = e.size();
        count = w.size() - countK;
        cout << countQ - count << endl;
    }
    return 0;
}

Explanation of Inclusion-Exclusion Logic

I attempted an inclusion-exclusion approach using set sizes:

  1. King Attack Positions: First, I insert all valid attack positions of the King into a set w. The size of this set (countK = w.size()) gives us the number of unique positions that can attack the King.
  2. Queen Attack Positions: Next, I create a separate set e to store all valid attack positions of the Queen. The size of e (countQ = e.size()) represents the number of unique positions that can attack the Queen independently.
  3. Union of Positions: While inserting the Queen's positions into e, I also insert them into w. Now, w contains the union of attack positions for both the King and the Queen ($$$K \cup Q$$$).
  4. Unique to Queen: The difference count = w.size() - countK gives the number of new unique attack positions added by the Queen that were not already in w (i.e., positions that attack only the Queen and not the King).
  5. Intersection: Finally, subtracting count from countQ (countQ - count) gives the number of Queen attack positions that overlapped with the King's positions—which represents the exact number of positions that attack both pieces simultaneously ($$$K \cap Q$$$).

集合の要素数を用いた包除原理によるアプローチ (Inclusion-Exclusion Approach using Set Sizes)

  1. まず、キングを攻撃できるすべての有効な位置を集合 w に挿入します。この集合のサイズ(countK = w.size())は、キングを攻撃できるユニークな位置の数を表します。
  2. 次に、クイーンを攻撃できるすべての有効な位置を格納するための別の集合 e を作成します。e のサイズ(countQ = e.size())は、キングとは独立してクイーンを攻撃できるユニークな位置の数を表します。
  3. クイーンの位置を e に挿入すると同時に、w にも挿入します。これにより、w はキングとクイーンの両方の攻撃位置の和集合(Union)となります。
  4. 差分である count = w.size() - countK は、w にまだ存在しなかった(つまりキングは攻撃せず、クイーンのみを攻撃する)クイーンによって新たに追加されたユニークな攻撃位置の数を表します。
  5. 最後に、countQ から count を引く(countQ - count)ことで、キングの位置と重複したクイーンの攻撃位置の数が得られます。これが両方の駒を同時に攻撃できる位置の正確な数(積集合 / Intersection)となります。

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский DokjaKim 2026-10-07 16:41:59 638
en1 Английский DokjaKim 2026-10-07 16:40:08 3105 Initial revision (published)