JOI 2011 春合宿 day1-1 横断幕(Banner)

問題文
https://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day1.pdf

解法
部分点
対角する2点を決めれば長方形は決まるので全探索をすると部分点がもらえます。

満点
まず2列を決めます。すると長方形のすべての頂点がその列に含まれることがわかります。
また、2列が決まった状態で行を二つ決めると長方形ができます。ここで、二つの頂点の色の組として、ある一行にある、別のもう一つの行にある
を考えることができます。
この頂点の色の組は6パターンの、, , , , , が考えられます。(色の順序は問いません)
そして、すべての2列の組に対してのそれぞれの頂点の色の組の個数がわかっていれば四本の柱の選び方の個数が出てきます。0, 1, 2 がそろっていればいいため、
これは

((0, 1)の個数) * { ((0, 2)の個数) + ((1, 2)の個数) + ((2, 2)の個数) } + ((0, 2)の個数) * { ((1, 1)の個数) + ((1, 2)の個数) } + ((1, 2)の個数) * ((0, 0)の個数)

をすると求めることができ、これをすべての2列の組に対して求めました。

下のコードでは頂点の色の組をbitで表現しています。
0番目のビットが立っているときにはその頂点の組には黒がある。
1番目のビットが立っているときにはその頂点の組には灰色がある。
2番目のビットが立っているときにはその頂点の組には白がある。
というようにし、例えば(黒, 白)を(b, w)と表現し、bitの状態は 101 (= 5)としています。

ソースコード

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PA;
typedef priority_queue<int> PQ;
typedef vector<int> VE;
#define int long long
#define INF 1000000009
#define INFL 1000000000000000018
#define mod 1234567
#define pb push_back
#define MAXN 1003
#define bb 1
#define gg 2
#define ww 4
#define bg 3
#define bw 5
#define gw 6
 
 
int h, w, fid[500][500], ans, res;
 
signed main()
{
    cin >> h >> w;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> fid[i][j];
        }
    }
    for(int i = 0; i < w - 1; i++){
        for(int j = i + 1; j < w; j++){
            int bit, sum[7] = {0};
            for(int k = 0; k < h; k++){
                bit = 0;
                bit |= ((1 << fid[k][i]) | (1 << fid[k][j]));
                if(bit == bb){
                    sum[bit]++;
                }
                else if(bit == gg){
                    sum[bit]++;
                }
                else if(bit == ww){
                    sum[bit]++;
                }
                else if(bit == bg){
                    sum[bit]++;
                }
                else if(bit == bw){
                    sum[bit]++;
                }
                else if(bit == gw){
                    sum[bit]++;
                }
            }
            res = sum[bg] * (sum[bw] + sum[gw] + sum[ww]) + sum[bw] * (sum[gg] + sum[gw]) + sum[gw] * sum[bb];
            ans += res;
        }
    }
    cout << ans << endl;
 
    return 0;
}