WARushスマートフォン用の表示で見るWARushSRMの結果とか、解けた問題のコードを書いていきますこの広告は、90日以上更新していないブログに表示しています。"ColorfulBuilding"問題http://community.topcoder.com/stat?c=problem_statement&pm=12583訳N個の高層ビルが左から右へと一直線に建っている。これらの建物は1~Nと番号が振られている。(ただし、左から右へと順番に番号が振られているとは限らない)あなたはどのように番号が振られているのか分かっていない。番号iのビルの高さはiである。N個のビルの高さは1~Nの順列となっている。それぞれのビルは、1つの色で塗られている。複数のビルが、同じ色で塗られている場合もある。あなたは、i番目のビルが塗られている色について分かっている。(その情報の詳細については後ほど詳しく説明する)あなたはこれらのビル群の左側の遠い位置に立っている。この場所からはビルは部分的に見えてくる。低いビルが、それより高いビルよりも遠い位置に建っていれば、それは隠れて見えなくなってしまうからだ。正確には、ビルXは、それよりも前の(ビルXよりも左側の)ビルが全てビルXよりも低ければ、(上側一部分かもしれないが)見えることになる。遠い位置から見ているため、あなたは同じ色の2つのビルを区別する事はできない。具体的には、同じ色のビルH1とH2があり、その間に違う色のビルが見えるように建っていなければ、その2つのビルは1つのビルとしてあなたには見える。3つ以上同じ色のビルが連なっていても1つのビルに見えてしまう。あなたにはL個のビルが見えている。言い換えれば、あなたの立っているところからはそのビル群はL-1回色が変わって見えるということである。color1を文字列連結したものをC1、color2を文字列連結したものをC2とする。これはビルの色を表していて、i番目のビルの色はC1[i]+C2[i]である。C2[j]であれば、2つのビルは同じ色である事を示す。これらの情報より、ビルの建ち方が何パターンあるかを返せ。計算量がヤバイからなぁ・・・。DPっぽいんだけど、ど~も上手い方法が分からん。解法コチラを参考にしました。あなたは嘘つきですかと聞かれたら「YES」と答えるブログwriterとしても活躍されてるsnukeさんのブログですね。ありがとうございます。DP!!しかし・・・しかし、番号N~1の順番でビルを置いていくのだという。ここですでに「ええっ!そ・・そんなDPのやり方があるのか!」である。色は無視して、ビルとビルの区別が必ずできるとしたときに、どのようにDPしていけばいいのか考える。場合の数とDP式を立てると、この問題は解く事ができる。その他は00個ビルを置いて、見えるビルは0個なので、それは1パターンあるのである。・先頭(一番左)においた場合この場合、見えるビルは1つ増える。]の最初の更新のため)・それ以外この場合、見えるビルは増えない。置ける場所は既にビルが置かれている数分だけある。