Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

ワーシャルフロイド法で嵌ったらDPテーブルのインデックスは集合というパターンがみえた

中国人郵便配達問題 www.rustforbeginners.com でワーシャルフロイド法を使って全点間最小距離を求めましたが、私の初期の解答はAOJの37番目のテストでこけてしまい、色々試行錯誤して間違いに気づくのに1時間かかりました。 その間違いは、ワーシャルフロイ…

中国人郵便配達問題の考え方

中国人郵便配達問題とは 中国人郵便配達問題は、巡回セールスマン問題 www.rustforbeginners.com の類問ですが、すべてのノードではなく、すべてのエッジを通るという問題です。 https://onlinejudge.u-aizu.ac.jp/problems/DPL_2_B 名前の由来が気になった…

巡回セールスマン問題の考え方

巡回セールスマン問題が初見で解けなかったので、考え方をまとめておきます。 巡回セールスマン問題とは 考え方 コード 巡回セールスマン問題とは https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/2/DPL_2_A 全部の点を通って帰ってくる最短経路を…

個数制限つきナップザック問題の考え方

個数制限付きナップザック問題にかなり苦戦したので、考え方を書き残しておきます。 個数制限つきナップザック問題とは 愚直に考えてTLE 真の解法 01ナップザックに帰着 m個をlogm個に圧縮する 個数制限つきナップザック問題とは 個数制限つきナップザック問…

LCSを使ってLISを実装する

LISのことを考えていたら、これは入力列をソートしたものとのLCSで計算出来るのではないかとふと思ったので実験します。 具体的には、LIS(A) = LCS(A, A.sorted.dedup)ですね。 直感的には正しいような気がします。というか意味合いとしては、A.sorted.dedup…

コイン問題で嵌ったので反省文を書きます

コイン問題とは 最初の解答 TLEをアドホックに修正しましょう 最終解 勘違いの原因は何か? コイン問題とは コイン問題というのは、「ある金額を作るのに最小のコイン数」を求めなさいという問題です。日本の貨幣はうまく設計されているため貪欲法で自明です…

動的計画法でOptionを使うとわかりやすい説

DPではDPテーブルの初期状態を決める必要があります。それはふつう、漸化式から求まるのですが、下のナップザック問題を解くDPの場合、dp[0]=0が初期状態ですね。 そしてこの場合、C++など他の言語では他のマスを-1など意味のない値で初期化すると思います。…