[JOI合宿]2011-Day1:Banner

問題文 : こちら

思ったとおりに実装してAC.

実装 15 分 + Debug 1 分 (string.hの宣言を忘れている & 答えのオーバーフロー修正.)

愚直解として, 辺を4つ決めるO((WH)^2)の解が考えられる. これは40 %解法となる.

ここで, 長方形の縦の辺を全て決めると (O(H^2)), 横の辺を全て走査し(O(W)), 横の辺に含まれている色を分類することで, 数学的に旗の組み合わせを求めることができる. (O(1))
故に, O(W^2H)で, 100 % の得点を得ることができる.

#include <stdio.h>
#include <string.h>

#define min(a, b) ((a) > (b) ? (b) : (a))

int main(void)
{
    int H, W;
    int i, j, k;
    static int map[512][512];
    int comb[3][3];
    long long ans;
    
    scanf("%d%d", &H, &W);
    
    for (i = 0; i < H; i++){
        for (j = 0; j < W; j++){
            scanf("%d", &map[i][j]);
        }
    }
    
    ans = 0;
    
    for (i = 0; i < H; i++){
        for (j = i + 1; j < H; j++){
            memset(comb, 0, sizeof(comb));
            for (k = 0; k < W; k++){
                int a = min(map[i][k], map[j][k]);
                int b = map[i][k] + map[j][k] - a;
                comb[a][b]++;
            }
            ans += comb[0][0] * comb[1][2] +
                   comb[1][1] * comb[0][2] +
                   comb[2][2] * comb[0][1] +
                   comb[0][1] * (comb[0][2] + comb[1][2]) +
                   comb[0][2] * comb[1][2];
        }
    }
    
    printf("%lld\n", ans);
    
    return (0);
}