Rustコトハジメ

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

エディタ開発を始めてRustが全くわかってないことがわかった

前回の投稿から22日間無投稿だったそうです。 とりあえず競プロ勉強を一旦休憩するために3日ほど旅行に出て、帰ったら再開するつもりだったのですが、ずっとエディタ開発をしてしまいました。 3週間ほどやってようやく報告出来る程度には成果が出たので、一…

ヒストグラムの中の最大の長方形を見つけるアルゴリズム

https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/3/DPL_3_C ヒストグラムが与えられて、その中にある長方形の最大面積を求めるという問題は日常生活で気にすることはありませんが、競技プログラミングでは結構重要なアルゴリズムなのではないかと思…

巨大ナップザック問題の考え方 (半分全列挙)

AOLのライブラリコースのうちDPLにはさまざまな種類のナップザック問題が詰め込まれており、どれもエッセンスとしては重複がないので良問と思いました。そのうち、巨大ナップザック問題の考え方を紹介します。初見では全く太刀打ち出来なかったです。 https:…

いっ・・・いもす法出たー

AOJのDSLを全部解きました。全部Rustです。 内容としては Union Find (重みつきもある) セグツリー (遅延多め) スライド 圧縮 いもす法 です。重要なトピックが詰まってると思いました。 自分としては、AOJのライブラリコースの中ではこのDSLとDPL(動的計画…

ワーシャルフロイド法で嵌ったら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 全部の点を通って帰ってくる最短経路を…