---
tags: GCJ
---
# GCJ Qual 2020 E - Indicium を $O(N^2)$ で解く

## 問題

$N\times N$ マスに数字を書き込んで

- 各行に $1$ から $N$ が 1 つずつ
- 各列に $1$ から $N$ が 1 つずつ
- 左上から右下への和が $K$

となるようにしてください

## 考察

2部マッチングを忘れたのでパズルをがんばる

めちゃくちゃがんばると解ける

$K = N^2 - 2,\ N + 2$ のときが一番難しい

これを

とりあえずこうして

残りをどうにかしてパターン化しながら埋めたい
こんな感じに埋める

こんな感じに

残りはやるだけ

でもこれは $N$ が偶数だと使えない

もうちょっと簡略化して、1 を縦・横・斜めに重複がないように配置する問題にする

偶数のときもパターン化したい
奇数番を先に偶数番を後に埋める

$N = 2\pmod{6}$ のとき使えない

途中から反転させると…？

反転させる位置が $\frac{N - 8}{3}$ か $\frac{N - 2}{3}$ であれば重複がないように配置できる。

## 実装

https://codingcompetitions.withgoogle.com/codejam/submissions/000000000019fd27/dGF0eWFt

int solve(){
    LL(n,k);
    if(n==3){
        if(k==5||k==7)return POSSIBLE(0);
    }
    if(k==n+1||k==n*n-1)return POSSIBLE(0);
    POSSIBLE();
    if(n==4&&k==10){
        ll ans[4][4]={1,3,4,2,4,2,1,3,2,4,3,1,3,1,2,4};
        each(i,ans)out(i);
        return 0;
    }
    if(k%n==0){
        vector<ll>a(n);
        a[0]=k/n;
        rep(n-1)a[i+1]=a[i]%n+1;
        vv(ll,ans,n,n);
        rep(n)rep(j,n)ans[i][j]=a[(i-j+n)%n];
        each(i,ans)out(i);
        return 0;
    }
    if(k==n*n-2||k==n+2){
        bool rev=k==n+2;
        vv(ll,ans,n,n);
        ll m=n-2;
        ll s=m-2;
        rep(m)ans[i][i]=n;
        rep(m)ans[i][(i+1)%m]=n-1;
        ans[m][m+1]=ans[m+1][m]=n;
        ans[m][m]=ans[m+1][m+1]=n-1;
        if(n&1){
            rep(m-2)ans[0][i+2]=(m-i)%m+1;
        }
        elif(s%6!=4){
            rep(s/2)ans[0][i+2]=(m-i*2)%m+1;
            rep(s/2)ans[0][i+s/2+2]=(m-i*2-1)%m+1;
        }
        else{
            ll d=(s-4)/3;
            rep(s){
                ll j=i/2+((i>=d)^(i&1)?s/2:0);
                ans[i][(i+j+2)%m]=1;
            }
            rep(i,1,m)rep(j,2,m)if(ans[i-1][(i-1+j)%m])ans[i][(i+j)%m]=ans[i-1][(i-1+j)%m]%m+1;
            rep(j,2,m)if(ans[m-1][(m-1+j)%m])ans[0][j]=ans[m-1][(m-1+j)%m]%m+1;
        }
        rep(i,1,m)rep(j,2,m)ans[i][(i+j)%m]=ans[i-1][(i-1+j)%m]%m+1;
        rep(m)rep(j,m,n)ans[i][j]=(i+j+1)%m+1;
        vv(ll,index,m+1,0);
        vv(ll,value,m,0);
        rep(j,m){
            vec(bool,contain,n+1);
            rep(m)contain[ans[i][j]]=1;
            rep(i,1,m+1)if(!contain[i]){
                index[i].push_back(j);
                value[j].push_back(i);
            }
        }
        rep(m)if(!ans[m][i]){
            ll at=i,val=value[i][0];
            do{
                at=index[val][index[val][0]==at];
                ans[m+1][at]=val;
                val=value[at][value[at][0]==val];
                ans[m][at]=val;
            }while(at!=i);
        }
        if(rev)each(i,ans)each(j,i)j=n+1-j;
        each(i,ans)out(i);
        return 0;
    }
    bool rev=n*(n+1)/2<k;
    if(rev)k=n*(n+1)-k;
    vector<ll>a(n);
    a[0]=k/n;
    ll diff=k-a[0]*(n-2);
    a[1]=(diff-1)/2;
    if(a[0]==a[1])a[1]--;
    a.back()=diff-a[1];
    rep(i,2,n-1){
        a[i]=a[i-1]%n+1;
        while(a[i]==a[0]||a[i]==a[1]||a[i]==a.back())a[i]=a[i]%n+1;
    }
    if(rev)each(i,a)i=n+1-i;
    vv(ll,ans,n,n);
    rep(n)rep(j,n)ans[i][j]=a[(i-j+n)%n];
    swap(ans[0],ans[1]);
    each(i,ans)out(i);
    return 0;
}
signed main(){
    LL(t);
    rep(t){
        Case(i+1);
        solve();
    }
}