AtCoder ABC #251 (パナソニックグループプログラミングコンテスト2022) : Ex - Fill Triangle

意外と実行時間短かった。
https://atcoder.jp/contests/abc251/tasks/abc251_h

問題

ブロックが三角形上にN段並んでいる。
各ブロックには、0～6の整数値が書かれている。
うち、最下段である上からN段目に書かれた値が、RLE形式で与えられる。

i段目の端からj個目のブロックには、(i+1)段目の端からj個目と(i+1)段目の端から(j+1)個目に書かれたブロックの値の和を7で割った余りが書かれているものとする。
K段目の各ブロックに書かれた整数値を答えよ。

解法

二項係数の7で割った剰余を眺めてみると、i段目の端からj個目に書かれたブロックの値は、(i+7^n)段目の端からj個目と(j+7^n)個目とに書かれたブロックの値の和を7で割った余りであることがわかる。

そこで、N段目から(N-7^n)がK未満にならない最大のnを取って(N-(7^n))段目を求めて行こう。
この際、尺取り法の要領で、(N-(7^n))段目の値もRLE形式で保持していくとよい。

int N,M,K;
vector<pair<int,int>> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>M>>K;
	FOR(i,M) {
		cin>>x>>y;
		V.push_back({x,y});
	}
	
	while(N>K) {
		ll v=1;
		while(N-v*7>=K) v*=7;
		N-=v;
		ll LS=0,LP=0;
		ll RS=0,RP=0;
		vector<pair<int,int>> V2;
		while(V[RS].second<=v) {
			v-=V[RS].second;
			RS++;
		}
		RP=v;
		while(RS<V.size()) {
			int lf=V[LS].second-LP;
			int rf=V[RS].second-RP;
			int nl=min(lf,rf);
			int nv=(V[LS].first+V[RS].first)%7;
			if(V2.empty()||V2.back().first!=nv) {
				V2.push_back({nv,nl});
			}
			else {
				V2.back().second+=nl;
			}
			LP+=nl;
			RP+=nl;
			if(V[LS].second==LP) LS++, LP=0;
			if(V[RS].second==RP) RS++, RP=0;
		}
		
		V=V2;
		
	}
	FORR2(a,b,V) {
		FOR(i,b) cout<<a<<" ";
	}
	cout<<endl;
	
	
}

まとめ

なんとか解けてよかったね。