ちょっと手間取った。
https://code.google.com/codejam/contest/8314486/dashboard#s=p2
問題
N桁の整数が与えられる。
途中、任意の整数を取り除き、代わりに末尾に0を加える、という動作を任意回数行える。
そうして得られる最大の整数を(10^9+7)で割った余りを答えよ。
解法
元の整数の各桁が降順になるようにすれば最大となる。
元の整数の桁をノード数分で均等配分し、個々のノードの担当範囲で降順にしたうえで、最後にそれらを連結しよう。
愚直に数列を処理してしまうとO(N)個の整数をノード間でやり取りすることになるが、各ノード内でランレングス圧縮して数列を表現するようにすれば、各ノードが持つ数列は最大10要素なので通信量の問題がなくなる。
各ノードで降順にしたものを、代表ノードで連結し、再びそれらを降順になるようにしよう。
あとはこのランレングス表現した数値を(10^9+7)で割るだけである。
整数dが下からx桁目からy個連続している場合、その総和はd*(10^y-1)/9*10^(x-1)となるので、これは容易にmod (10^9+7)を求められる。
int TN,MY; ll N; ll p10[1010101]; ll mo=1000000007; ll modpow(ll a, ll n = mo-2) { ll r=1; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } void slow() { int i,j,k,l,r,x,y; string s; if(MY!=0) return; p10[0]=1; FOR(i,1010000) p10[i+1]=p10[i]*10%mo; vector<int> V; FOR(i,N) { y=GetDigit(i); while(V.size() && V.back()<y) V.pop_back(); V.push_back(y); } ll ret=0; FOR(i,V.size()) (ret+=V[i]*p10[N-1-i])%=mo; cout<<ret<<endl; } void fast() { int i,j,k,l,r,x,y; string s; int L=N*MY/TN; int R=N*(MY+1)/TN; vector<pair<int,int>> V; for(i=L;i<R;i++) { y=GetDigit(i); while(V.size() && V.back().first<y) V.pop_back(); if(V.size() && V.back().first==y) V.back().second++; else V.push_back({y,1}); } PutInt(0,(int)V.size()); FORR(e,V) PutInt(0,e.first), PutInt(0,e.second); Send(0); if(MY!=0) return; V.clear(); FOR(i,TN) { Receive(i); x=GetInt(i); while(x--) { int a=GetInt(i); int b=GetInt(i); while(V.size() && V.back().first<a) V.pop_back(); if(V.size() && V.back().first==a) V.back().second+=b; else V.push_back({a,b}); } } ll ret=0; int d=N; FORR(e,V) { d-=e.second; ll a=modpow(10,d)*e.first%mo; ll b=(modpow(10,e.second)+(mo-1))*modpow(9)%mo; (ret += a*b)%=mo; } cout<<ret<<endl; } void solve(){ N=GetNumberLength(); if(N<1000) slow(); else fast(); }
まとめ
9で割るのを忘れてWAを繰り返した。