Explanation of Inclusion-Exclusion Logic for 1904A

Revision en1, by DokjaKim, 2026-10-07 16:40:08

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; pair<long long,long long>q; cin>>k.first>>k.second; cin>>q.first>>q.second; set<pair<long long,long long>>w; set<pair<long long,long long>>e; vectorx={-a,-b,b,a}; vectory1={b,a,a,b}; vectory2={-b,-a,-a,-b}; int count=0; //for the king interceptions

//upper side
    for(int i=0;i<4;i++){
        w.insert({k.first+x[i],k.second+y1[i]});
    }
    //lowerside
    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

    //upper side
    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]});

    }
    //lowerside
    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;

}

I attempted an inclusion-exclusion approach using set sizes:

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.

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.

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.

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).

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 (the intersection).

~

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

まず、キングを攻撃できるすべての有効な位置を集合 w に挿入します。この集合のサイズ(countK = w.size())は、キングを攻撃できるユニークな位置の数を表します。

次に、クイーンを攻撃できるすべての有効な位置を格納するための別の集合 e を作成します。e のサイズ(countQ = e.size())は、キングとは独立してクイーンを攻撃できるユニークな位置の数を表します。

クイーンの位置を e に挿入すると同時に、w にも挿入します。これにより、w はキングとクイーンの両方の攻撃位置の和集合(Union)となります。

差分である count = w.size() — countK は、w にまだ存在しなかった(つまりキングは攻撃せず、クイーンのみを攻撃する)クイーンによって新たに追加されたユニークな攻撃位置の数を表します。

最後に、countQ から count を引く(countQ — count)ことで、キングの位置と重複したクイーンの攻撃位置の数が得られます。これが両方の駒を同時に攻撃できる位置の正確な数(積集合 / Intersection)となります。

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English DokjaKim 2026-10-07 16:41:59 638
en1 English DokjaKim 2026-10-07 16:40:08 3105 Initial revision (published)