このミスは痛い。
http://codeforces.com/contest/708/problem/B
問題
01で構成された文字列Sがある。
このSの2文字を取ったとき、i,jの順で2文字が登場する数A[i][j]が与えられる。
ここから可能なら元のSを復元せよ。
解法
最初に0,1の数B[0],B[1]を求めよう。
0と1の対応関係はおいておいて、からB[0],B[1]がわかる。
また、B[0]*B[1]==A[0][1]+A[1][0]であることを確認しよう・
ここで注意点として、A[0][0]やA[1][1]が0の時、B[0]やB[1]は0の場合と1の場合がある点に注意。
そこはB[0]*B[1]==A[0][1]+A[1][0]を満たすようそれぞれ選択しよう。
あとは0をB[0]個並べた後、1のあと0が出てくる数がA[1][0]回になるように1をB[1]個並べていくだけ。
ll A[2][2]; ll n0,n1; void solve() { int i,j,k,l,r,x,y; string s; cin>>A[0][0]>>A[0][1]>>A[1][0]>>A[1][1]; while(n0*(n0-1)/2<A[0][0]) n0++; while(n1*(n1-1)/2<A[1][1]) n1++; if(n0*(n0-1)/2!=A[0][0]) return _P("Impossible\n"); if(n1*(n1-1)/2!=A[1][1]) return _P("Impossible\n"); if(n0==0 && A[0][1]+A[1][0]) n0=1; if(n1==0 && A[0][1]+A[1][0]) n1=1; if(n0*n1 != A[0][1]+A[1][0]) return _P("Impossible\n"); if(n0==0 && n1==0) return _P("0\n"); if(n0==0 || n1==0) { FOR(i,max(n0,n1)) _P("%d",n0==0); _P("\n"); return; } int post=A[0][1]/n0; int pre=n1-post; A[0][1] -= post*n0; string S=string(pre,'1')+string(n0,'0')+string(post,'1'); FOR(i,S.size()) { if(S[i]=='0') { while(A[0][1]) { A[0][1]--; swap(S[i-1],S[i]); i++; } break; } } cout<<S<<endl; }
まとめ
まぁ自分はその注意点を見落としてWAしたんだけどね…。