初Hard AC、1桁順位、Highest更新、といいことづくめなのだが、問題が問題だけにいまいち喜べない。
https://community.topcoder.com/stat?c=problem_statement&pm=14707
https://community.topcoder.com/stat?c=problem_statement&pm=14708
問題
d1+d2要素の非負整数列Xのうち、隣接要素の差の絶対値が1以下で、先頭d1要素の和がw1、後半d2要素の和がw2となるようなものがあるか。
解法
D要素で和がWとなるような数列のうち、端に来る可能性があるものを求めよう。
端の要素をvとすると、この数列の上限は(v+(v+D-1))*D/2、下限は(v+(v-(D-1))*D/2 (vがD未満の時はv*(v+1)/2)となるので、Wがその範囲に来るようなvの上限下限を二分探索で求めることができる。
そうするとX[d1-1]とX[d1]に配置可能な値の範囲が求まるので、差が1以下になるような2値を取れるか判定すればよい。
string Y="Possible"; string N="Impossible"; class RememberWords { public: ll LV(ll S,ll D) { ll L=max(S-(D-1),0LL); return (S+L)*(S-L+1)/2; } ll RV(ll S,ll D) { ll R=S+(D-1); return (S+R)*(D)/2; } ll lowest(int D,int W) { ll v=(1LL<<30)-1; for(int i=29;i>=0;i--) if(RV(v-(1LL<<i),D)>=W) v-=1LL<<i; return v; } ll highest(int D,int W) { ll v=0; if(W==0) return 0; for(int i=29;i>=0;i--) if(LV(v+(1LL<<i),D)<=W) v+=1LL<<i; return v; } string isPossible(int d1, int d2, int w1, int w2) { ll L1=lowest(d1,w1); ll R1=highest(d1,w1); ll L2=lowest(d2,w2); ll R2=highest(d2,w2); cout<<L1<<" "<<R1<<endl; cout<<L2<<" "<<R2<<endl; if(L1>R1 || L2>R2) return N; if(R1+1==L2) return Y; if(R2+1==L1) return Y; if(max(L1,L2)<=min(R1,R2)) return Y; return N; } }
まとめ
なぜこれ落とした…。