ichirin2501's diary

いっちりーん。

SRM 458 DIV2

/topcoder

250pt submit
500pt opened
950pt opened

Challenges -25pt

Rate: 854 -> 896(+42)

1/19追記


250pt

Easy - Desertification
182.79/250


問題文の要約。
1<=W,H<=10、1<=T<=1000000000。
フィールドは'F','D'の文字のみ。Fは森、Dは砂漠。1年経つごとに砂漠の周りの東西南北の地域が砂漠になる。
T年後の砂漠の地域の数を返す。

幅優先で書こうかと思ったけど、時間かかりそうなので途中で路線変更。
結局少し時間かかってしまった。何やってんだろ…。

class Desertification{
public:
	int desertArea(vector <string> island, int T)
	{
		const int dy[]={-1,0,1,0};
		const int dx[]={0,1,0,-1};
		
		for(int t=0;t<T;t++){
			int flag=0;
			vector<string> tmp = island; //tmp is befor
			for(int i=0;i<island.size();i++){
				for(int j=0;j<island[i].size();j++){
					if(island[i][j]=='D'){
						for(int k=0;k<4;k++){
							int tx=j+dx[k];
							int ty=i+dy[k];
							if(tx<0||ty<0||tx>=tmp[i].size()||ty>=tmp.size())continue;
							
							tmp[ty][tx]='D';
							flag=1;
						}
					}
				}
			}
			island=tmp;
			if(flag==0)break;
			if(flag==1 && T>island.size()*island[0].size()){
				return island.size()*island[0].size();
			}
		}
		int ans=0;
		for(int i=0;i<island.size();i++)
			for(int j=0;j<island[i].size();j++)
				if(island[i][j]=='D')ans++;
		return ans;
	}
};


500pt

Medium - BouncingBalls
結局最後まで問題文の意味がわからず終わった問題。


問題文の要約
直線上にボールを1〜12個置く（x軸Onlyみたいな感じ）。
ジョンは各々のボールを右or左方向に転がし、1秒あたり1進む（等速直線運動）。
ボールが衝突するとき、速度は変わらず方向だけ変わる。
T秒後までのボールが衝突する（2回目も含む）期待値を求める。
1<=T<=100000000


Return the expected number of bounces between all balls during T seconds (including those collisions that happen exactly at T seconds).
ほう、期待される値？、バウンド？、T秒の間に全てのボールがバウンド？
・・・、T秒の間に全てのボールがバウンド（衝突後のボールとの衝突も含む）する確率を求めろ？
サンプルと答えが合わない♪
となって、抜け出せず終わりました。

正しくは、T秒の間にボールがバウンドする期待値を求めろ（2回目以降の衝突も含む）という意味でした。
くっそー、ソートして包除原理プログラムで使ったビットによる選択アルゴリズムと、
等速直線運動だから2つのボールの距離が2*T以下かどうか判定するだけじゃん。ばーかばーか。

class 
{
public:
	double expectedBounces(vector <int> x, int T)
	{
		int size = x.size();
		int cnt = 0;
		sort(x.begin(),x.end());
		for(int i=0;i<(1<<size);i++){
			int tmp = i;
			for(int j=0;j<size;j++){
				if((tmp>>j)&1){
					for(int k=j+1;k<size;k++)
						if(!((tmp>>k)&1))
							if((x[k]-x[j])/2.0 <= T)cnt++;
				}
			}
		}
		return (double)cnt/(1<<size);
	}
};

他の方のコードを拝見すると、もっと良い解法がありました。
上のコードだと、計算量は(2^N * N(N+1)/2)になります。
任意の2個のボールが衝突するのは距離が2*T以下で確率は互いの方向に転がした場合のみだから、0.25に限られるので、
ボールの組み合わせをループで回しつつ距離が2*T以下なら0.25足していくだけで求められる。計算量は(N(N+1)/2)

class BouncingBalls
{
public:
	double expectedBounces(vector <int> x, int T)
	{
		double ans = 0.0;
		sort(x.begin(),x.end());
		for(int i=0;i<x.size();i++)
			for(int j=i+1;j<x.size();j++)
				if((double)(x[j]-x[i])/2.0 <= (double)T)ans+=0.25;
		
		return ans;
	}
};


950pt

Hard - ProductTriplet
すごく面白そうな問題でした。わかんないけど。


問題文の要約
minx <= x <= maxx
miny <= y <= maxy
minz <= z <= maxz
x * y = z
を満たす、(x,y,z)の個数を求める。
1 <= maxx,maxy,maxz <= 1000000000
1 <= minx,miny,minz <= max(対応するx,y,z)

一応コードをはっておく、あとで解説書く

class ProductTriplet
{
public:
	long long colc(int x, int y, int z)
	{
		int zz = sqrt((double)z);
		long long ret = 0;
		for(int i=1;i<=x && i<=zz;i++)
			ret += min(y,z/i);
		for(int i=1;i<=y && i<=zz;i++)
			ret += max(0, min(x,z/i)-zz);
		return ret;
	}
	long long countTriplets(int minx, int maxx, int miny, int maxy, int minz, int maxz)
	{
		long long ans = 0;
		ans += colc(maxx  ,maxy  ,maxz  );
		ans -= colc(minx-1,maxy  ,maxz  );
		ans -= colc(maxx  ,miny-1,maxz  );
		ans -= colc(maxx  ,maxy  ,minz-1);
		ans += colc(minx-1,miny-1,maxz  );
		ans += colc(minx-1,maxy  ,minz-1);
		ans += colc(maxx  ,miny-1,minz-1);
		ans -= colc(minx-1,miny-1,minz-1);
		return ans;
	}
};

解説どうしよう。図が欲しい。
zを固定してxy平面で見たてると、y=z/xのような反比例のグラフを表すことが出来る。
そのグラフの内側の領域かつ、minx〜maxx,miny〜maxyの領域にある格子点を数え上げればいい。

図が欲しい。
図が欲しい。

というわけで、包除原理を点ではなく領域として応用する　というのが鍵でした。