WARush

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

SRM585 Div1 Easy "TrafficCongestion"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=11361

いくつかの都市があり、道路でつながっている。道路網の構造は、都市をノード・道路をエッジとしたときに完全二分木になっている。

あなたは木の高さを表すint treeHeightが与えられる。(完全二分木の高さとは、木のルートノードとリーフノードを結ぶ道路の数である)したがって、2^(treeHeight+1)-1だけの都市と、2^(treeHeight+1)-2だけの道路の数があることになる。

私たちはいくつかの車をこの道路網に送りたい。それぞれの車は出発する都市から目的の都市まで、同じ年を2度通らずに走る。(それぞれの車のルートは、出発地と目的地によって、一意に決められる事に注意せよ)出発する都市と、目的の都市は同じでもよく、この場合車は1つの都市を訪れるだけである。

私たちの目的はそれぞれの都市を訪れる車をちょうど1台にして、車を送り出すことである。このようにしたときに、送り出す車の最小を返せ。

制約

0 <= treeHeight <= 10^6



Editorialsを見て

一応実装してみた。

イマイチ理解できない・・・はぁ・・・
Div2のとは制約のみ違います。




ソースコード

const int MOD = 1000000007;

long long s[1000050];

class TrafficCongestion {
public:
    int theMinCars(int treeHeight){
        long long ans = 1;
        s[0] = 1;
        s[1] = 2;
        for( int i = 2; i <= treeHeight; i++ ){
            ans = (s[i-2] * 2 + 1) % MOD;
            s[i] = (ans + s[i-1]) % MOD;
        }
        return (int)ans;
    }
};