kojingharangの日記

Codeforces #153 Div1 A - Points on Line

12:44 |

• X座標が N 個与えられるので、点間の最大距離が D 以下になるような 3 点の取り方の数を求める問題。
• N≦10**5, D≦10**9

• 両端が決まるとそれに挟まれる別の点の個数だけ 3 点とれる
• ソートしておくと...
• 左端それぞれについて(O(N)), それに対応する右端のうち一番右のところは upper_bound で O(logN) で見つかる
• 右端としてありうるのはX[左端+2]からX[右端]までなので
• ある左端についての答えは M=左端と一番右の右端に挟まれる数字の個数として M≧0 なら 1からMまでの和
• 全体で O(NlogN)

• （あとで）しゃくとり法みたいにすると upper_bound 使わなくてよいようです

• ↓Accepted

int main() {
	//ios::sync_with_stdio(false);
	ll N, D;
	while(cin>>N>>D) {
		VI w(N);
		REP(i, N) {
			cin>>w[i];
		}
		sort(ALL(w));
		
		ll ans=0;
		REP(i, N-2) {
			// binary search [i+1, N-1]
			int idx = (upper_bound(&w[i+1], &w[N], w[i]+D) - &w[0])-1;
			//cout<<i<<" "<<idx<<endl;
			ll mid = idx-i-1;
			if(mid>=0) ans += mid*(mid+1)/2;
		}
		
		cout<<ans<<endl;
	}
	
	return 0;
}

ツイートする

Codeforces #159 Div1 B - Playing with Permutations

12:44 |

• 置換 A を Ai in [1, N] (i in [1, N]), Ai≠Aj (i≠j, i, j in [1, N]) とする
• 置換 Q, S が与えられる。恒等置換 P に対して毎回 Q か Q^-1 を作用させる操作を K 回やる。
• 「0回目～K-1回目は P!=S だが、ちょうど K 回目で S に等しくなる」ということはありえるかどうか求める問題。
• N, K≦100

• * を作用させる演算子として、P * Q * Q^-1 == P と元に戻るのと、作用させる順番が関係ないので、K 回後の状態は P * Q^? とあらわせる
• なので、i＜K 回目はすべての場合で P!=S で i==K 回目で P==S となる場合があるときだけ YES とするようにしてみたけど sample があわない

• 途中で P==S になる場合があってもそこを通らずに K 回目で P==S となれば YES になるのか

• 結局 BFS をすることになった。
• 予め Same[j] = S == Q^j (j in [-K, K]) かどうかを計算しておいて、
• ノード i が Same じゃなければ i-1, i+1 をキューに追加
• K回目で Same なら YES

• ノード数は 2K+1 程度なので O(NK+K^2) くらい?

• ↓Accepted

ll N, K;
VI Q, S, P, W;
VI Same; // idx [-K K]  [0 2K]

int apply(int sign) {
	if(sign==1) {
		REP(i, N) W[i]=P[Q[i]-1];
	} else {
		REP(i, N) W[Q[i]-1]=P[i];
	}
	REP(i, N) P[i]=W[i];
	return 1;
}

int main() {
	//ios::sync_with_stdio(false);
	while(cin>>N>>K) {
		Q=VI(N);
		S=VI(N);
		P=VI(N);
		W=VI(N);
		Same=VI(2*K+1);
		REP(i, N) {
			cin>>Q[i];
		}
		REP(i, N) {
			cin>>S[i];
		}
		
		for(int sign=-1;sign<=1;sign+=2) {
			REP(i, N) P[i]=i+1;
			REP(i, K+1) {
				int same=1;
				REP(j, N) if(P[j]!=S[j]) same=0;
				//cout<<P<<endl;
				Same[i*sign + K] = same;
				apply(sign);
			}
		}
		//cout<<Same<<endl;
		//break;
		
		deque<int> q;
		q.PB(0);
		int OK=0;
		REP(loop, K+1) {
			deque<int> nq;
			VI vis(2*K+1);
			while(q.size()) {
				int idx = q.front();q.pop_front();
				//cout<<"loop "<<loop<<" pop "<<idx<<endl;
				if(loop==K && Same[idx+K]) {
					//cout<<" same at Kth"<<endl;
					OK=1;break;
				}
				if(loop<K && !Same[idx+K]) {
					//cout<<" not same"<<endl;
					if(!vis[idx-1+K]) {vis[idx-1+K]=1; nq.PB(idx-1); }
					if(!vis[idx+1+K]) {vis[idx+1+K]=1; nq.PB(idx+1); }
				}
			}
			//cout<<"NQ "<<nq<<endl;
			q = nq;
			if(q.size()==0) break;
		}
		
		
		cout<<(OK?"YES":"NO")<<endl;
		//break;
	}
	
	return 0;
}

ツイートする

Codeforces #159 Div1 C - Number Transformation

12:44 |

• a = a-1 か a = a-(a % x) (x in [2, k]) の操作ができる。
• a==b になるまでの最小の操作回数を求める問題。
• 1≦b≦a≦10**18, 2≦k≦15

• 2から15までの最小公倍数が 360,360 なのでこの単位でなんかできるんじゃないかというところから進まず。

ツイートする