kojingharangの日記

SRM 623 Div1 300 UniformBoard

13:24 |

• A or P or . が入ったマスがgrid状にNxN個ある. AかPをどこか他の.のマスに移す操作を最大K回できるとき、全部Aになってる最大rectに含まれるAの数を求めよ。
• 1≦N≦20

• 全てのrectについて、K手以内で全部Aにできるかどうかを判定するなら O(N^6) →いけそう
• 内側の . or P のとこは全部外側のAを持ってくるので、外側のAが足りるかどうか
• 内側の P がある場合、それを外に出すために外側に最低1個 . があるかどうか
• 必要なら P を出して(1) Aを入れる(1) 回数 numP*2 + numDot ≦ K ならOK
• 今日は2回目のコンパイルで全sample pass (maxの閉じカッコがなかった)
• 最大ケースとかいくつかチェック→提出
• 450 わからんー

• challenge される

• あとで
• 内側のPがある場合、（初期状態ではなく内側の . に外側の A を移動した後で）外側に . が1個以上あればいいのだった。
• この辺が300ということなのか? うむむ

• accepted in practice

class UniformBoard {
	public:
	int getBoard(vector <string> B, int K) {
		int N=B.size();
		int ans = 0;
		REP(sx, N) REP(sy, N) RANGE(ex, sx, N) RANGE(ey, sy, N) {
			int iE=0,iP=0,oE=0,oA=0;
			REP(x, N) REP(y, N) {
				if(sx<=x && x<=ex && sy<=y && y<=ey) {
					if(B[x][y]=='P') iP++;
					if(B[x][y]=='.') iE++;
				} else {
					if(B[x][y]=='A') oA++;
					if(B[x][y]=='.') oE++;
				}
			}
			//if(iE+iP<=oA && (iP==0 || oE>0) && iE+2*iP <= K) ans=max(ans, (ex-sx+1)*(ey-sy+1)); //だめ
			if(iE+iP<=oA && (iP==0 || iE+oE>0) && iE+2*iP <= K) ans=max(ans, (ex-sx+1)*(ey-sy+1));
		}
		return ans;
	}
};

ツイートする