ぐぬぬ・・・

プログラミング Codeforces コンテスト

http://d.hatena.ne.jp/heisseswasser/20100618/1276827953
ということで、解説〜

#include <iostream>
using namespace std;

struct Info
{
	int	n;
	int	d;
	int	m;
	int	l;

	Info() :n(0),d(0),m(0),l(0)
	{}
};

int step(int s, const Info& info)
{
	const int cur_pos = s * info.d;
	if( cur_pos > (info.n-1) * info.m + info.l ) 	{ return s; }	//out of last platform
	if( (cur_pos % info.m) > info.l )		{ return s; }	//fall down info gap between platforms

	return step(s+1, info);
}

Info GetInfo()
{
	Info info;
	cin >> info.n >> info.d >> info.m >> info.l;
	info.n -= 1;	//n as maximum index of platforms
	
	return info;
}

int main()
{
	const Info 	info = GetInfo();
	const int 	adv = step(0, info);

	cout << adv * info.d;
}

まず英語でコメントが書いてある時点ですごいですよね。
英語とか私には出来ないです＞＜；；

1つ目

GetInfo()内で

	info.n -= 1;	//n as maximum index of platforms

としてるのに

	if( cur_pos > (info.n-1) * info.m + info.l ) 	{ return s; }	//out of last platform

と、条件のところでまた1引いてます。
一番簡単な例として n = 1 を考えると 0 が答えになっちゃうのがすぐに分かるかと思います。
ということで、ここがまず1つ目。

2つ目

問題文を見ると各値の範囲は 1 ≤ n, d, m, l ≤ 106, l < m となっています。
ということで、例えば
n = 1000000
d = 2
m = 1000000
l = 999998
のようなテストケースを考えましょう。
この場合最終的な位置はどこになるでしょうか？
1つ目のプラットフォームを超えると2つ目のプラットフォーム内での位置は一番最初、つまり1つ目のプラットフォームと同じような状態となります。
つまり、これは落ちずにずっと続くことになります。
ではどこに落ちるかと言うと n ( = 1000000 ) 回目のプラットフォームを超えたとき、すなわち 1000000000000 = 1012 で落ちることになります。
これはintの範囲を大きく超えてます。
ということで、型にはintではなくlong longなどを使いましょう。


こういう問題では値の範囲をしっかり考えて余裕が持てるような型を選択しましょう！
むしろ、こういう問題はこういったオーバーフローが発生するように問題が設定されているので特に注意です！

3つ目

さてさて、2つ目と同じテストケースを考えましょう。
この答えは 1012 でした。
つまり、再帰は 1012 回となることになります。
なぜこうなるかといえば同じプラットフォーム内でのジャンプでも毎回ちゃんとジャンプしているためです。
ということで、こういうのは1回にまとめちゃいましょう！
つまり、1回の再帰は1回のジャンプに相当するのではなく、1回のプラットフォーム分のジャンプにまとめてしまうのです！
1つ目のプラットフォームでは l / d + 1 = 999998 / 2 + 1 = 500000 回ジャンプするのでこれを1回にまとめると 1 / 500000 に減ります。


ちなみに、ここは自分もハマった点です。。。
ここの処理に手を抜いたためにTLEに・・・orz

4つ目

さて、2つ目の処理で 500000 回 が 1回 にまで落ちました。
が、先のテストケースを見るとまだ m ( = 1000000 ) 回再帰することになります。
これはやっかいです。
これを減らそうとしたいのですが、うまくいきません・・・
で、頑張ってスタックを潰さないように引数を全部外に出してローカル変数も全部外に出しました。
ちなみにこうなりました。

#include <iostream>
using namespace std;

struct Info
{
	int	n;
	int	d;
	int	m;
	int	l;

	Info() :n(0),d(0),m(0),l(0)
	{}
};

long long s;
Info info;
long long cur_pos;
long long j;

long long step( void )
{
	cur_pos = s * info.d;
	j = ( ( cur_pos / info.m ) * info.m + info.l - cur_pos ) / info.d;
	if( cur_pos > static_cast<long long>(info.n) * info.m + info.l ) 	{ return s; }	//out of last platform
	if( (cur_pos % info.m) > info.l )		{ return s; }	//fall down info gap between platforms

	s += j + 1;
	return step();
}

Info GetInfo()
{
	Info info;
	cin >> info.n >> info.d >> info.m >> info.l;
	info.n -= 1;	//n as maximum index of platforms
	
	return info;
}

int main()
{
	info = GetInfo();
	s = 0;
	const long long	adv = step();

	cout << adv * info.d;
}

が、やっぱりスタックが足りません。
うむむ・・・

結末

で、よく見るとstep()関数は最後にstep()を呼び出してるだけなのでこれwhile(true)でいけるんじゃない？というふうになり、

#include <iostream>
using namespace std;

struct Info
{
	int	n;
	int	d;
	int	m;
	int	l;

	Info() :n(0),d(0),m(0),l(0)
	{}
};

long long s;
Info info;
long long cur_pos;
long long j;

long long step( void )
{
	while( true ) {
		cur_pos = s * info.d;
		j = ( ( cur_pos / info.m ) * info.m + info.l - cur_pos ) / info.d;
		if( cur_pos > static_cast<long long>(info.n) * info.m + info.l ) 	{ return s; }	//out of last platform
		if( (cur_pos % info.m) > info.l )		{ return s; }	//fall down info gap between platforms

		s += j + 1;
	}
}

Info GetInfo()
{
	Info info;
	cin >> info.n >> info.d >> info.m >> info.l;
	info.n -= 1;	//n as maximum index of platforms
	
	return info;
}

int main()
{
	info = GetInfo();
	s = 0;
	const long long	adv = step();

	cout << adv * info.d;
}

となりました。
で、Codeforcesに投げてみたら見事通りました。
やったね♪


・・・あれ？
再帰はどこにいっちゃったんでしょうね？＞＜

まとめ

僕には再帰では書く力がありませんでした＞＜
誰か代わりにお願いします＞＜；；；