初めてDPっぽい問題のDPっぽい解答方針を自分で立てられた気がする。 DPというのは、「昨日までの結果が分かれば今日の結果はすぐわかっちゃうぜ」という問題に対する汎用的なメソッドだということがやっと理解出来た。 初めてDPを習ったのは多分大学3年の算…

やるだけ。 topcoderはグラフは隣接行列の文字列表現で与えられるぽいのでそれの練習的な。 このコードでは重複の処理を考えたくないので2友達かどうかを示すフラグテーブルを構成しているけど、@chokudai さんのライブコーディングではちゃんと重複が起こら…

DPの問題 格子状の道のある格子から別の格子に行くには何通り？という典型的な問題と同じタイプ。 但し、動きが複雑なのでちょっと見通しにくくなっている。 また、格子状の道と違い、あるマスからあるマスまで行く時に、行き方によってステップ数が異なるの…

メモ化再帰版 再帰する時に、同じ計算を何回もやるような場合は、メモを入れちゃえば、圧倒的に早くなる。 DPと両方使えるようになりたい。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #include <set> #include <cctype> #include <queue> #include <stack></stack></queue></cctype></set></utility></iostream></algorithm></map></vector></string></sstream>…

だいぶDPとメモ化再帰を行き来出来るようになった。 ただ、下のコードは桁あふれでシステムテストが通らない。 桁あふれぢゃないのかな。だけど、手元では合ってるんだよな。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #inclu</utility></iostream></algorithm></map></vector></string></sstream>…

適当な人を1番と決めて、時計回りに2, .., nと番号を振る。この時、1と3が握手しちゃうと、2が誰とも握手出来ない。同様の理由で、1が握手し得るのは2, 4, ..., n だけ。で、1とiの人が握手すると円卓がnより真に小さい部分グループに分かれる。この問題の構…