2941:Homogeneous Squares

keyword

行列　C

概要

サイズN*N (N<1000)の行列が与えられる。任意の置換σに対してΣa[i][ σ[i] ]が同じ値をとるかどうか判定する問題。
各行の階差数列が等しくなるかどうか判定すれば良い。なぜなら、a[i][k+1] - a[i][k] != a[j][k+1] - a[j][k]ならa[i][k] + a[j][k+1] != a[i][k+1] + a[j][k]だからこの部分を入れ換えればよいから。計算量O(N^2)でこれ以上はどうしようもないのに制限時間ギリギリだった。どうしろと。

int difs[1001];

main(){
    int n, i, j, prev, cur, isOk;
    while(n = readint(), n){
        isOk = 1;
        for(i=0;i<n;i++){
            if(i==0){
                for(j=0;j<n;j++){
                    cur = readint();
                    if(j){
                        difs[j] = cur - prev;
                    }
                    prev = cur;
                }
            }
            else{
                for(j=0;j<n;j++){
                    cur = readint();
                    if(j && difs[j] != cur - prev){
                        isOk = 0;
                    }
                    prev = cur;
                }
            }
        }
        if(isOk)puts("homogeneous");
        else puts("not homogeneous");
    }
}