Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-03-09SRM499 Div1

SRM499 Div1 250 ColorfulRabbits

| 20:59 | SRM499 Div1 250 ColorfulRabbits - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM499 Div1 250 ColorfulRabbits - SRM diary(Sigmar) SRM499 Div1 250 ColorfulRabbits - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

サンプル読む限り、同じ数のウサギをカウントして適当に足し合わせるだけにしか見えないけど・・・

書いた→サンプル通った

提出

うーん・・・合ってるよな・・・


ソースコード

class ColorfulRabbits {
public:
	int getMinimum(vector <int> rep) {
		int res=0;
		int n=rep.size();

		map <int, int> cnt;
		for(int i=0; i<n; i++) {
			cnt[rep[i]]++;
		}

		for(map <int, int>::iterator mpi=cnt.begin(); mpi!=cnt.end(); mpi++) {
			int v=mpi->first+1;
			res+=mpi->second/v*v;
			if(mpi->second%v>0) res+=v;
		}
		return res;
	}
};

SRM499 Div1 550 WhiteSpaceEditing

| 20:59 | SRM499 Div1 550 WhiteSpaceEditing - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM499 Div1 550 WhiteSpaceEditing - SRM diary(Sigmar) SRM499 Div1 550 WhiteSpaceEditing - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

うーん・・・まずはサンプル確認

sample0によるとdeleteを使っているようだがどういう場面でdeleteが必要になるのだろう

少なくともsample0はdeleteなしでも同じ答えになる。

{0}→{2}→{2,2,2}→{3,2,2}→{3,2,3}

同じようにやればどんな場面でもdeleteなしでできそうだ。

まずreturnの数はどうやっても数列のサイズ-1にしかならないので最初に加算する。

spaceのコストは、例えば、a<=b<=c<=dで{a,c,b,d}を作るとき、以下の順で作ればc+(d-b)のスコアで作成できる

{a}→{a,a}→{a,b}→{a,b,b}→{a,c,b}→{a,c,b,b}→{a,c,b,d}

もっと複雑なパターンでも同じように作成できる

例えば{1,2,4,3,2,5}などでは以下のようにやれば良い

{1}→{1,1}→{1,2}→{1,2,2,2}→{1,2,3,2}→{1,2,3,3,2}→{1,2,4,3,2}→{1,2,4,3,2,2}→{1,2,4,3,2,5}

deleteを使っても結局このようなGreedyな方法より良いスコアは出せそうにない。(試せば分かるが、どうやってもdeleteのスコアとspaceのスコアが相殺される)

少なくとも、sampleは全部これで答えが合う。

・・・

これは簡単すぎていかにも罠っぽいな。計算量も余裕すぎるし。550でこの解はありえん。

(10分くらい反例を探す)

あれー反例見つからない・・

だんだん550出してる人も増えてきたし・・一回提出しとくか・・・

提出

その後も残り45分ずっと反例を考えるが見つからず・・


チャレンジフェーズ

みんな全然違うDP解(涙目)

8回もチャレンジを受けるが生き残る


システムテスト

Passed

信じられん。こんな単純な解で良いとは・・


ソースコード

以下は部分増加列をまとめて1つのスコアとして扱っているが、単にlines[i]>lines[i-1]のときlines[i]-lines[i-1]を加算するだけでも同じ解になります

SRM494 Div1 500 AlternatingLane(木を切り倒さなくても一緒・・みたいな)と同じ感じですね

class WhiteSpaceEditing {
public:
	int getMinimum(vector <int> lines) {
		lines.push_back(0);
		int n=lines.size();
		int res=n-2;

		int prev=0, base=0;
		for(int i=0; i<n; i++) {
			if(lines[i]<prev) {
				res+=prev-base;
				base=lines[i];
			}
			prev=lines[i];
		}
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110309