Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-03-10SRM536 Div1

SRM536 Div1 500 RollingDiceDivOne

| 11:45 | SRM536 Div1 500 RollingDiceDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM536 Div1 500 RollingDiceDivOne - SRM diary(Sigmar) SRM536 Div1 500 RollingDiceDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

うーん分からん

しかし値が大きすぎるので、一発で求める系の可能性は高いよなあ・・

大まかに言えば、1+面数を足しあわせて2で割れば期待値になるんでそれに近い値っぽい

なぜか2と2とか、2と3とかで検討して、2以上離れた数字の組み合わせを全く考えなかったので、上の考えでそのまま提出してしまった。酷い

当然Challenged


後で

サイコロ2つで考えてみる。2と4のサイコロだと、縦軸を2の方の目、横軸を4の方の目とすると以下みたいな平面で合計値の組み合わせを表せる

2 3 4 5
3 4 5 6

見ての通り、斜めに切ると同じ数字が出てくる

サイコロ3つだと直方体の形で、斜めの面が全て同じ数字になる

4次元以上は人間の頭では想像できないが、同じような感じ


2と4のサイコロの例で考えてみると、3~5が2つずつ出てくるので、解は3である

3という数字は、上に書いた平面で短い順に辺を辿っていったときに、最後から2番目の角の数字である

3~5までは、斜めにスライスしたら同じ長さなので、同じ数だけ数字が出てくる

条件を整理すると、最後から2番目の角に来るまでに辿ってきた数字の数(2つ)が、最後の辺の数字の数(4つ)以下であれば、その数字が解になる

別の言い方をすると、一番大きい数字(6)から、逆方向に順に短い辺を辿って、最後から2番目の角(5)に来た時に、前から順に辿った最後から2番目の角(3)以上であればいいということになる


逆にその条件を満たさないときは、前からと後ろからで最後から2番目の角の値の中間が解になるはず

(この2つの間では、スライスした面が一度大きくなり、また小さくなるはずだから)


ソースコード

以上の考え方でプラクティス通った

他の人を見ると色々考え方があるみたいですね。

public:
	long long mostLikely(vector <int> dice) {
		long long res;
		int n=dice.size();

		sort(dice.begin(), dice.end());
		ll sum_front=accumulate(dice.begin(), dice.end()-1, 1LL);
		ll sum_back=accumulate(dice.begin(), dice.end(), 0LL);
		ll slices=sum_front-(n-1);
		sum_back-=slices-1;
		if(sum_front<=sum_back) res=sum_front;
		else res=(sum_front+sum_back)/2;

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