kmjp's blog

競技プログラミング参加記です

Google Code Jam 2020 Round 1A : B. Pascal Walk

ちょっと余分にやりすぎたかも。
https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd74/00000000002b1353

問題

パスカルの三角形を考える。
各要素がハニカム状に並んでいるとみなし、最上段から初めて隣接要素をたどることを考える。
同じ要素を2回以上通らない経路のうち、長さが500以下で総和がNとなるものを構築せよ。

解法

パスカルの三角形は、横1段分の要素の総和を取ると2の累乗になる。
そこで、(0-originで)各段rで一番端だけを通るか、全部を通るかで総和を1か2^rだけ追加できる。
なので、移動する最下段Rを総当たりし、段の大きい順に総和が入力値から溢れない範囲で、どん欲に全部通るか判定していこう。
あとは全部通るかどうかに従い、三角形上をジグザグに降りる。

ll N;

static const int N_=1020;
static ll C_[N_][N_];

void solve(int _loop) {
	int f,i,j,k,l,x,y,r;
	
	cin>>N;
	
	vector<pair<int,int>> R;
	for(x=0;x<=35;x++) {
		ll lef=N-(x+1);
		R.clear();
		int side=0;
		
		for(y=x;y>=0;y--) {
			if(lef>=(1LL<<y)-1) {
				lef-=(1LL<<y)-1;
				if(side==0) {
					FOR(i,y+1) R.push_back({y,i});
				}
				else {
					FOR(i,y+1) R.push_back({y,y-i});
				}
				side^=1;
			}
			else {
				if(side==0) {
					R.push_back({y,0});
				}
				else {
					R.push_back({y,y});
				}
			}
		}
		if(lef==0) break;
	}
	assert(x<36);
	
	reverse(ALL(R));
	ll sum=0;
	
	_P("Case #%d:\n",_loop);
	FORR(r,R) {
		_P("%d %d\n",r.first+1,r.second+1);
		sum+=C_[r.first][r.second];
	}
	//_P("%lld %lld\n",N,sum);
	assert(N==sum);
}

void init() {
	int i,j;
	FOR(i,N_) C_[i][0]=C_[i][i]=1;
	for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=min(1LL<<40,C_[i-1][j-1]+C_[i-1][j]);
}

まとめ

本番は念のため段の途中で終わるケースも試したけど、不要だったみたいね。