PKU演習問メモ(6/23)

PKU
No. 問題名 問題の種類および解法 難易度
3363 Annoying painting tool 貪欲法 ★☆☆☆☆
1018 Communication System 二分探索 ★★★☆☆
1416 Shredding Company 深さ優先探索 ★★☆☆☆
3273 Monthly Expense 二分法 ★★☆☆☆
1053 Set Me 総当り ★☆☆☆☆

3363 Annoying painting tool

問題概要

nxmマスのグリッド上に0,1が描かれている。r行c列の長方形の範囲の0,1を全て入れ替える操作が可能なとき、nxmマスが全て0状態から与えられた状態を作るまでの必要な操作の回数の最小値を求めよ。

不可能な場合-1を出力せよ。

解法

左上のマスが1の場合、左上のマスを端にするような長方形について反転操作をしなければ、どうやっても左上のマスを1にすることは出来ない。
その次に上で左から二番目のマスにも、三番目のマスにも……、二行目の左のマスも……と同様に考えていくと必要な操作の最低回数は一意に定まることがわかる。


操作をし終えた後で右および下の端に1が残ってしまったらその状態は作れない。

ソースコード
char field[100][101];

int main()
{
	int h,w,r,c;
	while(cin>>h>>w>>r>>c,h)
	{
		rep(i,h)cin>>field[i];
		int ans=0;
		for(int i=0;i<h-r+1;i++)for(int j=0;j<w-c+1;j++)if(field[i][j]=='1')
		{
			ans++;
			rep(k,r)rep(l,c)field[i+k][j+l]=field[i+k][j+l]=='0'?'1':'0';
		}
		rep(i,w)if(field[h-1][i]=='1')ans=-1;
		rep(i,h)if(field[i][w-1]=='1')ans=-1;
		cout<<ans<<endl;
	}
	return 0;
}

1018 Communication System

問題概要

n個の製品を作りたい。それぞれの製品にはバンド幅と価格があり、製品ごとに、どのラインから生産するかでバンド幅と価格が変わる。
今、各製品に対して一つずつ生産ラインを以下のように選ぶとき、そのB/P比の値を求めよ。

  • 各製品のバンド幅の最小値Bと、各製品の価格の和Pに対して、B/Pを最小にする。

N≦100,各製品の生産ラインの個数m[i]≦100を満たす。

解法

問題文が理解できなくて放置していた問題。
何度も読み返すと上のようなことを言っているらしい。


バンド幅の最小値Bを一つ決めると、残りは貪欲にバンド幅B以上の中で最も価格の安い生産ラインを選べばよいため、B/P比は一意に定まる。
したがってBの候補として全てのバンド幅を試してみればよい。

ただしバンド幅B以上で最も安い生産ラインを線形探索で探索するとループ回数が最悪1億になりおそらくTLEになる（試してない）ので、そこでは二分探索を用いる。
入力する時点で、製品におけるバンド幅Bに対する最も安い生産価格を求めておくことで上の二分法が可能になる。


またバンド幅の「最小値の最大値」、「最大値の最小値」の範囲を超えるようなバンド幅が最小バンド幅になることはありえないのでその範囲に限定して探索する。


以上、少しややこしいがコードにしたのが以下。
上位の回答は1〜2桁速いのでもしかしたら貪欲に最適解を求められるのかも。。。


[追記]他に解いてる方が居ないかと思って探してみた。線形探索で通るみたい、というか線形探索のほうが速いジャッジデータid:kusano_prog:20091213:1260687011

ソースコード
int n,m[100],minmax,maxmin;
pi pr[100][100];

double solve()
{
	cin>>n;
	rep(i,n)
	{
		cin>>m[i];
		rep(j,m[i])cin>>pr[i][j].first>>pr[i][j].second, pr[i][j].second*=-1;
		sort(pr[i],pr[i]+m[i]);
		for(int j=m[i]-2;j>=0;j--)if(pr[i][j].second<pr[i][j+1].second)
		pr[i][j].second=pr[i][j+1].second;
		rep(j,m[i])pr[i][j].second*=-1;
	}
	minmax=0; maxmin=inf;
	rep(i,n)
	{
		int mn=inf,mx=0;
		rep(j,m[i])mn=min(mn,pr[i][j].first),mx=max(mx,pr[i][j].first);
		minmax=max(minmax,mn); maxmin=min(maxmin,mx);
	}
	
	double ans=0;
	rep(i,n)rep(j,m[i])if(minmax<=pr[i][j].first&&pr[i][j].first<=maxmin)
	{
		int sum=0;
		rep(k,n)sum+=lower_bound(pr[k],pr[k]+m[k],mp(pr[i][j].first,0))->second;
		ans=max(ans,pr[i][j].first*1.0/sum);
	}
	return ans;
}
int main()
{
	int CS; cin>>CS;
	rep(cs,CS)printf("%.3f\n",solve());
	return 0;
}

1416 Shredding Company

問題概要

6桁以下の数字が与えられる。この数字を、それらの和が与えられたtを超えずにtにできるだけ近いような整数に分割したい。
そのような分割を出力せよ。

例：
入力
50 12346
に対して答えは
43 1 2 34 6

分割が不可能な場合は"error"を、同じ和になる分割が複数ある場合"rejected"をそれぞれ出力せよ。

解法

leading zeroは許可されるようだ。
問題文に"Neither integers may have a 0 as the first digit, e.g., 123 is allowed but 0123 is not."とあるのはなんなのだろう。


数字は6桁しかないので工夫全くなしの深さ優先探索で十分間に合う。

ソースコード

string使いまくりの実装。

int target,len;
string num;
int ans; bool dup;
vector<string> anss,strs;

void dfs(int c,int sum)
{
	if(sum>target)return;
	if(c>=len)
	{
		if(sum==ans)dup=1;
		if(sum>ans)
		{
			ans=sum;
			anss=strs; dup=0;
		}
	}
	for(int i=c+1;i<=len;i++)
	{
		strs.pb(num.substr(c,i-c));
		int t; stringstream(*strs.rbegin())>>t;
		dfs(i,sum+t);
		strs.erase(strs.end()-1);
	}
}

int main()
{
	while(cin>>target>>num,target||num!="0")
	{
		len=num.size(); strs.clear();
		dup=0; ans=-1;
		
		dfs(0,0);
		
		if(ans<0)cout<<"error"<<endl;
		else if(dup)cout<<"rejected"<<endl;
		else
		{
			cout<<ans; fr(i,anss)cout<<" "<<*i; cout<<endl;
		}
	}
	return 0;
}

3273 Monthly Expense

問題概要

N日間の歳出の予定が与えられる。N日間を、連続する何日かの月間"fajomonths"に分割する（各月間の長さは1日以上の任意）。
"fajomonths"の個数をM個にしたいとき、"fajomonths"の中で歳出が最大の月間の歳出が最小になるような"fajomonths"の作り方における最小値を求めよ。

N≦100000である。

解法

政治用語っぽいのが使われてるのですごく問題文が理解しにくい。日本語にしても理解しにくい。
要するに、数列を連続するM個の区間に区切って、各区間の和の最大値を最小にせよという問題。


定石どおり二分法でいける。

ソースコード
int n,m,money[100000];

bool ok(int lim)
{
	int s=0,ret=1;
	rep(i,n)
	{
		if(s+money[i]>lim)s=0,ret++;
		s+=money[i];
	}
	return ret<=m;
}

int main()
{
	scanf("%d%d",&n,&m);
	rep(i,n)scanf("%d",money+i);
	
	int lo=*max_element(money,money+n)-1,hi=accumulate(money,money+n,0),mid;
	while(lo+1<hi)
	{
		mid=(lo+hi)/2;
		if(ok(mid))hi=mid;
		else lo=mid;
	}
	cout<<hi<<endl;
	return 0;
}

1053 Set Me

問題概要

81種類のカードがある。カードには3通りの「模様の形」、通りの「模様の色」、3通りの「模様の塗り方」、模様の数が1〜3個のものがある。
この中から場に並べる12枚のカードの種類が与えられたとき、その中で可能な"Set"の作り方を、指定されたフォーマットで全て列挙せよ。


Setとは、形、色、塗り方、数が、それぞれ3枚のカードで異なるか全て同じような3枚のカードの組をいう。

解法

12枚のカードから3つのカードを調べるのは12C3通りしかないので、全ての組み合わせについてsetかどうか判定すればよい。
書かねばならないコードの量はやや多目かも。

ソースコード
char tab[15][9];
int ans,sets[4][3];

bool ok(int a,int b,int c)
{
	rep(i,4)
	{
		if(!(tab[a][i]==tab[b][i]&&tab[a][i]==tab[c][i])&&
			!(tab[a][i]!=tab[b][i]&&tab[b][i]!=tab[c][i]&&tab[c][i]!=tab[a][i]))
		return 0;
	}
	return 1;
}
void search(int found)
{
	rep(i,12)
	for(int j=i+1;j<12;j++)
	for(int k=j+1;k<12;k++)
	if(ok(i,j,k))
	{
		sets[ans][0]=i; sets[ans][1]=j; sets[ans][2]=k;
		ans++;
	}
}

int main()
{
	while(~scanf("%s",tab[0]))
	{
		rep(i,11)scanf("%s",tab[i+1]);
		ans=0;
		search(0);
		
		printf("CARDS: "); rep(i,12)printf(" %s",tab[i]); puts("");
		printf("SETS:   ");
		if(ans==0)puts("*** None Found ***");
		else
		{
			printf("1. "); rep(i,3)printf(" %s",tab[sets[0][i]]); puts("");
			if(ans>1)rep(i,ans-1)
			{
				printf("        %d. ",i+2); rep(j,3)printf(" %s",tab[sets[i+1][j]]); puts("");
			}
		}
		puts("");
	}
	return 0;
}