ちょっと余分にやりすぎたかも。
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]); }
まとめ
本番は念のため段の途中で終わるケースも試したけど、不要だったみたいね。