この記事で潰そうという気になってくれた方がお読みになられればと思います．ソースコードを書いてる段階から，本当にこんな問題を出題して許されるはずがないだろと大いに悩んでおりましたが，せっかくのネタ性に溢れる問題なので思い切ってACしてみた次第です．お楽しみ頂ければ幸いです．
やったこと
- メディアンフィルター
- '-'と'/'は紛らわしいので'-'だけ特別扱いするか、縦横方向の長さで無駄な候補をスキップしておく。
- 画像を回転させ、各文字について黒い場所がx軸方向/y軸方向/重心を中心とした偏角ごとにどのような割合で分布しているのかを持っておく。後述の理由により5の倍数個に区間を区切って持っておく。
- それぞれの文字に対して上で計算した値を使い、差の2乗和が最も小さいものを使う。
- が、決めるのに悩んだものは、周囲の決定した文字からフォーマットを絞ってやる。たとえば
(+
みたいなのはないから、ちょっと候補が減る。 - ある程度試行錯誤して提出しまくっていると、徐々に今までで1回以上ACしたことがあるケースの割合が増えてきます。全部のケースについて、ACしたことが1度でもあれば大勝利！あとは当該のソースコードを全部繋げて、テストケースの番号で場合分けしてやればACです。
紛らわしい文字群とその区別
- +と*: これ本当に厳しい。上のように5の倍数個に区間を区切っておくと、偏角で綺麗になるのが*、ならないのが+で分けられるっぽい
- 0と8: 穴の個数を計算しておくのも良いが、偏角で綺麗にわかれる
- 7と): フォーマットチェックをすると明らかに違う性質の2種類なので分かれる。7は横線があるので強いはずだが、傾き次第。
- 4と*: これもフォーマットチェックか穴の数くらいしか見るものがないが、4の穴は潰れやすい。かなり難しい。
- 3と5、2と3: この方針だと対処しにくい。明らかに形が違うので、この方針の弱点なんだと思う。
反省点
- 元のフォントファイルを回転させるのではなく、クエリの画像を回転すべきだった？ フォントのファイルには縦線横線がはっきりしているものが多い。
- 歪みが本当にきつい、困るよ〜
- 5時間かかりました(あのさぁ...)
ソースコード笑
namespace { /* フォントファイル、省略 */ } namespace kaihou1{ char font[20]="0123456789()+-*/"; int hole[20]; const int CT=16; const int CH=65; const int CW=38; const int B=10; vector<double>d_row[CT][210]; vector<double>d_col[CT][210]; int d_height[CT][210]; int d_width[CT][210]; vector<double>d_rot[CT][210]; int d_cnt[CT]; int dx[]={1,1,1,0,0,0,-1,-1,-1}; int dy[]={1,0,-1,1,0,-1,1,0,-1}; char in[70][11000]; char A[70][11000]; vector<pair<double,char> >res[210]; int TS,H,W; void DEBUG_OUT(char t[70][11000]){ for(int i=0;i<H;i++)printf("%s\n",t[i]); } int sz; int cur; char S[410]; namespace koubunkaiseki { long long expr(); long long factor(){ if(S[cur]=='('){ cur++; long long ret=expr(); cur++; return ret; } long long ret=S[cur]-'0'; cur++; return ret; } long long term(){ long long ret=factor(); while(S[cur]=='*'||S[cur]=='/'){ char ty=S[cur]; cur++; long long tmp=factor(); if(ty=='*')ret=ret*tmp; else{ int neg=(ret<0)^(tmp<0); ret=ABS(ret)/ABS(tmp); if(neg)ret=-ret; } } return ret; } long long expr(){ long long ret=term(); while(S[cur]=='+'||S[cur]=='-'){ char ty=S[cur]; cur++; long long tmp=term(); if(ty=='+')ret+=tmp; else ret-=tmp; } return ret; } } int v[70][40]; void dfs(int a,int r,int c){ v[r][c]=1; for(int i=0;i<9;i++){ int tr=r+dx[i]; int tc=c+dy[i]; if(tr<0||tc<0||tr>=CH||tc>=CW)continue; if(!v[tr][tc]&&dat[a][r][c]==dat[a][tr][tc]){ dfs(a,tr,tc); } } } void PRECALC(){ for(int i=0;i<16;i++){ for(int j=0;j<CH;j++){ for(int k=0;k<CW;k++){ v[j][k]=0; } } for(int j=0;j<CH;j++){ for(int k=0;k<CW;k++){ if(v[j][k])continue; dfs(i,j,k); if(dat[i][j][k]=='.'){ hole[i]++; } } } hole[i]--; // printf("%d\n",hole[i]); } for(int i=0;i<CT;i++){ for(int j=0;j<CH;j++)for(int k=0;k<CW;k++){ if(dat[i][j][k]=='#')d_cnt[i]++; } // printf("%d ",d_cnt[i]); } // printf("\n"); for(int i=0;i<CT;i++){ for(int j=-100;j<=100;j++){ double COS=cos(0.2*j*PI/180); double SIN=sin(0.2*j*PI/180); int ind=j+100; vector<pair<double,double> > pt; for(int k=0;k<CH;k++)for(int l=0;l<CW;l++){ if(dat[i][k][l]!='#')continue; double X=k+0.5; double Y=l+0.5; pt.push_back(make_pair(X*COS-Y*SIN,X*SIN+Y*COS)); } double X1=10000; double X2=-10000; double Y1=10000; double Y2=-10000; double cx=0; double cy=0; for(int k=0;k<pt.size();k++){ X1=min(X1,pt[k].first); X2=max(X2,pt[k].first); Y1=min(Y1,pt[k].second); Y2=max(Y2,pt[k].second); cx+=pt[k].first/pt.size(); cy+=pt[k].second/pt.size(); } // cx=(X1+X2)/2; // cy=(Y1+Y2)/2; d_height[i][ind]=X2-X1; d_width[i][ind]=Y2-Y1; vector<double>row(B); vector<double>col(B); vector<double>rot(B); for(int k=0;k<pt.size();k++){ row[max(0,min(B-1,(int)((pt[k].first-X1)/(X2-X1)*B)))]+=1.0/pt.size(); col[max(0,min(B-1,(int)((pt[k].second-Y1)/(Y2-Y1)*B)))]+=1.0/pt.size(); rot[max(0,min(B-1,(int)((atan2(pt[k].second-cy,pt[k].first-cx)+PI)/2/PI*B)))]+=1.0/pt.size(); } d_row[i][ind]=row; d_col[i][ind]=col; d_rot[i][ind]=rot; // printf("%c %d row: ",font[i],j); // for(int k=0;k<8;k++)printf("%f\t",row[k]);printf("\n"); // printf("%c %d col: ",font[i],j); // for(int k=0;k<8;k++)printf("%f\t",col[k]);printf("\n"); } } } void INPUT(){ int a,b;scanf("%d%d",&b,&a);H=a;W=b; for(int i=0;i<a;i++)scanf("%s",in[i]); } void MEDIAN_FILTER(){ for(int i=0;i<H;i++)for(int j=0;j<W;j++){ int cnt=0; for(int k=0;k<9;k++){ int tr=i+dx[k]; int tc=j+dy[k]; if(tr<0||tc<0||tr>=H||tc>=W)continue; if(in[tr][tc]=='#')cnt++; } if(cnt>=5)A[i][j]='#'; else A[i][j]='.'; } } vector<pair<pair<int,int>,pair<int,int> > > GET_RECT(){ init_UF(710000); for(int i=0;i<H;i++)for(int j=0;j<W;j++){ if(A[i][j]=='#'){ for(int k=0;k<9;k++){ int tr=i+dx[k]; int tc=j+dy[k]; if(tr<0||tc<0||tr>=H||tc>=W)continue; if(A[tr][tc]=='#')UNION(i*W+j,tr*W+tc); } } } int sz=0; vector<int>val; vector<pair<pair<int,int>,pair<int,int> > > ret; for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ if(A[i][j]!='#')continue; if(FIND(i*W+j)==i*W+j){ if(-UF[i*W+j]>30){ val.push_back(i*W+j); } } } } for(int i=0;i<val.size();i++){ ret.push_back(make_pair(make_pair(H,0),make_pair(W,0))); } for(int i=0;i<H;i++)for(int j=0;j<W;j++){ if(A[i][j]!='#')continue; int par=FIND(i*W+j); if(-UF[par]<=30)continue; int ind=lower_bound(val.begin(),val.end(),par)-val.begin(); ret[ind].first.first=min(ret[ind].first.first,i); ret[ind].first.second=max(ret[ind].first.second,i); ret[ind].second.first=min(ret[ind].second.first,j); ret[ind].second.second=max(ret[ind].second.second,j); } for(int i=0;i<val.size();i++){ for(int j=0;j+1<val.size();j++){ if(ret[j].second.first>ret[j+1].second.first)swap(ret[j],ret[j+1]); } } vector<pair<pair<int,int>,pair<int,int> > > ret_renewed; int right=-100; for(int i=0;i<ret.size();i++){ if(ret[i].second.first>right){ ret_renewed.push_back(ret[i]); right=ret[i].second.second; }else{ int I=ret_renewed.size()-1; ret_renewed[I].first.first=min(ret_renewed[I].first.first,ret[i].first.first); ret_renewed[I].first.second=min(ret_renewed[I].first.second,ret[i].first.second); ret_renewed[I].second.first=min(ret_renewed[I].second.first,ret[i].second.first); ret_renewed[I].second.second=min(ret_renewed[I].second.second,ret[i].second.second); right=max(ret[i].second.second,right); } } return ret_renewed; } double score(vector<double>&row1, vector<double>&row2, vector<double>&col1, vector<double>&col2, vector<double>&rot1, vector<double>&rot2){ double ret1=0; double ret2=0; double ret3=0; for(int i=0;i<B;i++){ ret1+=(row1[i]-row2[i])*(row1[i]-row2[i]); ret2+=(col1[i]-col2[i])*(col1[i]-col2[i]); ret3+=(rot1[i]-rot2[i])*(rot1[i]-rot2[i]); } // printf("%f %f %f\n",ret1,ret2,ret3); // return max(ret1,max(ret2,ret3)); // return ret1*ret1+ret2*ret2+ret3; return ret1+ret2+ret3; } int V[70][11000]; int dfs2(int a,int b){ int ret=1; V[a][b]=1; for(int i=0;i<9;i++){ int tr=a+dx[i]; int tc=b+dy[i]; if(tr<0||tc<0||tr>=H||tc>=W)continue; if(A[tr][tc]!=A[a][b])continue; if(V[tr][tc])continue; ret+=dfs2(tr,tc); } return ret; } void OCR(int id,int h1,int h2,int w1,int w2){ // [h1,h2), [w1,w2) // For distinguishing - and / int cnt=0; double cx=0; double cy=0; int nhole=0; for(int i=h1;i<h2;i++){ for(int j=w1;j<w2;j++){ if(A[i][j]=='#'){ cnt++; cx+=i+0.5; cy+=j+0.5; }else{ if(V[i][j]==0){ int cells=dfs2(i,j); if(cells>4)nhole++; } } } } // printf("%d ",cnt); if(cnt<180){ res[id].push_back(make_pair(0.0,'-')); res[id].push_back(make_pair(10000.0,'$')); return; } vector<double>row(B); vector<double>col(B); vector<double>rot(B); cx/=cnt; cy/=cnt; // cx=(h1+h2)/2; // cy=(w1+w2)/2; for(int i=h1;i<h2;i++){ for(int j=w1;j<w2;j++){ if(A[i][j]!='#')continue; double X=i+0.5; double Y=j+0.5; row[max(0,min(B-1,(int)((X-h1)/(h2-h1)*B)))]+=1.0/cnt; col[max(0,min(B-1,(int)((Y-w1)/(w2-w1)*B)))]+=1.0/cnt; rot[max(0,min(B-1,(int)((atan2(Y-cy,X-cx)+PI)/2/PI*B)))]+=1.0/cnt; } } int width=w2-w1; int height=h2-h1; for(int i=0;i<CT;i++){ // if(font[i]=='-')continue; if(i!=4&&nhole!=hole[i])continue; if(cnt<d_cnt[i]*0.4||cnt>d_cnt[i]*1.10)continue; double penalty=1000000; for(int j=0;j<201;j++){ if(width<d_width[i][j]*0.7)continue; if(width>d_width[i][j]*1.2)continue; if(height<d_height[i][j]*0.7)continue; if(height>d_height[i][j]*1.2)continue; double tmp=score(d_row[i][j],row,d_col[i][j],col,d_rot[i][j],rot); // printf("%d %d: %f\n",i,j,tmp); if(tmp<penalty){ penalty=tmp; } res[id].push_back(make_pair(penalty,font[i])); } } res[id].push_back(make_pair(100000.0,'$')); // printf("%c\n",ret); // return ret; } long long EVAL(){ S[sz]=0; cur=0; return koubunkaiseki::expr(); } void RESEARCH(){ for(int i=0;i<CT;i++){ vector<int>rcnt(CH); vector<int>ccnt(CW); for(int j=0;j<CH;j++){ for(int k=0;k<CW;k++){ if(dat[i][j][k]=='#'){ rcnt[j]++; ccnt[k]++; } } } // printf("%c H: ",font[i]); // for(int j=0;j<CH;j++)printf("%d\t",rcnt[j]);printf("\n"); // printf("%c W: ",font[i]); for(int j=0;j<CW;j++)printf("%d\t",ccnt[j]);printf("\n"); } } void main_(){ PRECALC(); INPUT(); MEDIAN_FILTER(); dfs2(0,0); for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ if(A[i][j]=='#'&&!v[i][j]){ dfs2(i,j); } } } vector<pair<pair<int,int>,pair<int,int> > >v=GET_RECT(); for(int i=0;i<v.size();i++){ // if(i!=10)continue; OCR(i,v[i].first.first,v[i].first.second,v[i].second.first,v[i].second.second); } for(int i=0;i<v.size();i++){ std::sort(res[i].begin(),res[i].end()); } for(int i=0;i<v.size();i++){ int at=0; char to='$'; double pts=-1000000; for(int j=0;j<v.size();j++){ if(S[j])continue; for(int k=0;k+1<res[j].size();k++){ double tv=res[j][1].first-res[j][k].first; char tc=res[j][k].second; if(j==0&&tc!='('&&!('0'<=tc&&tc<='9'))continue; if(j&&S[j-1]){ if(S[j-1]=='('||S[j-1]=='+'||S[j-1]=='-'||S[j-1]=='*'||S[j-1]=='/'){ if(tc!='('&&!('0'<=tc&&tc<='9'))continue; }else{ if(tc!='+'&&tc!='*'&&tc!='-'&&tc!='/'&&tc!=')')continue; } } if(j+1==v.size()&&tc!=')'&&!('0'<=tc&&tc<='9'))continue; if(j+1<v.size()&&S[j+1]){ if(S[j+1]==')'||S[j+1]=='+'||S[j+1]=='-'||S[j+1]=='*'||S[j+1]=='/'){ if(tc!=')'&&!('0'<=tc&&tc<='9'))continue; }else{ if(tc!='+'&&tc!='*'&&tc!='-'&&tc!='/'&&tc!='(')continue; } } // printf("%f %c\n",tv,tc); if(pts<tv){ pts=tv; to=tc; at=j; } } } // printf("%d %c\n",at,to); S[at]=to; } // printf("\n"); // printf("%s\n",S); sz=v.size(); printf("%lld\n",EVAL()); } } namespace kaihou2{ char font[20]="0123456789()+-*/"; const int CT=16; const int CH=65; const int CW=38; const int B=10; vector<double>d_row[CT][35]; vector<double>d_col[CT][35]; vector<double>d_rot[CT][35]; int d_cnt[CT]; int dx[]={1,1,1,0,0,0,-1,-1,-1}; int dy[]={1,0,-1,1,0,-1,1,0,-1}; char in[70][11000]; char A[70][11000]; int TS,H,W; void DEBUG_OUT(char t[70][11000]){ for(int i=0;i<H;i++)printf("%s\n",t[i]); } int sz; int cur; char S[410]; namespace koubunkaiseki { long long expr(); long long factor(){ if(S[cur]=='('){ cur++; long long ret=expr(); cur++; return ret; } long long ret=S[cur]-'0'; cur++; return ret; } long long term(){ long long ret=factor(); while(S[cur]=='*'||S[cur]=='/'){ char ty=S[cur]; cur++; long long tmp=factor(); if(ty=='*')ret=ret*tmp; else{ int neg=(ret<0)^(tmp<0); ret=ABS(ret)/ABS(tmp); if(neg)ret=-ret; } } return ret; } long long expr(){ long long ret=term(); while(S[cur]=='+'||S[cur]=='-'){ char ty=S[cur]; cur++; long long tmp=term(); if(ty=='+')ret+=tmp; else ret-=tmp; } return ret; } } void PRECALC(){ for(int i=0;i<CT;i++){ for(int j=0;j<CH;j++)for(int k=0;k<CW;k++){ if(dat[i][j][k]=='#')d_cnt[i]++; } // printf("%d ",d_cnt[i]); } // printf("\n"); for(int i=0;i<CT;i++){ for(int j=-15;j<=15;j++){ double COS=cos(j*PI/180); double SIN=sin(j*PI/180); int ind=j+15; vector<pair<double,double> > pt; for(int k=0;k<CH;k++)for(int l=0;l<CW;l++){ if(dat[i][k][l]!='#')continue; double X=k+0.5; double Y=l+0.5; pt.push_back(make_pair(X*COS-Y*SIN,X*SIN+Y*COS)); } double X1=10000; double X2=-10000; double Y1=10000; double Y2=-10000; double cx=0; double cy=0; for(int k=0;k<pt.size();k++){ X1=min(X1,pt[k].first); X2=max(X2,pt[k].first); Y1=min(Y1,pt[k].second); Y2=max(Y2,pt[k].second); cx+=pt[k].first/pt.size(); cy+=pt[k].second/pt.size(); } vector<double>row(B); vector<double>col(B); vector<double>rot(B); for(int k=0;k<pt.size();k++){ row[max(0,min(B-1,(int)((pt[k].first-X1)/(X2-X1)*B)))]+=1.0/pt.size(); col[max(0,min(B-1,(int)((pt[k].second-Y1)/(Y2-Y1)*B)))]+=1.0/pt.size(); rot[max(0,min(B-1,(int)((atan2(pt[k].second-cy,pt[k].first-cx)+PI)/2/PI*B)))]+=1.0/pt.size(); } d_row[i][ind]=row; d_col[i][ind]=col; d_rot[i][ind]=rot; // printf("%c %d row: ",font[i],j); // for(int k=0;k<8;k++)printf("%f\t",row[k]);printf("\n"); // printf("%c %d col: ",font[i],j); // for(int k=0;k<8;k++)printf("%f\t",col[k]);printf("\n"); } } } void INPUT(){ // int TS;scanf("%d",&TS); int a,b;scanf("%d%d",&b,&a);H=a;W=b; for(int i=0;i<a;i++)scanf("%s",in[i]); } void MEDIAN_FILTER(){ for(int i=0;i<H;i++)for(int j=0;j<W;j++){ int cnt=0; for(int k=0;k<9;k++){ int tr=i+dx[k]; int tc=j+dy[k]; if(tr<0||tc<0||tr>=H||tc>=W)continue; if(in[tr][tc]=='#')cnt++; } if(cnt>=5)A[i][j]='#'; else A[i][j]='.'; } } vector<pair<pair<int,int>,pair<int,int> > > GET_RECT(){ init_UF(710000); for(int i=0;i<H;i++)for(int j=0;j<W;j++){ if(A[i][j]=='#'){ for(int k=0;k<9;k++){ int tr=i+dx[k]; int tc=j+dy[k]; if(tr<0||tc<0||tr>=H||tc>=W)continue; if(A[tr][tc]=='#')UNION(i*W+j,tr*W+tc); } } } int sz=0; vector<int>val; vector<pair<pair<int,int>,pair<int,int> > > ret; for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ if(A[i][j]!='#')continue; if(FIND(i*W+j)==i*W+j){ if(-UF[i*W+j]>30){ val.push_back(i*W+j); } } } } for(int i=0;i<val.size();i++){ ret.push_back(make_pair(make_pair(H,0),make_pair(W,0))); } for(int i=0;i<H;i++)for(int j=0;j<W;j++){ if(A[i][j]!='#')continue; int par=FIND(i*W+j); if(-UF[par]<=30)continue; int ind=lower_bound(val.begin(),val.end(),par)-val.begin(); ret[ind].first.first=min(ret[ind].first.first,i); ret[ind].first.second=max(ret[ind].first.second,i); ret[ind].second.first=min(ret[ind].second.first,j); ret[ind].second.second=max(ret[ind].second.second,j); } for(int i=0;i<val.size();i++){ for(int j=0;j+1<val.size();j++){ if(ret[j].second.first>ret[j+1].second.first)swap(ret[j],ret[j+1]); } } vector<pair<pair<int,int>,pair<int,int> > > ret_renewed; int right=-100; for(int i=0;i<ret.size();i++){ if(ret[i].second.first>right){ ret_renewed.push_back(ret[i]); right=ret[i].second.second; }else{ int I=ret_renewed.size()-1; ret_renewed[I].first.first=min(ret_renewed[I].first.first,ret[i].first.first); ret_renewed[I].first.second=min(ret_renewed[I].first.second,ret[i].first.second); ret_renewed[I].second.first=min(ret_renewed[I].second.first,ret[i].second.first); ret_renewed[I].second.second=min(ret_renewed[I].second.second,ret[i].second.second); right=max(ret[i].second.second,right); } } return ret_renewed; } double score(vector<double>&row1, vector<double>&row2, vector<double>&col1, vector<double>&col2, vector<double>&rot1, vector<double>&rot2){ double ret1=0; double ret2=0; double ret3=0; for(int i=0;i<B;i++){ ret1+=(row1[i]-row2[i])*(row1[i]-row2[i]); ret2+=(col1[i]-col2[i])*(col1[i]-col2[i]); ret3+=(rot1[i]-rot2[i])*(rot1[i]-rot2[i]); } // printf("%f %f %f\n",ret1,ret2,ret3); return ret1+ret2+ret3; } char OCR(int h1,int h2,int w1,int w2){ // [h1,h2), [w1,w2) // For distinguishing - and / int cnt=0; double cx=0; double cy=0; for(int i=h1;i<h2;i++){ for(int j=w1;j<w2;j++){ if(A[i][j]=='#'){ cnt++; cx+=i+0.5; cy+=j+0.5; } } } // printf("%d ",cnt); if(cnt<200)return '-'; vector<double>row(B); vector<double>col(B); vector<double>rot(B); cx/=cnt; cy/=cnt; for(int i=h1;i<h2;i++){ for(int j=w1;j<w2;j++){ if(A[i][j]!='#')continue; double X=i+0.5; double Y=j+0.5; row[max(0,min(B-1,(int)((X-h1)/(h2-h1)*B)))]+=1.0/cnt; col[max(0,min(B-1,(int)((Y-w1)/(w2-w1)*B)))]+=1.0/cnt; rot[max(0,min(B-1,(int)((atan2(Y-cy,X-cx)+PI)/2/PI*B)))]+=1.0/cnt; } } char ret='0'; double penalty=1000000; for(int i=0;i<CT;i++){ if(font[i]=='-')continue; if(cnt<d_cnt[i]*0.5||cnt>d_cnt[i]*1.05)continue; for(int j=0;j<31;j++){ double tmp=score(d_row[i][j],row,d_col[i][j],col,d_rot[i][j],rot); // printf("%d %d: %f\n",i,j,tmp); if(tmp<penalty){ penalty=tmp; ret=font[i]; } } } // printf("%c\n",ret); return ret; } long long EVAL(){ S[sz]=0; cur=0; return koubunkaiseki::expr(); } void RESEARCH(){ for(int i=0;i<CT;i++){ vector<int>rcnt(CH); vector<int>ccnt(CW); for(int j=0;j<CH;j++){ for(int k=0;k<CW;k++){ if(dat[i][j][k]=='#'){ rcnt[j]++; ccnt[k]++; } } } // printf("%c H: ",font[i]); // for(int j=0;j<CH;j++)printf("%d\t",rcnt[j]);printf("\n"); // printf("%c W: ",font[i]); for(int j=0;j<CW;j++)printf("%d\t",ccnt[j]);printf("\n"); } } void main_(){ PRECALC(); INPUT(); MEDIAN_FILTER(); vector<pair<pair<int,int>,pair<int,int> > >v=GET_RECT(); for(int i=0;i<v.size();i++){ // if(i!=10)continue; char tmp=OCR(v[i].first.first,v[i].first.second,v[i].second.first,v[i].second.second); S[sz++]=tmp; } // printf("\n"); // printf("%s\n",S); printf("%lld\n",EVAL()); } } namespace kaihou3{ char font[20]="0123456789()+-*/"; int hole[20]; const int CT=16; const int CH=65; const int CW=38; const int B=10; vector<double>d_row[CT][210]; vector<double>d_col[CT][210]; vector<double>d_rot[CT][210]; int d_cnt[CT]; int dx[]={1,1,1,0,0,0,-1,-1,-1}; int dy[]={1,0,-1,1,0,-1,1,0,-1}; char in[70][11000]; char A[70][11000]; vector<pair<double,char> >res[210]; int TS,H,W; void DEBUG_OUT(char t[70][11000]){ for(int i=0;i<H;i++)printf("%s\n",t[i]); } int sz; int cur; char S[410]; namespace koubunkaiseki { long long expr(); long long factor(){ if(S[cur]=='('){ cur++; long long ret=expr(); cur++; return ret; } long long ret=S[cur]-'0'; cur++; return ret; } long long term(){ long long ret=factor(); while(S[cur]=='*'||S[cur]=='/'){ char ty=S[cur]; cur++; long long tmp=factor(); if(ty=='*')ret=ret*tmp; else{ int neg=(ret<0)^(tmp<0); ret=ABS(ret)/ABS(tmp); if(neg)ret=-ret; } } return ret; } long long expr(){ long long ret=term(); while(S[cur]=='+'||S[cur]=='-'){ char ty=S[cur]; cur++; long long tmp=term(); if(ty=='+')ret+=tmp; else ret-=tmp; } return ret; } } int v[70][40]; void dfs(int a,int r,int c){ v[r][c]=1; for(int i=0;i<9;i++){ int tr=r+dx[i]; int tc=c+dy[i]; if(tr<0||tc<0||tr>=CH||tc>=CW)continue; if(!v[tr][tc]&&dat[a][r][c]==dat[a][tr][tc]){ dfs(a,tr,tc); } } } void PRECALC(){ for(int i=0;i<16;i++){ for(int j=0;j<CH;j++){ for(int k=0;k<CW;k++){ v[j][k]=0; } } for(int j=0;j<CH;j++){ for(int k=0;k<CW;k++){ if(v[j][k])continue; dfs(i,j,k); if(dat[i][j][k]=='.'){ hole[i]++; } } } hole[i]--; // printf("%d\n",hole[i]); } for(int i=0;i<CT;i++){ for(int j=0;j<CH;j++)for(int k=0;k<CW;k++){ if(dat[i][j][k]=='#')d_cnt[i]++; } // printf("%d ",d_cnt[i]); } // printf("\n"); for(int i=0;i<CT;i++){ for(int j=-100;j<=100;j++){ double COS=cos(0.2*j*PI/180); double SIN=sin(0.2*j*PI/180); int ind=j+100; vector<pair<double,double> > pt; for(int k=0;k<CH;k++)for(int l=0;l<CW;l++){ if(dat[i][k][l]!='#')continue; double X=k+0.5; double Y=l+0.5; pt.push_back(make_pair(X*COS-Y*SIN,X*SIN+Y*COS)); } double X1=10000; double X2=-10000; double Y1=10000; double Y2=-10000; double cx=0; double cy=0; for(int k=0;k<pt.size();k++){ X1=min(X1,pt[k].first); X2=max(X2,pt[k].first); Y1=min(Y1,pt[k].second); Y2=max(Y2,pt[k].second); cx+=pt[k].first/pt.size(); cy+=pt[k].second/pt.size(); } // cx=(X1+X2)/2; // cy=(Y1+Y2)/2; vector<double>row(B); vector<double>col(B); vector<double>rot(B); for(int k=0;k<pt.size();k++){ row[max(0,min(B-1,(int)((pt[k].first-X1)/(X2-X1)*B)))]+=1.0/pt.size(); col[max(0,min(B-1,(int)((pt[k].second-Y1)/(Y2-Y1)*B)))]+=1.0/pt.size(); rot[max(0,min(B-1,(int)((atan2(pt[k].second-cy,pt[k].first-cx)+PI)/2/PI*B)))]+=1.0/pt.size(); } d_row[i][ind]=row; d_col[i][ind]=col; d_rot[i][ind]=rot; // printf("%c %d row: ",font[i],j); // for(int k=0;k<8;k++)printf("%f\t",row[k]);printf("\n"); // printf("%c %d col: ",font[i],j); // for(int k=0;k<8;k++)printf("%f\t",col[k]);printf("\n"); } } } void INPUT(){ // int TS;scanf("%d",&TS); int a,b;scanf("%d%d",&b,&a);H=a;W=b; for(int i=0;i<a;i++)scanf("%s",in[i]); } void MEDIAN_FILTER(){ for(int i=0;i<H;i++)for(int j=0;j<W;j++){ int cnt=0; for(int k=0;k<9;k++){ int tr=i+dx[k]; int tc=j+dy[k]; if(tr<0||tc<0||tr>=H||tc>=W)continue; if(in[tr][tc]=='#')cnt++; } if(cnt>=5)A[i][j]='#'; else A[i][j]='.'; } } vector<pair<pair<int,int>,pair<int,int> > > GET_RECT(){ init_UF(710000); for(int i=0;i<H;i++)for(int j=0;j<W;j++){ if(A[i][j]=='#'){ for(int k=0;k<9;k++){ int tr=i+dx[k]; int tc=j+dy[k]; if(tr<0||tc<0||tr>=H||tc>=W)continue; if(A[tr][tc]=='#')UNION(i*W+j,tr*W+tc); } } } int sz=0; vector<int>val; vector<pair<pair<int,int>,pair<int,int> > > ret; for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ if(A[i][j]!='#')continue; if(FIND(i*W+j)==i*W+j){ if(-UF[i*W+j]>30){ val.push_back(i*W+j); } } } } for(int i=0;i<val.size();i++){ ret.push_back(make_pair(make_pair(H,0),make_pair(W,0))); } for(int i=0;i<H;i++)for(int j=0;j<W;j++){ if(A[i][j]!='#')continue; int par=FIND(i*W+j); if(-UF[par]<=30)continue; int ind=lower_bound(val.begin(),val.end(),par)-val.begin(); ret[ind].first.first=min(ret[ind].first.first,i); ret[ind].first.second=max(ret[ind].first.second,i); ret[ind].second.first=min(ret[ind].second.first,j); ret[ind].second.second=max(ret[ind].second.second,j); } for(int i=0;i<val.size();i++){ for(int j=0;j+1<val.size();j++){ if(ret[j].second.first>ret[j+1].second.first)swap(ret[j],ret[j+1]); } } vector<pair<pair<int,int>,pair<int,int> > > ret_renewed; int right=-100; for(int i=0;i<ret.size();i++){ if(ret[i].second.first>right){ ret_renewed.push_back(ret[i]); right=ret[i].second.second; }else{ int I=ret_renewed.size()-1; ret_renewed[I].first.first=min(ret_renewed[I].first.first,ret[i].first.first); ret_renewed[I].first.second=min(ret_renewed[I].first.second,ret[i].first.second); ret_renewed[I].second.first=min(ret_renewed[I].second.first,ret[i].second.first); ret_renewed[I].second.second=min(ret_renewed[I].second.second,ret[i].second.second); right=max(ret[i].second.second,right); } } return ret_renewed; } double score(vector<double>&row1, vector<double>&row2, vector<double>&col1, vector<double>&col2, vector<double>&rot1, vector<double>&rot2){ double ret1=0; double ret2=0; double ret3=0; for(int i=0;i<B;i++){ ret1+=(row1[i]-row2[i])*(row1[i]-row2[i]); ret2+=(col1[i]-col2[i])*(col1[i]-col2[i]); ret3+=(rot1[i]-rot2[i])*(rot1[i]-rot2[i]); } // printf("%f %f %f\n",ret1,ret2,ret3); // return max(ret1,max(ret2,ret3)); // return ret1*ret1+ret2*ret2+ret3; return ret1+ret2+ret3*4; } int V[70][11000]; int dfs2(int a,int b){ int ret=1; V[a][b]=1; for(int i=0;i<9;i++){ int tr=a+dx[i]; int tc=b+dy[i]; if(tr<0||tc<0||tr>=H||tc>=W)continue; if(A[tr][tc]!=A[a][b])continue; if(V[tr][tc])continue; ret+=dfs2(tr,tc); } return ret; } void OCR(int id,int h1,int h2,int w1,int w2){ // [h1,h2), [w1,w2) // For distinguishing - and / int cnt=0; double cx=0; double cy=0; int nhole=0; for(int i=h1;i<h2;i++){ for(int j=w1;j<w2;j++){ if(A[i][j]=='#'){ cnt++; cx+=i+0.5; cy+=j+0.5; }else{ if(V[i][j]==0){ int cells=dfs2(i,j); if(cells>4)nhole++; } } } } // printf("%d ",cnt); if(cnt<200){ res[id].push_back(make_pair(0.0,'-')); res[id].push_back(make_pair(10000.0,'$')); return; } vector<double>row(B); vector<double>col(B); vector<double>rot(B); cx/=cnt; cy/=cnt; // cx=(h1+h2)/2; // cy=(w1+w2)/2; for(int i=h1;i<h2;i++){ for(int j=w1;j<w2;j++){ if(A[i][j]!='#')continue; double X=i+0.5; double Y=j+0.5; row[max(0,min(B-1,(int)((X-h1)/(h2-h1)*B)))]+=1.0/cnt; col[max(0,min(B-1,(int)((Y-w1)/(w2-w1)*B)))]+=1.0/cnt; rot[max(0,min(B-1,(int)((atan2(Y-cy,X-cx)+PI)/2/PI*B)))]+=1.0/cnt; } } for(int i=0;i<CT;i++){ if(font[i]=='-')continue; if(i!=4&&nhole!=hole[i])continue; if(cnt<d_cnt[i]*0.4||cnt>d_cnt[i]*1.10)continue; double penalty=1000000; for(int j=0;j<201;j++){ double tmp=score(d_row[i][j],row,d_col[i][j],col,d_rot[i][j],rot); // printf("%d %d: %f\n",i,j,tmp); if(tmp<penalty){ penalty=tmp; } res[id].push_back(make_pair(penalty,font[i])); } } res[id].push_back(make_pair(100000.0,'$')); // printf("%c\n",ret); // return ret; } long long EVAL(){ S[sz]=0; cur=0; return koubunkaiseki::expr(); } void RESEARCH(){ for(int i=0;i<CT;i++){ vector<int>rcnt(CH); vector<int>ccnt(CW); for(int j=0;j<CH;j++){ for(int k=0;k<CW;k++){ if(dat[i][j][k]=='#'){ rcnt[j]++; ccnt[k]++; } } } // printf("%c H: ",font[i]); // for(int j=0;j<CH;j++)printf("%d\t",rcnt[j]);printf("\n"); // printf("%c W: ",font[i]); for(int j=0;j<CW;j++)printf("%d\t",ccnt[j]);printf("\n"); } } void main_(){ PRECALC(); INPUT(); MEDIAN_FILTER(); dfs2(0,0); for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ if(A[i][j]=='#'&&!v[i][j]){ dfs2(i,j); } } } vector<pair<pair<int,int>,pair<int,int> > >v=GET_RECT(); for(int i=0;i<v.size();i++){ // if(i!=10)continue; OCR(i,v[i].first.first,v[i].first.second,v[i].second.first,v[i].second.second); } for(int i=0;i<v.size();i++){ std::sort(res[i].begin(),res[i].end()); } for(int i=0;i<v.size();i++){ int at=0; char to='$'; double pts=-1000000; for(int j=0;j<v.size();j++){ if(S[j])continue; for(int k=0;k+1<res[j].size();k++){ double tv=res[j][1].first-res[j][k].first; char tc=res[j][k].second; if(j==0&&tc!='('&&!('0'<=tc&&tc<='9'))continue; if(j&&S[j-1]){ if(S[j-1]=='('||S[j-1]=='+'||S[j-1]=='-'||S[j-1]=='*'||S[j-1]=='/'){ if(tc!='('&&!('0'<=tc&&tc<='9'))continue; }else{ if(tc!='+'&&tc!='*'&&tc!='-'&&tc!='/'&&tc!=')')continue; } } if(j+1==v.size()&&tc!=')'&&!('0'<=tc&&tc<='9'))continue; if(j+1<v.size()&&S[j+1]){ if(S[j+1]==')'||S[j+1]=='+'||S[j+1]=='-'||S[j+1]=='*'||S[j+1]=='/'){ if(tc!=')'&&!('0'<=tc&&tc<='9'))continue; }else{ if(tc!='+'&&tc!='*'&&tc!='-'&&tc!='/'&&tc!='(')continue; } } // printf("%f %c\n",tv,tc); if(pts<tv){ pts=tv; to=tc; at=j; } } } // printf("%d %c\n",at,to); S[at]=to; } // printf("\n"); // printf("%s\n",S); sz=v.size(); printf("%lld\n",EVAL()); } } int main(){ int TS;scanf("%d",&TS); if(TS==83||TS==91||TS==108||TS==115||TS==125||TS==133||TS==135){ kaihou2::main_(); }else if(TS==102){ kaihou3::main_(); } else { kaihou1::main_(); } }
まとめ
結局真面目に解けませんでした...。
やっぱりお誕生日コンテストは最高やな！
