--- 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$ のときが一番難しい ![](https://i.imgur.com/e7jzLq9.png =384x) これを ![](https://i.imgur.com/QgjFBiB.png =384x) とりあえずこうして 残りをどうにかしてパターン化しながら埋めたい ![](https://i.imgur.com/8tniiEl.png =384x) こんな感じに埋める ![](https://i.imgur.com/fZtxreW.png =288x) こんな感じに ![](https://i.imgur.com/FClAJKE.png =384x) 残りはやるだけ ![](https://i.imgur.com/YUcVx65.png =320x) でもこれは $N$ が偶数だと使えない ![](https://i.imgur.com/vFcflXP.png =320x) もうちょっと簡略化して、1 を縦・横・斜めに重複がないように配置する問題にする 偶数のときもパターン化したい ![](https://i.imgur.com/0n5R6Ul.png =288x) 奇数番を先に偶数番を後に埋める ![](https://i.imgur.com/1wpF1MM.png =288x) $N = 2\pmod{6}$ のとき使えない ![](https://i.imgur.com/1dd2F48.png =288x) 途中から反転させると…? 反転させる位置が $\frac{N - 8}{3}$ か $\frac{N - 2}{3}$ であれば重複がないように配置できる。 ## 実装 https://codingcompetitions.withgoogle.com/codejam/submissions/000000000019fd27/dGF0eWFt ```cpp 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(); } } ```