TopCoder Open Qual.1 Hard SequenceMerger

TopCoder 二分法

問題概要

与えられた数列の結び（和集合）をソートした数列において、n（n≦10億）番目の項を求めよ。

数列の形式は以下の3つである。

  • 等差数列 (初項・公差・項数が与えられる)
  • 等比数列 (初項・公比・項数が与えられる)
  • 例外 (各項が直接与えられる)

数列を指定する文字列に出現する数字は64bitに入らないこともありうる。
項数がnに満たない場合や、n番目の項が10億より大きい場合は-1を返せ。

解法

数列の数は10億を超えるので、直接書き出していくような解法は取れない。
n番目の項の値を二分法により求めることを考える。


では具体的にn番目の項の値valを求めるにはどうすれば良いかと言うと、

  • 和集合数列において、ある値「未満の項の数」を求める関数countを作り
  • count(val)≦n＜count(val+1)であるようなvalを二分法により探す


countについて。
例外数列の分は直接数えればよい。ソートしておくとlower_boundが使えて楽だが別に時間は余裕があるので必須ではない。
等差数列は、初項からいくつまでがval未満であるか割り算により求める。
等比数列はlogを使えばいくつまでがval未満かわかる。


二番目の条件は具体例を見れば比較的わかりやすい。
7,13,13,15,15,16,17が和集合数列であるとしよう。この数列の5番目の項を求めたいとする。
0番目から数えることにする（そのほうが数えやすいので）。なので以下4番目と呼ぶ。
4番目の項の値は15（の右のほう）である。
ここで、15より小さい項が3個、15以下の項が5個あるという意味である。
count(15)=3≦4（番目）＜count(15+1)=5となるようなval=15がn=4番目の値となっていることがわかるだろうか。


基本的な考え方はこれで良いが、数列を指定する文字列において64bitにも収まらない巨大な数が出てきたり(1000000002などと置き換えればよい)、doubleでは小数点誤差でテストに通らない（long doubleを使う必要がある）など細かい落とし穴が非常に多い。

ソースコード

TopCoderのPracticeRoomから見られるし、要らないような気もするけど……

vi e;
vector<vi> a,g;

class SequenceMerger {
	public:
	vector <int> getVal(vector <string> seqs, vector <int> positions)
	{
		e.clear(),a.clear(),g.clear();
		int n=seqs.size(),m=positions.size();
		
		//parse
		rep(i,n)
		{
			stringstream ss(seqs[i].substr(2));
			vi tmp; string str;
			while(ss>>str)
			{
				ll t;
				if(str.size()>10)t=1000000001;
				else stringstream(str)>>t;
				
				if(t>1000000000)t=1000000001;
				tmp.pb((int)t);
			}
			
			if(seqs[i][0]=='E')e.insert(e.end(),all(tmp));
			else if(seqs[i][0]=='A')a.pb(tmp);
			else g.pb(tmp);
		}
		sort(all(e));
		
		vi ans;
		rep(i,m)
		{
			positions[i]--;
			int lo=0,hi=1000000002,mid;
			while(lo+1<hi)
			{
				mid=(lo+hi)/2;
				if(count(mid)>positions[i])hi=mid;
				else if(count(mid+1)<=positions[i])lo=mid;
				else
				{
					lo=mid; break;
				}
			}
			if(lo>1000000001)lo=1000000001;
			ans.pb(lo==1000000001?-1:lo);
		}
		return ans;
	}
	int count(int val)
	{
		int ret=lower_bound(all(e),val)-e.begin();
		rp(i,a)
		{
			if(a[i][1]==0)
			{
				if(a[i][0]<val)ret+=a[i][2];
			}
			else if(a[i][0]<=val)
			{
				ret+=min(a[i][2],
					(val-a[i][0])/a[i][1]+((val-a[i][0])%a[i][1]!=0)
				);
			}
			ret=min(ret,1000000001);
		}
		rp(i,g)
		{
			if(g[i][1]==1||g[i][0]==0)
			{
				if(g[i][0]<val)ret+=g[i][2];
			}
			else if(g[i][0]<=val)
			{
				ret+=min(g[i][2],
					(int)ceil(log(ld(val)/g[i][0])/log(ld(g[i][1])))
				);
			}
			ret=min(ret,1000000001);
		}
		
		return ret;
	}
}