Hatena::ブログ(Diary)

simezi_tanの日記

2014-11-29

TopCoder SRM 622 Div1 Hard

| 01:05 | TopCoder SRM 622 Div1 Hardを含むブックマーク

問題

aまたはbからなる文字列が与えられる。

このとき、文字列に2回以上、重ならないで出現する空でない部分文字列の個数を求めよ。

文字列が同じときは一つと数える。

制約条件

文字列乱数により生成される。

n≦10^5

続きを読む

2014-11-27

Codeforces 480(#274 Div1) D. Parcels

| 20:50 | Codeforces 480(#274 Div1) D. Parcelsを含むブックマーク

問題

n個の箱があり、i番目の箱は

時刻in[i]に倉庫に入り、out[i]に倉庫から出る。

この荷物は重さがw[i]であり、上にs[i]までの荷物を載せることができる。

この荷物を倉庫に出し入れするとv[i]円もらえる。


倉庫には、同時に全体でSの重さの荷物しか入れられない。

また、荷物は直前に入れた荷物の真上にのみ置くことができ、最も上にある荷物のみを取り出すことができる。


利益を最大にするように、倉庫に出し入れする荷物を選択したときの利益を求めよ。

制約条件

n≦500

0≦in[i]<out[i]<2*n

w[i], s[i], S≦1000

v[i]≦10^6

続きを読む

2014-11-26

Codeforces 478(#273 Div2only) E. Wavy numbers

| 18:11 | Codeforces 478(#273 Div2only) E. Wavy numbersを含むブックマーク

問題

wavy numberとは、数字を10進法で書いたときの数字をx1,x2,x3,...,xnとすると

x1<x2>x3<x4…が成り立つまたは、x1>x2<x3>x4…が成り立つ数のことを言う。

Nの倍数のwavy numberでK番目に小さいものを求めよ。

答えが存在しない場合や10^14より大きくなる場合は-1を出力せよ。

制約条件

N, K≦10^14

続きを読む

2014-11-25

Codeforces 484(#276 Div1) E. Sign on Fence

| 04:30 | Codeforces 484(#276 Div1) E. Sign on Fenceを含むブックマーク

問題

長方形の板がN枚並んで出来ているフェンスがある。

i番目の板は幅1, 高さがh[i]の長方形で、下側の辺は地面にぴったりとくっついている。


このフェンスに看板を貼る候補がQ通りある。

各候補は、l, r, wで表され、l枚目からr枚目の板の内部に幅wの長方形の看板を貼りたいことを意味する。

看板は、底の面が地面にぴったりくっつくように、板からはみ出ないよう貼らなければならない。


それぞれの候補に対して貼れる看板の最大の高さを求めよ。

制約条件

N≦10^5

h[i]≦10^9

Q≦10^5

続きを読む

2014-11-16

2014-2015 ACM-ICPC, NEERC, Moscow Subregional Contest J. JPEG is Awesome!

| 23:58 | 2014-2015 ACM-ICPC, NEERC, Moscow Subregional Contest J. JPEG is Awesome!を含むブックマーク

問題

K日間にわたって写真を撮る。カメラの記憶容量はLであり、写真一枚が消費する記憶容量は非圧縮の場合Dである。


i日目にはti枚の写真を撮り、j番目の写真のできばえはQijである。

写真は好きなものを好きなだけ削除することができる。

また、同じ日の写真は同じ圧縮率α(0≦α≦1)で圧縮することができる。

圧縮した場合、記憶容量はα倍、できばえはα倍になる。

同じ日の写真を、違う圧縮率で圧縮することはできない。


できばえの合計値の最大値を求めよ。

出力は分数の形で出力せよ。

制約条件

K≦10^6

L, D≦10^9

写真の合計枚数≦10^9

方針

0. 同じ日の中で写真はできばえの良い順に使うとしてよい。

1. 圧縮する日は高々一日だけでよい。

2. 非圧縮の場合の容量の和はL + D未満であるとしてよい


1. 最適解において圧縮した日が二日あるなら、1容量あたりのできばえが多い日のαを大きくすれば得をするのでこれは最大性に反する。

2. 最適解において、L + D以上なら、圧縮している日の最後の一枚を削ればできばえが増加する。


なので、i日目を圧縮すると仮定し、i日目にj枚使うとするのを全通り試せばよい。

2.より採用する写真の枚数(m)はあらかじめわかっているので、

i日目にj枚使うとすると、i日以外では貪欲にいい順にm - j枚とればよい。


これは適切なデータ構造(BITなど)を使えばO(log(n))時間でできる。

分数のところは多倍長とか使って頑張る。

ソースコード

const int MX = 1000010;
ll bit[MX], bit2[MX];
inline void add(ll *bit, int i, ll x){
	for(i++ ; i < MX; i += i & -i) bit[i] += x;
}
inline ll sum(ll *bit, int i){
	ll res = 0;
	for(i++; i; i -= i & -i) res += bit[i];
	return res;
}
inline int get(ll *bit, int k){
	if(k == 0) return -1;
	if(sum(bit, MX - 2) < k) return -inf;
	
	int lo = 0, hi = 1 << 32 - __builtin_clz(MX), mid;
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		if(mid > MX || bit[mid] >= k) hi = mid;
		else k -= bit[lo = mid];
	}
	return lo;
}

ll sums[MX];
int K, L, D, delta;
vector<vi> v, pos;

inline void calc(ll o, ll cursum, int j, ll &d, ll &x, ll &y){
	d = o;
	x = cursum;
	y = (j + 1ll) * D;
	ll g = __gcd(x, y), z = ((j + 1ll) * D - delta);
	x /= g; y /= g;
	g = __gcd(z, y);
	z /= g; y /= g;
	
	if(x * 1.0 * z <= 1e18){
		x *= z;
		d += x / y; x %= y;
	}
	else{
		BigNum a = convert(x), c = convert(z);
		pair<BigNum, Int> m = divmod(a * c, y);
		stringstream ss;
		ss << m.first;
		d += atoll(ss.str().c_str());
		x = m.second;
	}
}

int main(){
	scanf("%d%d%d", &K, &L, &D);
	v.resize(K);
	pos.resize(K);
	
	vector<pi> in;
	
	rep(i, K){
		int t, u; scanf("%d", &t);
		rep(j, t) scanf("%d", &u), v[i].pb(-u);
		sort(all(v[i]));
	}
	random_shuffle(all(v));
	rep(i, K){
		rep(j, v[i].size()) in.pb(mp(v[i][j], i));
	}
	sort(all(in));
	int n = in.size();
	
	rep(i, n){
		pos[in[i].second].pb(i);
		sums[i + 1] = sums[i] - in[i].first;
		
		add(bit, i, 1);
	}
	
	ll ans = sums[min(n, L / D)];
	int usecnt = (L + D - 1) / D;
	delta = (ll)usecnt * D - L;
	long double ansd = ans;
	ll d = ans, x = 0, y = 1;
	
	
	#if 0
	rep(i, n) cerr<<-in[i].first<<(i==n-1?"\n":" ");
	rep(i, n) cerr<<in[i].second<<(i==n-1?"\n":" ");
	rep(i, K) rep(j, pos[i].size()) cerr<<pos[i][j]<<(j==pos[i].size()-1?"\n":" ");
	
	dbg(usecnt);
	dbg(delta);
	dbg(ansd);
	#endif
	
	if(usecnt > n){
		cout << ans << endl;
		return 0;
	}
	assert(usecnt <= n);
	assert(delta < D);
	assert(n <= 1000000);
	
	vi ord;
	rep(i, K) ord.pb(i);
	random_shuffle(all(ord));
	
	rep(ii, K){
		int i = ord[ii];
		vi &u = v[i];
		int t = u.size();
		ll cursum = 0;
		
		assert(sum(bit2, MX - 3) == 0);
		assert(sum(bit, MX - 3) == n);
		
		rep(j, t){
			add(bit2, pos[i][j], -u[j]);
			add(bit, pos[i][j], -1);
		}
		rep(j, t){
			if(j >= usecnt) break;
			
			int p = get(bit, usecnt - j - 1);
			cursum -= u[j];
			
			//dbg(j); dbg(p);
			
			if(p == -inf) continue;
			/*
			dbg(n - t + j + 1);
			dbg(usecnt);
			*/
			assert(n - t + j + 1 >= usecnt);
			
			ll o = sums[p + 1] - sum(bit2, p);
			long double tmp = o + 1.0l * cursum * ((j + 1ll) * D - delta) / (j + 1) / D;
			
			assert(o <= ans);
			if(ansd >= tmp + EPS) continue;
			
			ll dd, xx, yy;
			calc(o, cursum, j, dd, xx, yy);
			
			if(d < dd || d == dd &&
				convert(x) * yy < convert(xx) * y){
			
				ansd = tmp;
				d = dd;
				x = xx;
				y = yy;
			}
			assert(x < y);
			assert(__gcd(x, y) == 1);
		}
		rep(j, t){
			add(bit2, pos[i][j], u[j]);
			add(bit, pos[i][j], 1);
		}
	}
	cout << d;
	if(x) cout << " + " << x << "/" << y;
	cout << endl;
	dbg((double)ansd);
	
	return 0;
}