Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-03-10SRM536 Div1

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