SRM587 Div1 Easy & Div2 Medium "JumpFurther"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12300
訳
子ギツネのジローは階段の一番下の段に立っている。一番下の段は番号0が振られていて、そこから一段上がった段は番号1、さらに一段あがった段は番号2が振られ、それが同じように続いていく。階段はとても長く、ジローが一番上の段にたどり着く事はない事が保証される。
ジローはN回の行動を起こす。その行動に、順に1からNの番号を振る。行動Xを起こすとき、ジローは何もしないか、ちょうどX段ジャンプして上に上がるか、という2つの選択肢を選んでいく事になる。言い換えれば、ジローが段Yにいて、行動Xを起こすとき、段Yに留まるか、段Y+Xにジャンプするか・・である。
例えば、N=3であれば、ジローは1段ジャンプするのかしないのか、2段ジャンプするのかしないのか、3段ジャンプするのかしないのか・・3度選んでいく事となる。
段の1つは壊れている。この段の番号はbadStepとして与えられる。ジローはここに乗る事はできない。
あなたはNとbadStepという整数が与えられる。ジローが到達する事ができる、最大の段の番号を返せ。
制約
1 <= N <= 2000
1 <= badStep <= 4 * 10^6
考えた事
まず1回も待機することなく、badStepな段を踏む事がなく行動できるのであれば、その時の到達の段の番号を返せばよい。
それが無理なら、どれか1つの行動を待機してみて、いけるかどうか確かめる。その中でベストなものを選べばよい。
書いててなんかおかしい・・・
事後
kmjpさんのブログで書かれていたことだけど、一度も待機しないときに、運悪くbadStepな段を踏んでしまう場合、最初の1段上がる行動を待機すればよいのだ。
ソースコード
class JumpFurther { public: int furthest(int N, int badStep){ int sum = N * (N + 1) / 2; for( int i = 0; i <= N; i++ ){ int cul = 0; bool ok = true; for( int j = 1; j <= N; j++ ){ if( i == j ) continue; if( cul + j == badStep ) ok = false; cul += j; } if( ok ){ return sum - i; } } return 0; } };