第二回 アルゴリズム実技検定 : M - 食堂

コンテスト回次が漢数字なの地味にめんどいな。
https://atcoder.jp/contests/past202004-open/tasks/past202004_m

問題

ある食堂では、D日周期で料理が提供され、各日に提供される料理の種別が与えられる。

各人には食事の好みが設定されており、毎日以下の条件で食事を食べる。

• 好みの食事が出た場合、それを食べる。
• 好みでない食事が出た場合、前回食事からL日経過していた時に限り、それを食べる。

以下のクエリに順次答えよ。

• ある人の好みの食事と、最初に食事した日が与えられる。以降T日間の間に何回食事を食べるか。

解法

ダブリングで解く。
食事の種類ごとに、その食事が出るi回目の日付から、(i+2^n)回目の日付とそこまでの食事回数をダブリングで求めて行こう。
そうすれば、クエリ毎に好みの食事を食べる最後のタイミングがわかり、その後L日毎に食事をとることが計算できる。

int D,L,N;
vector<int> DS[101010];
vector<ll> num[101010][31];
int K;
ll F,T;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>D>>L>>N;
	FOR(i,D) {
		cin>>x;
		DS[x].push_back(i);
		DS[x].push_back(i+D);
	}
	FOR(i,101000) if(DS[i].size()) {
		sort(ALL(DS[i]));
		num[i][0].resize(DS[i].size()/2);
		FOR(j,DS[i].size()/2) {
			x=DS[i][j+1]-DS[i][j];
			num[i][0][j]=(x+(L-1))/L;
		}
		FOR(x,30) {
			num[i][x+1].resize(num[i][x].size());
			FOR(j,num[i][x].size()) {
				num[i][x+1][j]=min(1LL<<60,num[i][x][j]+num[i][x][(j+(1<<x))%num[i][0].size()]);
			}
		}
	}
	
		
	FOR(i,N) {
		cin>>K>>F>>T;
		if(DS[K].size()==0) {
			cout<<0<<endl;
			continue;
		}
		F--;
		x=lower_bound(ALL(DS[K]),F)-DS[K].begin();
		ll F2=DS[K][x];
		if(F2!=F) {
			T-=1+(F2-F+L-1)/L;
			if(T<0) {
				cout<<0<<endl;
				continue;
			}
		}
		else {
			T--;
		}
		x%=(DS[K].size()/2);
		ll ret=1;
		for(j=29;j>=0;j--) if(T>=num[K][j][x]) {
			T-=num[K][j][x];
			ret+=1<<j;
			x=(x+(1<<j))%(DS[K].size()/2);
		}
		cout<<ret<<endl;
		
	}
	
	
}

まとめ

Lの上限は10^9なので、常人なら死にますね。