マトリョーシカ的日常スマートフォン用の表示で見るマトリョーシカ的日常ワクワクばらまく明日のブログ。2013-04-15Topcoder基本のき:全探索、再帰、メモ化をマスターする!やりかた避けては通れない道この前のSRMはレジスターに間に合わなかったので参加できず。僕も動的計画法を勉強しなくてはいけない。レベル2でも時々使うからだ。500]ここで勉強し始めたのだが、Javaで書かれていることもあり、よく分からないところがあった。なんとかメモ化までできたので自分なりの解説を交えながら、コードを晒していく。なんという羞恥プレイ。level1を問題にして、全探索、再帰、メモ化、そして動的計画法を解説している。王様は長い間出張していたので、できるだけ早く女王のもとに帰りたいと思っています。対して陸路と空路があります。王国の科学力は低く、空路による移動は墜落の危険を伴います。回までに留めるように言いました。王様が王女に会うための最短時間を求めなさい。Statementコードのひな形これからいくつかコードを載せていくが、それらをコピペしてコンパイルしても何にもならない。煩雑になるのを避けて同じ部分を書いていないためだ。先に進む前にコードのひな形てきなあれを紹介する。HEREの間の文字列はtopcoderのテンプレを設定すると、問題を開いたときに自動的にテストケースのコードを書いてくれるものだ。#2...PASSEDなどと書いてくれる。間違っている場合も指摘してくれる。これ以降はテストケース#0の場合を考えて図を貼っている。先ほど解説サイトとは少し数値が違うので注意してほしい。全探索まずは全探索でKの制限がない場合で書いてみる。ビットが立っている場合を空路とみなす、と書いてあるが、二進法の要領で陸路か空路かを選ぶことだ。C++ではべき乗の演算子がない。