★が2個も上がったか。
http://yukicoder.me/problems/940
問題
3*3の正方行列が門松行列であるとは、各列・各行・対角成分・反対角成分それぞれの3要素が並び順に対し門松列を成すものを指す。
入力として3*3の正方行列A[r][c]が与えられる。
ただし2要素は値が不定である。
この2要素に和がLとなる正整数をそれぞれ代入したときに、門松行列となるような要素の代入は何通りあるか。
解法
門松列の判定は要素間の大小関係と一致不一致だけわかればよい。
よって座標圧縮することを考えよう。
(非負の)A[r][c]の各値、(L-A[r][c])の各値、L/2、及びそれらの間の区間、でそれぞれ座標圧縮し、門松行列判定を行えばよい。
int T; int L; int A[9]; int li[8][3]= { {0,1,2}, {3,4,5}, {6,7,8}, {0,3,6}, {1,4,7}, {2,5,8}, {0,4,8}, {2,4,6}, }; int isok() { int i; FOR(i,8) { if(A[li[i][0]]==A[li[i][1]]) return 0; if(A[li[i][0]]==A[li[i][2]]) return 0; if(A[li[i][1]]==A[li[i][2]]) return 0; if(A[li[i][0]]<A[li[i][1]] && A[li[i][1]]<A[li[i][2]]) return 0; if(A[li[i][0]]>A[li[i][1]] && A[li[i][1]]>A[li[i][2]]) return 0; } return 1; } void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>L; vector<int> V; vector<int> cand; FOR(i,9) { cin>>A[i]; if(A[i]==0) V.push_back(i); else { if(A[i]<L) cand.push_back(A[i]); if(L-A[i]>=1) cand.push_back(L-A[i]); } } if(L<2) { _P("0\n"); continue; } cand.push_back(1); cand.push_back(L/2); cand.push_back(L-1); sort(ALL(cand)); cand.erase(unique(ALL(cand)),cand.end()); ll tot=0; FORR(r,cand) { A[V[0]]=r; A[V[1]]=L-r; tot += isok(); } FOR(i,cand.size()-1) { int x=cand[i]+1; int y=cand[i+1]-1; if(x>y) continue; A[V[0]]=x; A[V[1]]=L-x; if(isok()) tot+=y-x+1; } _P("%lld\n",tot); } }
まとめ
実装は多少面倒でも解法が自明な363より、こちらの発想ゲーの方が苦戦した。