kmjp's blog

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

Distributed Code Jam 2017 Round 1 : C. weird_editor

ちょっと手間取った。
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を繰り返した。