典型90問をRustでやっていく その1
おはようございます。
今回はタイトル通り典型90問をやっていきます。
この記事には
- 前書き
- 各問題の考察・感想などと、Rustで詰まった部分
- その他雑談
が含まれます。苦手な方はご注意ください。
前書き
大学で途中から競プロやる余裕がなくなってしまって歯がゆい思いをしていましたが、社会人になったらかえって時間ができたので、復帰がてら解いていきます。
折角なので流行りのRustを覚えつつやっていこうと思います。
「典型90問を解いてみた」系の記事は沢山あるので、今回は「Rustを始めてみたいな~」と思ってる人に多少役立つ内容を目指せればと思います。
と言っても文法とかは自分で調べていただくのがよいと思います。「素人はここで躓きました!」みたいなメモとしてご利用ください。
Rustよくわからんまま書いてるので間違いがあったらごめんなさい。
典型90問 なに
E8さん(https://twitter.com/e869120)という高校生時代からレッドコーダーの凄い人が企画・作題された90問の問題集です。
競技プログラミングで出てくる典型的な要素を詰めた教育コンテンツで、僕ぐらいの層(AtCoder灰~青)にちょうど良いっぽいです。
ご本人が詳しく解説されてるので、こちらをご覧ください。
E8さんは昨年末に本を出されているので、こちらも是非。
Rust なに
Rustはプログラミング言語のひとつです。
特徴として
- 生成コードの実行速度がC/C++レベルで速い
- 安全性の高いコードが書きやすい
- 利用可能な範囲が広い(組み込みからwebまで様々)
- モダンな文法や機能(これよくわからないまま言ってます みんな言ってるので多分あってます)
などがあります。
競プロにおける難点としては次が思い当たるので敬遠してました。
proconioという素敵なライブラリが用意されたので、入力受け取りが面倒な問題が解決されました。
という訳で今回はその他の難点をこちらでどうにか対処出来ればと考えています。
競技プログラミング なに
この記事見に来てて知らないなんてこと流石にないでござるよ~(笑)
おまえ だれ
ぼく こるぼー(@zero_kpr)
きじにしてき れんらく くれ
夢月ロア だれ
かわいい だいすき
はよもどってきて
環境構築
ではやっていきます。
と言ってもここ長くする気はないので、こんな感じのツールがあって便利だよ~という話だけします。
コンパイラ・ビルドツールなど
rustupというツールに各種ソフトが含まれています。インストールはこちら(https://www.rust-lang.org/ja/tools/install)
rustupにはCargoというソフトが入っています。
エディタ
vscodeを使います。ここは別に他のエディタでもあまり変わらないと思います。
拡張機能でrust-analyzerを入れましょう。
rust-analyzerはrustのリンターやコード補完、フォーマッターなどの機能を含む拡張機能です。
余談ですがLSP(Language Server Protocol)というのがあるらしく、そのおかげでrust-analyzerを他のエディタでも使えるみたいです。
後述しますが、なんかrust-analyzerが対応しているバージョンの問題でCargo.tomlファイルのeditionを2018にする必要があります。
そうしないとrust-analyzerがプロジェクトの読み込みに失敗します。
cargo newコマンドで新しいプロジェクトを作るとき、デフォルトだとeditionは2021に設定されているので、cargo.tomlファイルを開いて修正しましょう。2021を2018に書き換えるだけです。
もしくはcargo newを行う時に--editionで指定できるみたいなので、そちらでも良いと思います。
cargo atcoder
プロジェクトの作成や、書いたコードの提出を一括でやってくれます。超便利。
テストケース通らなかったら提出しないという親切設計なので安心です。
詳細はこちら(https://github.com/tanakh/cargo-atcoder)に全部載ってます。
2022年5月14日現在でちょっとした注意点があります。
cargo-atcoderでは内部でcargo newコマンドを呼び出すため、生成されたプロジェクトではeditionが2021になっています。
こちらはバージョン指定とか出来ないので、生成後に直さないとrust-analyzerがプロジェクトを読み込まず、補完などが効きません。
あと、cargo-atcoderのreadmeに書いてあるconfig.tomlの設定は絶対にやる方が良いです。
これをやらないとビルドに毎回時間を取られる上に、無駄な実行ファイルが大量に生成されて容量を食います。
cargo atcoderと、後述するproconioのinputマクロ(の元になったアイデア)はtanakhさんによって用意されたものです。
Twitterのbioに「今すぐフォローすべき競技プログラミング界のスーパーエンジニア」とあるので是非フォローしましょう。
tanakhさんのおかげでRustを始めたと言っても過言ではありません。𝐵𝐼𝐺 𝐿𝑂𝑉𝐸...
夢月ロア
問題が解けなくなったり、変なバグ踏んでイライラした時とかにおすすめです。
ぱっぱやを聴け。
Electronic Dance Roa?【Launchpad】 - YouTube
proconioについて
proconioはrustの競技プログラミング向けのIOライブラリで、inputマクロが主に使われます。
コードの上の方にuse proconio::input;を書いとけばatcoderでも使えます。
rustはそのまま使うと入力がすごく面倒で、予め入力用の関数を用意しておいたりすることになります。面倒!
そこでinputマクロが役立ちます。
input! { n: usize, a: [i32; N], }
こんな感じで書くと数値や配列やらをいい感じに受け取ってくれます。超便利!
proconioはstatiolakeさんが、tanakhさんのinputマクロをベースに用意してくださったようです。
元々対応してなかったinteractiveな入力形式にも対応していたり、型推論がちゃんと働いたりとすごいです。
statiolakeさんがいなかったらRustを始めていなかった可能性が高いです。𝐵𝐼𝐺 𝐿𝑂𝑉𝐸...
さて、だいぶ長くなりましたが問題を解いていきます。
001 001 - Yokan Party(★4)
提出したコードは
https://atcoder.jp/contests/typical90/submissions/31498336
です。
これはいつものフッフッフッwですね。
ある値で成立したらそれより大きい値でもずっと成立、みたいなのは二分探索が使えます。
ところで、僕は基本的に二分探索の方法はめぐる式二分探索(https://qiita.com/drken/items/97e37dd6143e33a64c8c)を使うことにしています。わかりやすいのでおすすめです。
Rustでは、変数宣言はこんな感じ↓
let (mut ok, mut ng): (i64, i64) = (0, l);
で構造化束縛みたいなのが出来るようです。便利。
前処理のところは面倒なのでVecのinsertを使いました。この辺はC++にもありますね。
二分探索のところ、C++みたいにtemplateでabs関数をいい感じにしてくれないかと思ったんですが、Rustはそういうのはダメっぽいです。
かわりにi32型にabsがメソッドとして用意されているらしく、
(ok-ng).abs()
で行けました。これならC++とほとんど変わらない文字数で書けますね。
FFの方に教えてもらいました、ありがとうございます。
002 002 - Encyclopedia of Parentheses(★3)
括弧列の問題、苦手。括弧列見ただけで反射的に悲鳴を上げました。
提出コードはこれです。
https://atcoder.jp/contests/typical90/submissions/31505604
定義通りに文字列を作っていき、最終的にVec→HashSet→Vecと変換することで各要素が一つずつになるようにしています。
割と力技で解いてしまったんですが、これは解説のようにbit全探索で解けますね。そちらもこの後に出しました。
この問題は無理な解法で粘ったのもあって結構嵌りました。
Rustでは文字列の結合がString型 + &str型の形式にならないといけないようです。面倒ですね。
次の記事がわかりやすかったです。
Rustの文字列結合はどうしてString+&strなのか - Qiita
あとはイテレータ周りがいまいちわかっていません。
into_iter().collect()
みたいなやつとか。
Rustのfor文はイテレータ専用らしく、vをイテレータに変換し、各要素を見ていくようです。
for x in &vみたいに参照にしておけば借用になってムーブされません。
こちらが詳しくてわかりやすいです。
iter()とinto_iter()の違いとちょっとした落とし穴 - Qiita
こいつfor文みたいな顔をしやがって、裏で生意気なことしてやがるな。
内部でinto_iterを呼んでいるが、into_iterは配列には実装されていない。だからRustではfor文で配列を使えないわけですね。
この辺りはAPG4bを読み終えたばかりだったりすると難しそうです。
for x in &v を回している間はv自体に変更を加えられないので、上のコードでは回りくどいやり方をしています。
この辺りはc++の方が簡単な気がしますが、一方でc++で雑に同じようなことをやるとバグの原因になりがちなので、こちらの方が良いのかもしれません。
もしくはもっといい書き方があるかも?
003 003 - Longest Circular Road(★4)
提出コードは↓です。
https://atcoder.jp/contests/typical90/submissions/31509639
木の直径ですね。二回dfsをします。
Rustではグローバル変数を使うのが色々面倒なので、C++やPythonでやってたみたいに関数からグローバル変数にアクセスするような書き方が出来ません。
もちろん安全性のためですが、一々参照を関数で渡す必要があって、競プロではちょっと面倒です。
とはいえRustにはC++より便利な部分があって、それはタプル型がPython並みに使いやすいことです。
おかげで上のコードのように、dfsの戻り値が綺麗に書けます。
for next_v in &graph[now]になっているところは、先述の借用の文ですね。
この場合next_vも参照になるので、後で参照外しをしています。
for文みたいな顔をして裏で何をしているのかわからないので、ちゃんと何をしてるのかドキュメントで調べる必要があります。いや他の言語でも調べろや。
実際はfor文は3種類しかない(T, &T, mut &T, std::iter - Rust)らしいので、一回理解してしまえばそんなに辛くなさそうです。
004 004 - Cross Sum(★2)
提出したコード↓
https://atcoder.jp/contests/typical90/submissions/31510508
みんな大好き累積和ですね。ここは特に嵌りませんでした。
おわりに
一旦ここで切り上げます。
別の記事に分けるか追記するかはその内決めます。