PKU演習問メモ(9/7)

No. 問題名 問題の種類および解法 難易度
3252 Round Numbers 数え上げ ★★★★☆
3253 Fence Repair 貪欲法 ★★★☆☆
3261 Milk Patterns 最長k-繰り返し部分列 ★★★★☆
3262 Protecting the Flowers 貪欲法 ★★★☆☆
3130 How I Mathematician Wonder What You Are! 幾何・多角形の切断 ★★★☆☆

3252 Round Numbers

問題概要

round numberとは、数を二進法で表したときに現れる0の数が、1の数以上であるような数のことを言う。
S以上F以下のround numberの数を求めよ。


1≦S≦F≦2000000000を満たす。

解法

数え上げはTopCoderでも頻出なのに苦手すぎる!!もっと解かないと!!
ソースのぐちゃぐちゃさがずっと嵌ってた感出してる。


n以下のround numberの数を求める方法を考える。
nを2進法で表したとき、i桁目を0に変えて、i-1桁目以下を適当にいじって、round numberをいくつ作れるかを足していく。

ソースコード
int C[32][32],CC[32][32];

int calc(int n)
{
	if(n==0)return 0;
	
	int d=0,zero=0,ret=0;
	for(int m=n;m;m/=2)d++;
	for(int m=n;m;m&=m-1)zero--; zero+=d;
	
	if(zero>=d-zero)ret++; //元の状態でround numberなら+1
	for(int i=1;i<d;i++)ret+=CC[i-1][(i+1)/2]; //元の数より桁数が少ないround number
	
	int cnt=1;
	for(int i=d-2;i>=0;i--) //i桁目を0に変えて、i+1桁目以上は
	if(n&1<<i)ret+=CC[i][max((d+1)/2-cnt,0)]; //そのままのround number
	else cnt++;
	
	return ret;
}
int main()
{
	rep(i,32)
	{
		rep(j,i+1)C[i][j]=i==0||j==0||j==i?1:C[i-1][j]+C[i-1][j-1];
		for(int j=i;j>=0;j--)CC[i][j]=(j==i?0:CC[i][j+1])+C[i][j];
	}
	
	int a,b; scanf("%d%d",&a,&b);
	printf("%d\n",calc(b)-calc(a-1));
	
	return 0;
}

3253 Fence Repair

問題概要

一本の棒からそれぞれの長さがL[i]のn本の棒を切り出したい。
ただし棒を切るのは有料で、長さlの棒を1度切るのに丁度lドルがかかる。


おがくずの量などは無視できるとするとき、欲しい棒を切り出すのにかかる最小の費用を求めよ。元の棒の長さは切り出したい棒の長さの和にちょうど等しいとする。

n≦20000,
L[i]≦50000を満たす。

解法

ハフマン木と同じ方法で出来ることに気づいた!
ハフマン木知らなきゃ無理ゲーな気がする。。。


木がばらばらになった状態から元の棒を復元することを考える。
最後に切るのは、最も短い2本の棒が最適。するとその2本の棒がつながるので、残りがn-1本になり、それらに対して同じ考察を繰り返すことができる。

ソースコード
int main()
{
	int n,l,a,b;
	scanf("%d",&n);
	priority_queue<int> Q;
	rep(i,n)scanf("%d",&l),Q.push(-l);
	
	ll ans=0;
	rep(i,n-1)
	{
		a=Q.top(); Q.pop();
		b=Q.top(); Q.pop();
		ans-=a+b;
		Q.push(a+b);
	}
	printf("%lld\n",ans);
	
	return 0;
}

3261 Milk Patterns

問題概要

ある牛からn日間の間に取れたミルクの量の記録が与えられる。
(i日目に取れたミルクの量はa[i])

1以上n以下の整数kが与えられた時、この数列a[i]の連続する部分列で、k回以上登場するもののうち長さが最大のものの長さを求めよ。
部分列同士は一部が重なっていてもかまわない。

n,k≦20000,
a[i]≦1000000を満たす。

解法

よくわかってない。最長k-繰り返し部分文字列を検出するKarp Miller Rosenbergのアルゴリズムというのがあるらしい。
これは文字列以外にも一般の数列にも適用できるらしく、それを使うとO(n(log n)^2)くらいの計算量で最長k-繰り返し部分列が求まる。らしい。


解法になってねえなーorz

ソースコード

spaghetti source最長繰り返し部分列(http://www.prefield.com/algorithm/string/karp_miller_rosenberg.html)のコードを使用

#define SETNUM(rank, i,s) \
  NUM[i] = make_pair(make_pair(rank[i], i+s<n?rank[i+s]:n), i);
#define RENUMBER(rank) \
  sort(NUM, NUM+n); \
  rank[ NUM[0].second ] = 0; \
  for (int i = 1; i < n; ++i) \
    rank[ NUM[i].second ] = rank[ NUM[i-1].second ] \
      + (NUM[i-1].first != NUM[i].first) ;
int n,ranks[32][200000];
void karp_miller_rosenberg_pre(vi &text) {
  int m = 0;
  pair<pair<int,int>,int> NUM[n];
  copy(all(text), ranks[m]);
  for (int k = 0; k <= n; k ? k*=2 : ++k) { // power of 2
    for (int i = 0; i < n; ++i) SETNUM(ranks[m], i, k);
    if (k > 0) ++m; RENUMBER(ranks[m]);
  }
}
int repeated_factor(vi &text, int r, int k) {
	int t, s;
  pair<pair<int,int>,int> NUM[n];
  int rank[n], count[n];
  for (s = 1, t = 0; s * 2 < r; s *= 2, ++t);
  for (int i = 0; i < n; ++i) SETNUM(ranks[t], i, r-s);
  RENUMBER(rank);
  memset(count, 0, sizeof(count));
  for (int i = 0; i < n; ++i)
    if (++count[ rank[i] ] >= k) return i;
  return -1;
}
int longest_repeated_factor(vi &text, int k) {
  karp_miller_rosenberg_pre(text);
	int low = 1, high = n;
  while (low+1 < high) {
    int mid = (low + high) / 2;
    if (repeated_factor(text, mid, k) < 0) high = mid;
    else                                    low = mid;
  }
  int t = repeated_factor(text, low, k);
  return t >= 0 ? low : 0;
}

int main()
{
	int k,t; scanf("%d%d",&n,&k);
	vi text; rep(i,n)scanf("%d",&t),text.pb(t);
	
	printf("%d\n",longest_repeated_factor(text,k));
	
	return 0;
}

3262 Protecting the Flowers

問題概要

n頭の牛が花壇を食べている。牛が花壇を食べる量を最小限に減らすため、牛を自分の小屋まで車に載せて運ぶ。
i番目の牛が一分間に破壊する花壇の量をD[i],牛の自分の小屋まで車で移動するのにかかる距離をT[i]分(往復には2T[i]分の時間がかかる)
とするとき、牛に食べられる最小の花壇の量を求めよ。


n≦100000を満たす。

解法

数日前のテープの問題と同じだよなあこれ。
Johnが運ぶ牛の列の中で、隣り合う牛を入れ替えたときの差を考えるとよいらしい。
(相変わらず証明が良くわからない……


という訳で前と全く同じ貪欲法。D[i]/T[i]の大きい牛から車で運んでいく。

ソースコード
typedef pair<long,long> pi;
int n;
pi in[100000];

bool cmp(const pi &l,const pi &r)
{
	return l.first*r.second>l.second*r.first;
}
int main()
{
	scanf("%d",&n);
	rep(i,n)scanf("%lld%lld",&in[i].first,&in[i].second);
	sort(in,in+n,cmp);
	
	ll ans=0,t=0;
	rep(i,n)
	{
		ans+=t*in[i].first;
		t+=2*in[i].second;
	}
	printf("%lld\n",ans);
	
	return 0;
}

3130 How I Mathematician Wonder What You Are!

問題概要

多角形Pがstar-shpaedであるとは、次のような点fが存在することを言う。
多角形内の任意の点pに対して線分fpが多角形Pの内部(または周)にある。


今n点からなる多角形を頂点の座標を反時計回りに与えられたとき、それがstar-shapedであるかどうか判定せよ。
n≦50を満たす。

解法

初めは全平面が候補に入る。
各辺に対して、辺の右側は内側に見えない部分ができてしまうため、右側の部分を切り落としていく。
残った部分がfの集合であるが、これが空かどうかを判定すればよい。

ソースコード

spaghetti source多角形の切断(http://www.prefield.com/algorithm/geometry/convex_cut.html)のコードを使用。

int main()
{
	int n;
	while(scanf("%d",&n),n)
	{
		G g,ng;
		g.pb(P(0,0)); g.pb(P(10000,0));
		g.pb(P(10000,10000)); g.pb(P(0,10000));
		
		int x[50],y[50];
		rep(i,n)scanf("%d%d",x+i,y+i);
		rep(i,n)
		{
			ng=convex_cut(g,L(P(x[i],y[i]),P(x[(i+1)%n],y[(i+1)%n])));
			if(ng.empty())
			{
				puts("0"); goto END;
			}
			g=ng;
		}
		puts("1"); END:;
	}
	return 0;
}