Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-05-04SRM505 Div1(復習)

SRM505 Div1 500 SetMultiples

| 07:41 | SRM505 Div1 500 SetMultiples - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM505 Div1 500 SetMultiples - SRM diary(Sigmar) SRM505 Div1 500 SetMultiples - SRM diary(Sigmar) のブックマークコメント

Problem Statement

後で

まずA-B区間とC-D区間を分けて考えると、k=2だけ考えれば良い

(B/2以下の数は2倍するとB以下である。また、2倍してもB/2以下の数は更に2倍すればいつかはB/2~Bの区間に入る。逆にB/2よ

り大きい数は2倍するとBを超えるため必ず残す必要がある。)

なのでAはmax(A, B/2+1)、Cはmax(C, D/2+1)とする

あとは、A-B区間のうちC-D区間の約数になっているものを減算するだけである

ここでA-B区間の数を1つ1つイテレートなどすると明らかにTLEとなるため、kをイテレートすることにする

まず最初にk1=D/B, k2=(C-1)/A+1とすると、k1はBがD以下となる最大のkであり、k2はAがC以上となる最小のkである

この時点でk2<=k1だとすると、A-Bの全区間がC-Dに入ることは明白である

続いてk1<k2の場合は、k2をD/Aに置き換えて、kをk1<=k<=k2の区間でイテレートすれば良さそうである

ここであるkのときに、C-D区間に入るA-Bの最大値をhi、最小値-1をloと置く

そうすると、hi-loが必要ない数字の数ということになる

また、次のkはhiがlo以下の最大の値となるように選べば重複が発生しないため単純に解から減じていくことができる

ということで後はコーディングするだけなのであるがminとかmaxとかいっぱい出てきて非常に間違えやすい

実際プラクティスで2回もWAを出した。考え方だけでなくコーナーケースのケアもとても難しい。。。

どうも上位の人の解法を見ると別の書き方をしている人もいるのでもう少し間違えにくい解き方もありそうではある。


ソースコード

class SetMultiples {
public:
	long long smallestSubset(long long A, long long B, long long C, long long D) {
		long long res=0;

		A=max(A, B/2+1);
		C=max(C, D/2+1);
		ll k1=D/B, k2=(C-1)/A+1;
		res=D-C+1;
		if(k2<=k1) return res;

		k2=D/A;
		ll k=k1;
		ll hi=B;
		res+=B-A+1;
		while(k<=k2) {
			ll lo=(C-1)/k;
			res-=max(hi-max(A-1, lo), 0LL);
			k=max(k+1, D/lo);
			hi=min(lo, D/k);
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110504