社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。
2011-06-05Google Code Jam 2011 Round 2
Google Code Jam 2011 Round 2 B Spinning Blade
Google Code Jam | |
解答方針
よくある普通のDPに見えるのだが何かうまく計算できなくてとりあえずsmallを全探索しようとし始める
サンプル合ったのでsmall提出。WA。おいおい・・・
(Kが偶数のときと奇数のときで重心位置が0.5刻みになるのに1刻みみたいに書いていたのが原因)
・・・
・・・
(すでにコンテスト開始から1時間経過)
よくわからないので再度Largeを真面目に考え始める
やはりDPだ
モーメントの計算方法Σ(p-c)*mass(p)を変形すると、Σp*mass(p)-c*Σmass(p)
従ってある正方形のp*mass(p)とmass(p)の和を記憶しておけば定数時間でモーメントを計算できる(⇔重心が中心にあるか判定できる)
ある長方形のΣmass(p)を求めるDPは、左上隅(0,0)~右下隅(r-1,c-1)までの長方形の重さをsum[r][c]、位置(r,c)の重さをmass[r][c]とすると、sum[r][c]=sum[r-1][c]+sum[r][c-1]-sum[r-1][c-1]+mass[r-1][c-1]で計算できる
このDPを使って、左上隅(r,c)~右下隅(r+k-1,c+k-1)の正方形の重さを求めるには、sum[r+k][c+k]-sum[r][c+k]-sum[r+k][c]+sum[r][c]を求めれば良い
あとは4隅の重さを引けば求めたいものが求められる
Σp*mass(p)はr成分とc成分に分けるとやはり同様に計算できる
DP部分の計算はO(R*C)
あとは正方形の位置と大きさを定めれば定数時間でモーメントが計算できるので、計算量はO(R*C*min(R,C))≒500^3程度
というDPを書くのにバグりまくってとんでもないことになった
mass[r][c]を事前計算せず混乱してしまったのが大きな過ちだった
提出時間:Large 1h44m41s
ソースコード
変数対応表
Σp*mass(p)→(msumr, msumc)
p*mass(p)→(mwr, mwc)
Σmass(p)→sum
入出力は省略。IMPOSSIBLEのときは-1を返す。
int solve(int R, int C, int D, vector <string> bl) { int res=-1; ll msumr[510][510]; ll msumc[510][510]; ll sum[510][510]; ll mwr[510][510]; ll mwc[510][510]; memset(msumr, 0, sizeof(msumr)); memset(msumc, 0, sizeof(msumc)); memset(sum, 0, sizeof(sum)); memset(mwr, 0, sizeof(mwr)); memset(mwc, 0, sizeof(mwc)); for(int r=0; r<R; r++) { for(int c=0; c<C; c++) { mwr[r][c]=r*(D+bl[r][c]-'0'); mwc[r][c]=c*(D+bl[r][c]-'0'); } } for(int r=1; r<=R; r++) { for(int c=1; c<=C; c++) { sum[r][c]=sum[r][c-1]+sum[r-1][c]-sum[r-1][c-1]+D+bl[r-1][c-1]-'0'; msumr[r][c]=msumr[r][c-1]+msumr[r-1][c]-msumr[r-1][c-1]+mwr[r-1][c-1]; msumc[r][c]=msumc[r][c-1]+msumc[r-1][c]-msumc[r-1][c-1]+mwc[r-1][c-1]; } } for(int r=0; r<R; r++) { for(int c=0; c<C; c++) { for(int k=3; k<=min(R, C); k++) { if(r+k>R || c+k>C) break; ll sumr=0, sumc=0; sumr=msumr[r+k][c+k]-msumr[r+k][c]-msumr[r][c+k]+msumr[r][c]-mwr[r][c]-mwr[r+k-1][c]-mwr[r][c+k-1]-mwr[r+k-1][c+k-1]; sumr*=2; sumr-=(sum[r+k][c+k]-sum[r+k][c]-sum[r][c+k]+sum[r][c]-(D+bl[r][c]-'0')-(D+bl[r+k-1][c]-'0')-(D+bl[r][c+k-1]-'0')-(D+bl[r+k-1][c+k-1]-'0'))*(r*2+k-1); sumc=msumc[r+k][c+k]-msumc[r+k][c]-msumc[r][c+k]+msumc[r][c]-mwc[r][c]-mwc[r+k-1][c]-mwc[r][c+k-1]-mwc[r+k-1][c+k-1]; sumc*=2; sumc-=(sum[r+k][c+k]-sum[r+k][c]-sum[r][c+k]+sum[r][c]-(D+bl[r][c]-'0')-(D+bl[r+k-1][c]-'0')-(D+bl[r][c+k-1]-'0')-(D+bl[r+k-1][c+k-1]-'0'))*(c*2+k-1); if(sumr==0 && sumc==0) res=max(res, k); } } } return res; }