2012-12-27

■ SRM525 Div2 600 DropCoins 00:42

問題の要約:

盤の上にコインが置かれており、上、下、左、右に1つ押し出す操作を行うことを何回か繰り返すことによって、盤上のコイン数をK個にするときに必要な操作数は？

制約: 盤の縦、横の長さは30以下

コインのあるマスは'o'、ないマスは'.'で表される。

解法: 縦の長さをC,横の長さをRとする。

　　　（左上のマスをboard[0][0],右下のマスをboard[R-1][C-1]とする）

　　　すると、上にa回、下にb回、左にc回、右にd回押し出したときに残るコインは、

　　　int num=0;
　　　for(int i=a;i<=C-1-b;i++){
　　　  for(int j=c;j<=R-1-d;j++){
　　　    if(board[i][j]=='o'){
　　　      num++;
　　　　　}
　　　　}
　　　}

　　　で求められる。

　　　＜解法を三つ紹介＞

　　　解法1 (O(C^3*R^3))

　　　　縦2列のセレクト(O(C^2))

　　　　横2列のセレクト(O(R^2))

　　　　で長方形を一意に決められる。

　　　　　あとはその中にあるコインをカウント(O(C*R))

　　　　C^3*R^3の最大値は30^6=約7.3*10^8

　　　　でも、この問題ではAC。（最大ケースでも約0.2secでした）

　　　解法2 (O(C^2*R^2))

　　　　縦2列のセレクト(O(C^2))

　　　　横2列のセレクト(O(R^2))

　　　　で長方形を一意に決められる。（解法1とここまでは同じ）

　　　　　でも、ここで二次元累積和のアルゴリズム(O(C*R))を使うと

　　　　　長方形内のコイン数がO(1)で求まる。

　　　　こっちの方法で解くと最大ケースでも0.008secでした。

　　　解法3 (O(C*R*min(C,R)))

　　　　縦、横の内短い方の長さを2列セレクト。(O(min(C,R)^2))

　　　　次に、長い方の辺を見たとき、尺取り法のアルゴリズム(O(max(C,R))

　　　　を用いると、O(min(C,R)^2*max(C,R))=O(C*R*min(C,R))で求まる。

　　　　尺取りをバグなく書くのって大変ですね。。。（まだ実装してないです）

以下、自分のソース

(解法1)

#include 
#include 
using namespace std;
class DropCoins{
public:
int getMinimum(vector  board, int K){
int ans=10000000;
for(int i=1;i<=board.size();i++){
	for(int j=i;j<=board.size();j++){
		for(int k=1;k<=board[0].size();k++){
			for(int l=k;l<=board[0].size();l++){
			int rp=0;
			for(int a=i;a<=j;a++){
				for(int b=k;b<=l;b++){
					if(board[a-1][b-1]=='o'){
						rp++;
					}
				}
			}
			if(rp==K){
					int q=i-1;
					int r=board.size()-j;
					int p=min(q,r);
					int s=k-1;
					int t=board[0].size()-l;
					int w=min(s,t);
					ans=min(ans,(q+r+p+s+t+w));
			}
			}
		}
	}
}
if(ans==10000000){
	return -1;
}else{
	return ans;
}
}
};

(解法2)

#include 
#include 
using namespace std;
class DropCoins{
public:
int getMinimum(vector  board, int K){
int rui[31][31]={};
for(int i=1;i<=board.size();i++){
	if(board[i-1][0]=='o'){
		rui[i][1]=rui[i-1][1]+1;
	}else{
		rui[i][1]=rui[i-1][1];
	}
}
for(int i=1;i<=board[0].size();i++){
	if(board[0][i-1]=='o'){
		rui[1][i]=rui[1][i-1]+1;
	}else{
		rui[1][i]=rui[1][i-1];
	}
}
for(int i=2;i<=board.size();i++){
	for(int j=2;j<=board[0].size();j++){
		if(board[i-1][j-1]=='o'){
			rui[i][j]=rui[i-1][j]+rui[i][j-1]-rui[i-1][j-1]+1;
		}else{
			rui[i][j]=rui[i-1][j]+rui[i][j-1]-rui[i-1][j-1];
		}
	}
}
int ans=10000000;
for(int i=1;i<=board.size();i++){
	for(int j=i;j<=board.size();j++){
		for(int k=1;k<=board[0].size();k++){
			for(int l=k;l<=board[0].size();l++){
				int eo=rui[j][l]-rui[j][k-1]-rui[i-1][l]+rui[i-1][k-1];
				if(eo==K){
					int q=i-1;
					int r=board.size()-j;
					int p=min(q,r);
					int s=k-1;
					int t=board[0].size()-l;
					int w=min(s,t);
					ans=min(ans,(q+r+p+s+t+w));
				}
			}
		}
	}
}
if(ans==10000000){
	return -1;
}else{
	return ans;
}
}
};

ツイートする