kmjp's blog

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

8VC Venture Cup 2017 - Elimination Round : D. PolandBall and Polygon

Fが解けなかったけどA-Eがまぁまぁ順調でどうにかIGMに復帰。
http://codeforces.com/contest/755/problem/D

問題

0~(N-1)のN頂点が凸図形を成すように順に並んでおり、隣接点同士が辺で結ばれている。
0番の頂点から始め、K大きな番号の点(そしてNで剰余をとった点)に向け線分を結ぶ、という処理を繰り返す。
NとKが互いに素なら、N回繰り返すと0番の頂点に戻るはずである。
その際、線分を増やすたびに元の図形が多角形何個に分割されるかを答えよ。

解法

K>N/2の場合、K=N-Kで置き換えて考えてもよい。

頂点v→(v+K)%Nに辺を張る場合、1+((v+1)~(v+K-1)%N)の各頂点において、隣接点以外に持つ辺の個数 の分だけ多角形が増える。
あとはBITなりSegTreeでそのような範囲の総和を高速に求めていけばよい。

int N,K;
template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> bt;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	K=min(K,N-K);
	
	ll cur=1;
	for(i=x=0;i<N;i++) {
		bt.add(x,1);
		cur++;
		if(x+K<=N) {
			cur += bt(x+K-1)-bt(x);
		}
		else {
			cur += bt(N)-bt(x);
			cur += bt(x+K-N-1);
		}
		x=(x+K)%N;
		bt.add(x,1);
		
		//_P("%I64d%c",cur,(i==N-1)?'\n':' ');
		_P("%lld%c",cur,(i==N-1)?'\n':' ');
	}
}

まとめ

これはすんなりいけた。