Codeforces #166 Div2. E. Three Horses

Eは本番で法則を求めきれず、Editorialを見て解いた。
http://codeforces.com/contest/271/problem/E

問題

２つの整数値を持つ(a,b)というカードが複数あるとき、以下の処理により新たなカードを生成できる。

1. (a,b)から(a+1,b+1)を生成
2. a,bがともに偶数なら、(a,b)から(a/2,b/2)を生成
3. (a,b)と(b,c)から(a,c)を生成

ここで、(1,a[1])、(1,a[2])、、、(1,a[N])のN毎のカードと数値Mが与えられたとき、そこから生成可能な1<=x

解法

本番では、元カードから生成できるカードのパターンを考えきれず時間切れ。

いかはEditorialの要約。
(x,y)において、差のy-x=dが奇数であるとする。(差が偶数なら、パターン1,2により差分を半分にできるので、いずれ差を奇数に持っていくことができる。)
とすると、(x,x+d)から(1,1+d)を生成し、そこからパターン1,3を使って(1,1+k*d)を生成できる。
また、ここから差がd,2d,4d,8d...となる任意の(x,y)を生成できる。

よって、(a[1]-1)～(a[N]-1)において、まず偶数要素は値が奇数になるまで２で割る。
次に、各要素の最大公約数Gを求める。
後は、Gの約数である各数値Dにおいて、(M-(2^L)D)を足しこんでいけばよい（(x,y)のうち差がD,2D,4D,8D,...となるものを足しこむ）

int N,M;
vector<int> A;

ll gcd(ll a, ll b) { return (b==0)?a:gcd(b,a%b);}

void solve() {
	int f,r,i,j,k,l;
	double ss;
	int x,y,d;
	
	N=GETi();
	M=GETi();
	FOR(i,N) {
		j=GETi()-1;
		while(j%2==0) j>>=1;
		A.push_back(j);
	}
	
	ll g=A[0];
	for(i=1;i<A.size();i++) g = gcd(g,A[i]);
	ll sum=0;
	for(d=1;d*d<=g;d+=2) {
		if(g%d) continue;
		
		int cd=d;
		while(cd<=M) {
			sum += M-cd;
			cd<<=1;
		}
		
		if(d*d<g){
			cd=g/d;
			while(cd<=M) {
				sum += M-cd;
				cd<<=1;
			}
		}
		
	}
	
	_P("%lld\n",sum);

	return;
}

まとめ

理屈としてはわかるけど、これ本番中に思いつくの難しいよな…。
と思いつつ、非正規参加者も含めると40名以上は思いついてるんだよな…。