Rustコトハジメ

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

LCAを実装した

LCA (Lowest Common Ancestor)は、木構造の中でもっとも低い共通の祖先を調べるデータ構造です。 これはナイーブに実装すると、ノード数分だけ時間がかかってしまいますが、Sparse Tableと同様のアイデアを用いることによってO(logN)まで落とすことが出来ま…

Sparse Tableを実装した

Sparse Tableというのは、配列上のある範囲の最小値(あるいは最大値)を持ったインデックスを返すためのデータ構造(いわゆるRMQ)で、ナイーブに実装すると明らかにO(N)かかるが、Sparse Tableだと構築にO(NlogN)かかるがクエリ自体はO(1)で終わる。 その…

Chu-Liu/Edmondsアルゴリズムを強連結成分分解を使って実装した

www.rustforbeginners.com で、SCCについて説明しました。今回は、SCCを応用して、最小全域有向木を探すアルゴリズムを実装します。一番参考になったのはこちらです。アルゴリズムとしては同じですが、SCCを使って自分で実装してみます。 www.creativ.xyz ア…

強連結成分分解

強連結成分分解(Strongly-Connected-Components, SCC)をメモっておきます。 強連結成分というのは、有向グラフにおいて、そのグループに含まれている点は、どの点u,vをとってもお互いに行き来出来るというものです。例えばサイクルなどは明らかに強連結成…

フォードファルカーソン法の復習

一回理解したと思ったんですが、もう一度読んだら全く理解不能だったため、蟻本に書いてあることを自分の言葉で書き直して復習します。 フォードファルカーソン法というのは、辺の容量が与えられたネットワークにおいてs-tの最大流を求めるアルゴリズムです…

牛ゲーの解法

スマホゲームを作ったり他のブログをやってたら2ヶ月間、競プロの勉強から離れていて、戻ってみたら牛ゲーのことすらすっかり忘れていたのでここで復習しておきます。(ものは忘れかけた頃に復習するのが良いのです。2ヶ月も開けたのは意図的です) 牛ゲーと…

ijkがMoongiftで紹介された

www.moongift.jp www.rustforbeginners.com おれが開発しているエディタijkが、Moongiftに紹介された。 Moongiftというのは新しいオープンソース・ソフトウェアを紹介している記事サイトで、時々ツイッターなどで見ることがあり、気になったものがあれば読む…

エディタ開発で5400行もRustを書いてしまったおれが思うRustの良さ

VSCode形式のスニペットを読み、それをTrie木で管理し、挿入モードで文字が入力された時に候補となるスニペットを探し、それを表示し、バッファに挿入するということが一通り出来るようになりました。 実装はやや難解な点もあり、かなり疲弊したので開発はし…

combineを使ってVSCodeのスニペットのパーサーを書く

エディタアスペなので引き続きエディタ開発をしています。 GitHub - akiradeveloper/ijk: A real editor for real programmers エディタ開発の進捗 今回やること 出来たもの 解説 挙動 感想 エディタ開発の進捗 今はVSCode形式のスニペットを読み込んで、入…

test-generatorを使ってテストを自動生成する

自動テストを始めることにした経緯 自動テストの重要性 何をテストするか test-generatorライブラリを使う テストファイル追加を検知する 自動テストを始めることにした経緯 ijkを開発していて、ツイッターでバグレポをもらった。 ありえん。そうならないよ…

flameを使ってボトルネックを可視化する

私は今、エディタを開発しています。 Ijk: A real editor for real programmers - announcements - The Rust Programming Language Forum やるべきことは色々あるのですが、その中でもボトルネックを可視化する作業の優先度を上げました。なぜかというと、Ru…

impl T for Box<T>パターン

GitHub - akiradeveloper/ijk: A real editor for real programmers 現在、私はエディタを開発しています。その中で知った設計パターンについて紹介します。 問題の定義 解決編 STEP1: BoxをViewにしてみる STEP2: Vに?Sizedを足す STEP3: selfをderefしてあ…

AOJのBalls and Boxesを全クリして感じたこと

前に、AOJのコースをやっていて、その理由は網羅性があって学習の効率が良いからという話をしました。組み合わせ最適化(DPL)の問題の中に、Balls and Boxesというのがあり、 https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/5 ひたすら色々な問題設…

包除原理を応用する問題

自力で解けず、他人の解法を見て、DPを使う解法はわかったのですが、理解しがたい解法があって、むしろそっちの方がマジョリティだったので、みんなが知ってる解法だから理解する必要があると考えて、結局5時間かかりました。コードから包除原理にノーヒント…

エディタ開発を始めて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 全部の点を通って帰ってくる最短経路を…

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

個数制限付きナップザック問題にかなり苦戦したので、考え方を書き残しておきます。 個数制限つきナップザック問題とは 愚直に考えて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など意味のない値で初期化すると思います。…

分割数の漸化式の考え方

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?作者: 秋葉拓哉,岩田陽一,北川宜稔出版社/メーカー: マイナビ発売日: 2012/01/28メディア: 単行本(ソフトカバー)購入: 25人 クリック: …

AtCoder Beginners Selectionをやった

AtCoder Beginners Selection - AtCoder AtCoderが用意した「初心者はまず全部これを解くこと」的な問題集を全部解きました。なんと4時間かかりました。最後の最後に朦朧としていてミスを冒しましたが、初心者向けということもあり、さすがに簡単でした。 た…

cargo-snippetがRustを最高にする

競技プログラミングでは、提出物として一枚のソースコードにすべてを詰めることを要求されます。だから、ふつうは自分なりのライブラリを作って、それをコピペして使うことになります。まずはテンプレートを貼り付けて、それから使うライブラリを貼り付けて…

Copy trait and its applications

What is Copy trait What conditions should Copy trait satisfy The applications of Copy trait What is Copy trait Copy trait is a marker trait that claims the data is able to copy instead of move. So types that implement Copy trait have copy …

Copyトレイトとその応用例

Copyトレイトとは Copyトレイトが満たすべき条件 Copyトレイトの応用例 Copyトレイトとは Copyトレイトは、その値をまるまるコピー出来ることを表すマーカートレイトである。Copyトレイトを実装するとデフォルトのムーブからコピーになる。 pub trait Copy :…