kojingharangの日記

SRM 552 Div1 500 FoxAndFlowerShopDivOne

01:06 |

• 残り 25 分くらい。
• grid に L or P or . が入っている。
• ２つの重ならない矩形内にて L の数(nL)と P の数(nP)の差が M 以内であるような最大の nL + nP を求める。
• grid の最大サイズ 30x30, M≦900

• 累積和を使ったとしても矩形１と矩形２をそれぞれ決めて判定すると 30^8 = 656*10^9 とかなのでだめ
• わからんね
• nL-nP ってそんなに種類ないからそれを使うんではないかと気づく
• nL-nP でソートして lower/upper bound とか使うのか？？
• 終了

• cafelier さんのをみると
• 分割軸を決めて(W+H通り)
• その左右or上下で全通り nL-nP, nL+nP を求めて
• その際 nL-nP が同じなら nL+nP が最大のものだけ残せばいいので map に記録していって
• 左右or上下から１コずつ全通りとってきて判定
• 最大でも (W+H)*(2*W^2*H^2 + 2*WH) ということで O(W^5) 程度に収まる模様。

• ↓実装練習 (passed system test in practice room)

class FoxAndFlowerShopDivOne {
	public:
	int theMaxFlowers(vector <string> F, int M) {
		int W=F[0].size();
		int H=F.size();
		
		// sum[y][x] is sum of [0, x) x [0, y)
		VVI sum(H+1, VI(W+1));
		VVI dif(H+1, VI(W+1));
		REP(x, W) REP(y, H) {
			sum[y+1][x+1] = (F[y][x]!='.' ? 1 : 0) + sum[y][x+1]+sum[y+1][x]-sum[y][x];
			dif[y+1][x+1] = (F[y][x]=='L' ? 1 : (F[y][x]=='P' ? -1 : 0)) + dif[y][x+1]+dif[y+1][x]-dif[y][x];
		}
		//cout<<sum<<endl;
		//cout<<dif<<endl;
		
		int ans = -1;
		REP(X, W) {
			map<int, int> hi0, hi1;
			// [0, X) x [0, H)
			for(int x0=0;x0<X;x0++) {
				for(int x1=x0;x1<X;x1++) {
					// [x0, x1] x [y0, y1]
					for(int y0=0;y0<H;y0++) {
						for(int y1=y0;y1<H;y1++) {
							int S = sum[y1+1][x1+1] - sum[y1+1][x0] - sum[y0][x1+1] + sum[y0][x0];
							int D = dif[y1+1][x1+1] - dif[y1+1][x0] - dif[y0][x1+1] + dif[y0][x0];
							hi0[D] = max(hi0[D], S);
							//cout<<MP(x0, MP(x1, MP(y0, y1)))<<" "<<S<<" "<<D<<endl;
						}
					}
				}
			}
			// [X, W) x [0, H)
			for(int x0=X;x0<W;x0++) {
				for(int x1=x0;x1<W;x1++) {
					// [x0, x1] x [y0, y1]
					for(int y0=0;y0<H;y0++) {
						for(int y1=y0;y1<H;y1++) {
							int S = sum[y1+1][x1+1] - sum[y1+1][x0] - sum[y0][x1+1] + sum[y0][x0];
							int D = dif[y1+1][x1+1] - dif[y1+1][x0] - dif[y0][x1+1] + dif[y0][x0];
							hi1[D] = max(hi1[D], S);
						}
					}
				}
			}
			FOR(e0, hi0) FOR(e1, hi1) if(abs(e0->first+e1->first)<=M) ans=max(ans, e0->second+e1->second);
		}
		
		REP(Y, H) {
			map<int, int> hi0, hi1;
			// [0, W) x [0, Y)
			for(int x0=0;x0<W;x0++) {
				for(int x1=x0;x1<W;x1++) {
					// [x0, x1] x [y0, y1]
					for(int y0=0;y0<Y;y0++) {
						for(int y1=y0;y1<Y;y1++) {
							int S = sum[y1+1][x1+1] - sum[y1+1][x0] - sum[y0][x1+1] + sum[y0][x0];
							int D = dif[y1+1][x1+1] - dif[y1+1][x0] - dif[y0][x1+1] + dif[y0][x0];
							hi0[D] = max(hi0[D], S);
						}
					}
				}
			}
			// [0, W) x [Y, H)
			for(int x0=0;x0<W;x0++) {
				for(int x1=x0;x1<W;x1++) {
					// [x0, x1] x [y0, y1]
					for(int y0=Y;y0<H;y0++) {
						for(int y1=y0;y1<H;y1++) {
							int S = sum[y1+1][x1+1] - sum[y1+1][x0] - sum[y0][x1+1] + sum[y0][x0];
							int D = dif[y1+1][x1+1] - dif[y1+1][x0] - dif[y0][x1+1] + dif[y0][x0];
							hi1[D] = max(hi1[D], S);
						}
					}
				}
			}
			FOR(e0, hi0) FOR(e1, hi1) if(abs(e0->first+e1->first)<=M) ans=max(ans, e0->second+e1->second);
		}
		return ans;
	}
};

ツイートする