WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
    }
};