Hatena::Grouptopcoder

yuyarinのtopcoder記

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

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

2010/09/28

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/

2010/05/24

Google Code Jam 2010 Round 1A B. Make it Smooth

| 16:01

http://code.google.com/codejam/contest/dashboard?c=544101#s=p1

解き方がわからなかった問題に再チャレンジ.

問題

最長 100 個の [0,255] の値(文字)が入った配列(文字列)が与えられる.隣り合う要素の差が M 以内であればこの文字列は smooth であるという.文字列に対して削除,置換,挿入の3操作が可能である.削除のコストは D で与えられ,置換のコストは置換前後の数値の差で定義される.挿入のコストは1要素につき I で与えられる.

このとき与えられた文字列を smooth にするために必要なコストの最小値を求める.

アプローチ

与えられた文字列に対してレーベンシュタイン距離の最小となるような文字列を作る操作を求める問題と等価である.

当たり前だけど,各文字を適当に固定して分岐して行く方法だと 255^100 以上の計算量になる.

と考えて実はこれやっぱりまさに典型的に DP で解けるのではないかと気付く.

(100 文字 + 頭 1)×(255 値)の配列 dp[101][256] を用意して,コストを代入して行く. dp[i][j] には i-1 番目の文字が j で i 番目の文字を決める直前のコストを代入する.

dp[0][j] は 0 で,他は十分大きな値にする(*1).INT_MAX を使ってしまうとコストを足したときに簡単に integer overflow を起こすので適度に大きくする.

前の文字 v[i-1] が j に決まったときに v[i] をある値 k に決めるコストを求めていき,k に決めた操作の中でコストが一番小さいものを取る.

これを繰り返して最後に N 文字目のコストで一番小さいものをとる(*2).

削除

v[i] を削除したときの累積コストは dp[i][j]+D である(*3).

変更

v[i] を文字 k に変更したときの累積コストは dp[i][j]+abs(v[i]-k) である(*4).ただし変更は M 以内に収まるような場合のみを行う.

挿入

j → k をつなぐ挿入を行うコストは I*((abs(k-j)-1)/M+1) である.

ここで気をつけなくてはいけないのが,v[i] の前,つまり v[i-1]=j → v[i]=k について挿入操作を行うのではなく,v[i] の後に行うということである.v[i]=j の後に,最後の文字が k になるように挿入を行うと, v[i+1] はあたかも v[i]=k に見える.

ポイントはこの挿入の操作は削除,変更を行ってコストを決めた後の v[i] に対して行うということである.

これを考慮しないと,値の変更・削除を行ってからその間に挿入を行う方がコストが安いケースに対応出来ない.

ここでハマった.

なので累積コストは dp[i][j]+I*((abs(k-j)-1)/M+1) ではなく dp[i+1][j]+I*((abs(k-j)-1)/M+1) とし,削除と挿入の後にコストの改善を行わなくてはならない.

ソースコード

以上のことをまとめるとこういうコードになる.

  • 挿入のところの if(k!=j) が必要ないので削除(2010/05/27 10:07)
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>

using namespace std;

typedef vector<int> VI;

#define Rep(i,n) for(int i=0;i<(n);++i)
#define MN(a,b) a = min(a,b)

// 128 >= 100 chars + 1
// 256 = (0..255)
int dp[128][256];

int solve(int D, int I, int M, int N, VI &v)
{
	// initialization (*1)
	Rep(i,N+1) Rep(j,256) dp[i][j] = 10000000;
	Rep(j,256) dp[0][j] = 0;
	
	Rep(i,N)
	{
		//delete v[i] (*3)
		Rep(j,256)
			MN(dp[i+1][j], dp[i][j]+D);

		// modify v[i]=j to k (*4)
		Rep(j,256)
			Rep(k,256)
				if(abs(j-k)<=M)
					MN(dp[i+1][k], dp[i][j]+abs(v[i]-k));

		// insert chars after v[i] = j
		// the last inserted char is k (*5)
		if(M>0)
			Rep(j,256)
				Rep(k,256)
					MN(dp[i+1][k], dp[i+1][j]+I*((abs(j-k)-1)/M+1));
	}
	
	// (*2)
	int r = INT_MAX;
	Rep(j,256)
		MN(r,dp[N][j]);
	
	return r;
}

int main(int argc, char* argv[])
{
	int T;
	cin >> T;
	
	Rep(t,T)
	{
		int D, I, M, N;
		cin >> D >> I >> M >> N;
		VI v(N);
		Rep(n,N)
			cin >> v[n];
		int r = solve(D, I, M, N, v);
		cout << "Case #" << t+1 << ": " << r << endl;
	}
	
	return 0;
}

忍者最終号忍者最終号2010/05/24 14:291を数えないようにした方がもっと早くなりそうだ.

yuyarinyuyarin2010/05/27 10:16あ,本当ですね.
そのようにしてみました.

2010/05/23

Google Code Jam 2010 Round 1B C. Your Rank is Pure

| 04:38

http://code.google.com/codejam/contest/dashboard?c=635101#s=p2&a=0

問題

正数の集合 S の中においてある数 n が pure である条件がある.n が S の中で r 番目の数であるとき n のランクは r であると言う.n のランクが r1 であり,数 r1 のランクが r2 であり,,,としていき最後に 1 にたどり着けば n は pure であると言う.

与えられた n について, S = {x|x∈[2,n]} の部分集合 S' において n が pure であるような S' の作り方の個数を求める.

結果

small は correct だったけど提出するコードを間違えた.

large は答えを出したけど,提出がギリギリで駄目だったけど,admin に問い合せろとエラーが出た.

なので問い合わせ中.

→提出は + 0.674 秒遅かったらしい.そう計測された以上 reject とのこと.正しいソースコードの再アップロードと,エラーの理由はスルーされた.

large-practice では正解を出せていた.

アプローチ

数字 n がランク r として出現するときの場合の数を求める.

DP でも解けるけど DP にせずに再帰とキャッシュ(*1)を使った.

r〜n の間に m 個(m∈[0,r-2]) の数字が入る場合(*2)の数は Combination(n-r-1,m) で(*3),1〜r の間に数字が入る場合の数は数字 r がランク r-m-1 で現れる場合の数なのでこの関数の再帰で求められる.これらを掛け合せたものが,数字 n がランク r として出現するときの場合の数である(*4).

この関数を入力 n に対して,数字 n がランク r∈[1,n] として出現するときの場合の数の合計を計算してあげれば良い(*5).

Combination を求める部分で Integer Overflow を起こしそうな気配なので,gmpxx にお世話になった.

ソースコード

提出コードから掲載コードへの変更点

  • キャッシュ部分をマクロ化.
  • include 順序の整列,改行の追加削除等,表示を見やすくするもの
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <iostream>

// using The GNU Multiple Precision Arithmetic Library
// http://gmplib.org/
// compile with -lgmpxx -lgmp
#include <gmpxx.h>

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())

#define make_cache(...) map< __VA_ARGS__ > cache;\
map< __VA_ARGS__ >::iterator cache_it;
#define cache_hit(query_) (cache_it=cache.find(query_))!=cache.end()
#define check_cache(query_) if(cache_hit(query_)) return (*cache_it).second;
#define store_cache(key_,value_) cache.insert(mp(key_,value_))

make_cache(pair<int,int>,mpz_class)

mpz_class func(int n, int r)
{
	if(r==1) return 1;
	
	// *1
	check_cache(mp(n,r));
	
	int N = n-r-1;
	int M = r-2;
	mpz_class ans = 0;
	
	// *2
	for(int m=0; m<=M; m++)
	{
		if(N<m) continue;
		mpz_class p=1;
		// Combination(N,m) *3
		for(int j=0; j<=m-1; j++)
			p *= (N-j);
		for(int j=2; j<=m; j++)
			p /= j;
		// *4
		ans += p*func(r, M-m+1);
	}
	
	// *1
	store_cache(mp(n,r),ans);
	
	return ans;
}

int solve(int n)
{
	mpz_class ans = 0;
	// *5
	for(int i=1; i<n; i++)
		ans += func(n, i);
	ans %= 100003;
	return ans.get_si();
}

int main(int argc, char* argv[])
{
	uint T;
	cin >> T;
	
	for(uint t=0;t<T;t++)
	{
		uint n;
		cin >> n;
		cout << "Case #" << t+1 << ": " << solve(n) << endl;
	}
	
	return 0;
}

AndiAndi2011/07/22 15:08Thanks alot - your answer solved all my problems after several days srtuglging

ymztwdpymztwdp2011/07/26 00:50iMKSlH , [url=http://vxqonjgohmzr.com/]vxqonjgohmzr[/url], [link=http://bdghiksyjeoz.com/]bdghiksyjeoz[/link], http://fqpjpgeffbmu.com/

EgwoloEgwolo2013/02/16 23:19Thanks for contributing. It's helepd me understand the issues.

zzokgazzokga2013/02/19 14:25gNeh7s <a href="http://jdxldqxslfbx.com/">jdxldqxslfbx</a>

ealpalshhtealpalshht2013/02/19 14:25ftpxVI <a href="http://cpdedlynamuf.com/">cpdedlynamuf</a>