読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

TopCoder SRM 587 Div1 Easy JumpFurther

今回は不参加。Easyが最終的な回答の割に手間取ったけど、Mediumが400pt以上とあっさり解けていた。
今回参加していればかなり上位に入れたのに…残念。
http://community.topcoder.com/stat?c=problem_statement&pm=12300

問題

数Nが与えられる。
無限に続く階段があり、1~NのN回のステップにおいて、i回目はその場にとどまるか、i段上がるかを選択できる。
badStep段目を使えない場合、最大何段目まで上がれるか答えよ。

解法

最初は無駄にDP風にやって時間を無駄にした。
とりあえず登れるところまで全力で登り、途中badStep目に遭遇した場合、初回の1段だけなかったことにすれば、あとはそこをスキップして登れる。

class JumpFurther {
	public:
	int furthest(int N, int badStep) {
		int i,sum=0;
		FOR(i,N) {
			if(sum+(i+1)==badStep) sum+=i;
			else sum+=i+1;
		}
		return sum;
	}
};

まとめ

Div1でこれだけ短く書けるのは珍しい。

広告を非表示にする