Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/09/28

SRM 483 Div1

| 00:55

SRM 483 Div1 Room 4

久々の SRM

250 pt. を取れていると思ったらまさかの Failed System Test.

500 pt. を開いて他制約ナップサック(ナップサックが複数並列して存在するような問題)だと思い解き方に悩み,解けずじまい.

0 point で rating down.アルゴリズムの勉強をちゃんとできないまま挑んでいるので,次あたりそろそろヤバそう.

Room では target, vlad89 による 900 pt. 虐殺タイムが始まる.結果,意外と 250 も落ちている人が多かった.

Petr がまさかの1問も解けていなかったせいで,今週は雨です.

Coding Phase153.28
Challange Phase0.00
System Test-153.28
Point Total0.00
Division Placed464
Old Rating1259
Pating Change-31
New Rating1228
ProblemProblem NameCoding TimeStatusPoints
250ptBestApproximationDiv10:26:21.693Failed System Test153.28
500ptBribes0:48:25.257Opened0
900pt------Unopend0

SRM 483 BestApproximationDiv1

| 00:55

http://www.topcoder.com/stat?c=problem_solution&rm=305892&rd=14236&pm=11023&cr=22851423

問題

与えられた数より小さい分母を持つ分数の中から,与えられた 1 より小さい小数点以下6桁の小数を最もよく近似する分数を見つける問題.

アプローチ

分母を小さい値から固定していき,分子を近似対象の小数と分母の掛け算で決定.誤差があるので分子は floor と ceil の両方を計算する.

本番では Failed System Test だった.理由は作った分数の小数表現を sprintf("%.8f") で作ったから.sprintf は指定桁数以下の値を四捨五入してしまうので小数点以下7桁目以降が 995 より大きいテストケースだと失敗する."%.10f" で失敗するケースは無かった模様.

Test Case: 138
Args: {1000, "0.812983"}
Expected: "313/385 has 6 exact digits"
Received: "526/647 has 7 exact digits"

こうした誤差を最初から出さないためには 10^6 倍して整数として計算するのがよい.問題はこの方法でも int の範囲内で計算できるように設計されているようだ.

*

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

inline int toi(string s){int v; istringstream iss(s);iss>>v;return v;}
template<class T> inline string tos(T x){ostringstream oss;oss<<x;return oss.str();}

#define For(i,a,b)    for(int i=(a);i<(b);++i)

string findFraction(int maxDen, string number)
{
	int ml = 0;
	int mn = 0;
	int md = 0;
	int num = toi(number.c_str()+2);
	
	For(d,1,maxDen+1) For(dd,0,2)
	{
		int n = num*d;
		n -= n%1000000;
		n += dd*1000000;
		int x = n/d;
		int y = 100000;
		int l = 1;
		For(i,0,6)
		{
			if(x/y!=num/y) break;
			l++;
			y /= 10;
		}
		if(l>ml)
		{
			mn = n/1000000;
			md = d;
			ml = l;
		}
	}
	
	char s[64];
	sprintf(s, "%d/%d has %d exact digits", mn, md, ml);
	
	return string(s);
}

SRM 483 Bribes

| 00:55

http://www.topcoder.com/stat?c=problem_solution&rm=305892&rd=14236&pm=11037&cr=22851423

問題

選挙において投票者に最小限の賄賂を渡して勝つようにする.n 人の投票者がいて,それぞれ影響度 influence と抵抗度 resistance が存在する.i 番目の人に賄賂を渡すと,j 番目の人の抵抗度が influence[i]/2^|i-j| だけ減る.全員の抵抗度が 0 以下になれば賄賂は成功する.賄賂が成功する渡し方のうち,賄賂を渡す人数が最小になる人数を返す.できなければ失敗として -1 を返す.

アプローチ

一見すると O(n*2^n) な複数ナップサック問題のように見えるが,影響度の値が 500 以下,つまり 2^9 より小さいので両隣 8 人目まで考慮すればいいことが分かる.これで 2^n の部分が 2^17 の定数で押さえられるので O(n).で解くことができる(定数項はそれなりに大きいので注意).

両隣 8 人を含めた計 17 人への賄賂を 17-bit で表現することができる.DP の問題の分割は投票者の人数で行うことができる.つまり0人,1人,と増やしていく.i 人目の抵抗度を 0 にするには i-8 人目から i+8 人目までの影響度を考慮すればいい.抵抗度を 0 にできるパターンの中から最も賄賂を渡す人数が少ないパターンを記録している. i+1 人目を計算するには i 人目のビットパターンのうち上位 16-bit だけ分かればよいので,配列に保存するのは 16-bit 分で良いことが分かる. n 人目まで繰り返していき,最小の値(人数)を選ぶ.

配列のサイズが大きいので int では allocate できない.short を使う.

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

#include <cmath>

using namespace std;

#define sz(a) int((a).size())
#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)

short dp[51][1<<16];

int minBribes(vector <int> influence, vector <int> resistance)
{
	int n = sz(influence);
	int INF = 100;
	
	Rep(i,n+1) Rep(j,1<<16)
		dp[i][j] = i ? INF : __builtin_popcount(j);
	
	Rep(i,n) Rep(mask,1<<17)
	{
		int sum = 0;
		for(int j=i-8,k=0; j<=i+8; j++,k++)
			if((mask&(1<<k)) && 0<=j&&j<n)
				sum += influence[j]>>abs(j-i);
		if(sum>=resistance[i])
			dp[i+1][mask>>1] = min(
				(int)dp[i+1][mask>>1],
				(int)dp[i][mask%(1<<16)]+mask/(1<<16)
			);
	}
	int r = INF;
	Rep(j,1<<16)
		r = min(r,(int)dp[n][j]);
	
	return r>n ? -1 : r;
}

SRM 483 Sheep

| 03:36

http://www.topcoder.com/stat?c=problem_statement&pm=10920&rd=14236

問題

重さのある羊がたくさんいる.これを重量の容量がある船に乗せて川を渡らせる.乗せる羊の選び方は,残り容量以下で重い方から選んでいく.与えられた回数以下で全ての羊を渡らせるときに,船の最小の容量を求める.

アプローチ

ぱっと見,何の変哲もない二分探索の問題であるが落とし穴がある.

ある容量で回数内に運べるからといって,それより大きい容量で運べるとは限らないからである.chokudai 氏がテストケースを挙げている

900のチャレンジケース 14,3,"100 60 50 39 35 30 30 30 25 25 24 20 9"less than a minute ago via P3:PeraPeraPrv

すげえwwwどうやって見つけたんだwww出典

容量 159 で成立するけど 160 では成立しないケースのようである.

というわけで二分探索で求めた後,前を 2000 個ほど探索している.この 2000 という値には全く根拠がないのだが(しいて言えば羊の重さの上限),本当にこれでいいんだろうか・・・?

※追記:wata さんによれば,(羊の重さの合計)/(運べる最大回数)から(羊の重さの合計)/(運べる最大回数)+(羊の最大の重さ)までに必ず解があると証明できるとのこと.

昨日の900の証明って別に簡単だよね 全部の和/回数+最大重みがあれば、極大サイズが全部の和/回数以上になるので絶対可能 よって全部の和/回数から+2000調べればよいless than a minute ago via HootSuite

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

#include <set>
#include <algorithm>
#include <numeric>

using namespace std;

#define sz(a) int((a).size())
#define All(a)  (a).begin(),(a).end()

#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)
#define Each(i,c)     for(typeof((c).begin()) i=(c).begin();i!=(c).end();++i)

bool judge(multiset<int> s, int c, int maxRuns)
{
	int runs = 0;
	multiset<int>::iterator it;
	while(sz(s))
	{
		int cc = c;
		while(cc>0&&sz(s))
		{
			it = s.upper_bound(cc);
			if(it==s.begin()) break;
			it--;
			cc -= *it;
			s.erase(it);
		}
		if(++runs>maxRuns)
			return false;
	}
	
	return true;
}

int minCapacity(int numSheep, int maxRuns, vector <string> part1, vector <string> part2, vector <string> part3, vector <string> part4)
{
	multiset<int> msi;
	string str;
	int n;
	Each(s,part1) str+=*s;
	Each(s,part2) str+=*s;
	Each(s,part3) str+=*s;
	Each(s,part4) str+=*s;
	istringstream iss(str); while(iss>>n) msi.insert(n);
	int sum = accumulate(All(msi),0);
	int max = *max_element(All(msi));
	
	for(int capasity=sum/maxRuns; capasity<=sum/maxRuns+max+1; capasity++)
		if(judge(msi,capasity,maxRuns)) return capasity;
	return -1;
/*
	// binary search version
	int min = *max_element(All(msi));
	int max = accumulate(All(msi),0);
	
	while(max-min>1)
	{
		int mid = (min+max)/2;
		if(bs(msi,mid,maxRuns))
			max = mid;
		else
			min = mid;
	}
	
	For(c,min-2000,max)
		if(bs(msi,c,maxRuns)) return c;
	
	return max;
*/
}

ttvijfyomttvijfyom2011/02/27 18:44XXnJye <a href="http://idnbvnetymog.com/">idnbvnetymog</a>, [url=http://ftuabcqbiduw.com/]ftuabcqbiduw[/url], [link=http://gwxepxsaficy.com/]gwxepxsaficy[/link], http://judtzquinqwh.com/