Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-01-23SRM494 Div1

SRM494 Div1 250 Painting

| 13:50 | SRM494 Div1 250 Painting - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM494 Div1 250 Painting - SRM diary(Sigmar) SRM494 Div1 250 Painting - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

おお、最近では珍しくやるだけの問題っぽい

O(n^5)だが・・・まあループ内の計算はしょぼいから何とかなるだろう

→書く

→サンプル合わない

何か繰り返しの範囲とか色々間違っている

→直す

→サンプル合った

→最大ケース(全部B)を試す

→問題なし

→提出

結構時間かかっちゃった・・・

コーディングスピード勝負はイマイチ勝てない感じ・・


チャレンジフェーズ

明らかにおかしい人を発見!!ラッキー!!!

+50


システムテスト

Passed


ソースコード

ブラシの大きさ2~50について、塗れるところを全部塗った場合に、目的とする絵が描けるかをチェックしています

class Painting {
public:
	int largestBrush(vector <string> pict) {
		int res=1;
		int n=pict.size(), m=pict[0].size();

		for(int s=2; s<=50; s++) {
			vector <string> b(n, string(m, 'W'));
			for(int r=0; r<=n-s; r++) {
				for(int c=0; c<=m-s; c++) {
					bool ok=true;
					for(int i=r; i<r+s; i++) {
						for(int j=c; j<c+s; j++) {
							if(pict[i][j]=='W') ok=false;
						}
					}
					if(ok) {
						for(int i=r; i<r+s; i++) {
							for(int j=c; j<c+s; j++) {
								b[i][j]='B';
							}
						}
					}
				}
			}
			bool ok2=true;
			for(int r=0; r<n; r++) {
				for(int c=0; c<m; c++) {
					if(pict[r][c]!=b[r][c]) ok2=false;
				}
			}
			if(ok2) res=s;
		}

		return res;
	}
};

SRM494 Div1 500 AlternatingLane

| 13:50 | SRM494 Div1 500 AlternatingLane - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM494 Div1 500 AlternatingLane - SRM diary(Sigmar) SRM494 Div1 500 AlternatingLane - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

いかにもDP

これはDPに違いない(←そうでもない)

ビューティを最大化するってどうしたら良いんだろう

んー・・・あ、そうか、極大か極小となっている高さの木以外を全部切り倒せばいいんだ

・・・

ということは結局何も切り倒さなくても一緒?みたいだな・・

じゃあ、、書くだけなのでは・・

DPでi本目まで倒したときの、最後の木の高さhのときのビューティの期待値を計算する(←まだDPにこだわっている)

何となく計算量無理そうだが、とりあえず答えが合うかどうか、DPで書いてみる

→答え合わない→色々直す

やっと答え合った・・・

確率計算の考え方が合っていることは分かったが計算量10万*10万なので無理

というか

DPの必要ないだろこれ

隣り合う木の高さの差分の平均値を合計するだけじゃないか

あー残り10分しかない

どうするんだどうするんだ・・(焦る)

i-1番目の木の高さlow[i-1]のときの、i番目の木の高さlow[i]~high[i]までの差分の合計値を求めれば、O(n)でlow[i-1]+1~high[i-1]の高さのときの差分合計値も求められる

よしこれだ

書いた

合わない

何でだーーー

→時間切れ

ゆっくりやりすぎた・・・最後は焦ってダメダメだし・・要反省・・


ソースコード

min関数が1個抜けてたのが合わない原因だった

というか、単に等差数列の和を求めればもっと簡単ですよね・・・何で気付かないんだ・・

class AlternatingLane {
public:
	double expectedBeauty(vector <int> low, vector <int> high) {
		double res=0;
		int n=low.size();

		for(int i=1; i<n; i++) {
			double v=0;
			for(int j=low[i]; j<=high[i]; j++) v+=abs(j-low[i-1]);
			double vv=v;
			for(int j=low[i-1]+1; j<=high[i-1]; j++) {
				v+=min(max(0, j-low[i]), high[i]+1-low[i]);
				v-=min(max(0, high[i]+1-j), high[i]+1-low[i]);
				vv+=v;
			}
			vv=vv/(high[i-1]+1-low[i-1])/(high[i]+1-low[i]);
			res+=vv;
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110123