Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-03-10SRM536 Div1

SRM536 Div1 250 MergersDivOne

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

Problem Statement

コーディングフェーズ

一瞬DPかと思ってちょっと時間を無駄にしてしまった

しかしよく見るとどう見ても小さい方から2つずつくっつけていけば最適っぽい

こういうGreedyなのって急ぐとろくなことがない。落ちる可能性が高い。

少し考えてみるが、反例が思いつかない。大丈夫な気がする。

提出。

プログラミングというより数学の問題ですね


ソースコード

class MergersDivOne {
public:
	double findMaximum(vector <int> rev) {
		double res;
		int n=rev.size();
		sort(rev.begin(), rev.end());

		res=rev[0];
		for(int i=1; i<n; i++) res=(res+rev[i])/2;
		return res;
	}
};

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;
	}
};

SRM536 Div1 1000 BinaryPolynomialDivOne

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

Problem Statement

コーディングフェーズ

値が大きすぎてどう見てもbinary methodとしか思えない

binary methodを再帰的に計算する場合、AやBを多項式として、A^2と、A*Bみたいなものの2種類の計算が出てくる

ところでA^2って、展開して、ある項kに着目すると、Σ(A[n]*A[k-n])みたいな係数の計算になる

ということは、A[n]*A[k-n]+A[k-n]*A[n]みたいに順序を入れ替えたものが出てくるので、A[k/2]*A[k/2]を除いて全て2の倍数である

なのでA[k/2]*A[k/2]以外の計算は無視できる


あとは、、A*Bになるところの計算が問題・・・

A*Bの片方は、元の配列aなので、最大50しか項がない

じゃあ50通りだけ係数を計算すればOKか

といっても50通りも計算したら、毎回50分岐して無理すぎる


うーん


いや違う

50分岐といっても、連続した50個の区間である

段々kを1/2していくのだから、50個くらいであれば同じ値に収束していくはずだ

ということは、メモ化すれば全然楽勝っぽい


残り15分くらいある。書ける気がする

書いた

合わない

結構悩む

ifの中に外側と同じ変数が定義してあった。ミスった。最悪。直した

まだメモ化の部分書いてない。

make_pairとかちまちま書いてたらコーディングフェーズが終わっていた

1分くらい間に合わなかった。

マクロは使わない主義だけど、今回だけはマクロが使いたくなった・・・


ソースコード

特に修正せずプラクティス通りました。もったいな・・

こっちのほうがMediumより簡単だった気がする

map <pair <ll, ll>, int> memo;

class BinaryPolynomialDivOne {
public:
	int rec(vector <int> &a, ll m, ll k) {
		int n=a.size();

		if(m==1) {
			if(k>=n) return 0;
			return a[k];
		}

		if(memo.count(make_pair(m, k))) return memo[make_pair(m, k)];

		int res=0;
		if(m%2==0) {
			if(k%2!=0) return 0;
			res=rec(a, m/2, k/2);
		} else {
			for(ll i=max(0LL, k-n+1); i<=k; i++) {
				res^=rec(a, m-1, i)*a[k-i];
			}
		}

		memo[make_pair(m, k)]=res;
		return res;
	}

	int findCoefficient(vector <int> a, long long m, long long k) {
		int res;

		memo.clear();
		res=rec(a, m, k);
		
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120310