PythonistaがRustはじめました#004 -- if式とwhileループ
宣言厨のwotsushiです。 今日は泣く泣くwhileで手続き的なコードを書いたお話です。
ABC116-B
入出力が以下の問題です。
- 入力: 正の整数s
- 出力: sを初項とするコラッツ数列について、過去に出現した値が初めて再び出現する項の番号
https://atcoder.jp/contests/abc116/tasks/abc116_b
HashSet
過去に出現した値を集合型のデータで管理してみます。 他の言語同様、Rustにも集合型のデータ構造はあります。 今回は、HashSet を使います。
使い方ですが、以下のような感じです。
use std::collections::HashSet; fn main() { // 空集合を生成 let mut s = HashSet::new(); // 1を追加する s.insert(1); // 1が含まれるかを表す真偽値を得る let x = s.contains(&1);
Pythonではset型はインポートせずに使えますが、Rustでは最初にインポートする必要があることに注意です。
HashSetと言うくらいなので、追加・存在判定はO(1)でできると思います（どこに書いているのだろう）。
また、存在判定するcontainsは引数に & をつける必要があります。
これ（参照型？）についてはいずれ記事を書こうと思います。
mutableな変数
今まで解いた問題はletで変数を定義していました。
しかしletで定義した変数はimmutableになってしまいます。
私は宣言厨なので、基本的にはletで事足りるのですが、今回の問題のように手続き的に解きたい場合は困ります。
このような場合、 let mut で変数を定義するとmutableな変数を定義できます。
let mut a = 1; // やっぱ2にする a = 2;
mutableだよ！というのを強調することを強制するよい仕様ですね。
if式
Pythonとは異なり、Rustではifは式です。 たしかRubyもifは式だったと思います。 したがって、以下のような書き方ができます。
let a = if x % 2 == 0 { a / 2 } else { 3 * a + 1 };
セミコロンはaの右辺の最後に記述することに注意です。
セミコロンは文の末尾を表すシンボルであり、 a / 2 や 3 * a + 1 は式なのでセミコロンは書いてはいけないのです。
ところで、Rustの式指向の考えは好感が持てますね。 Pythonもif式がほしいなあ（いつも三項演算子のifで無理やりそれっぽく書いています）。
whileループ
サブタイトルになっているwhileループですが、とくに説明することはないです。 他言語とほとんど同じだからです。
// aが3未満の間、aに1を加え続けるコード while a < 3 { a += 1; }
以上より、問題を解くコードは以下となります。
fn main() { // 入力 let s = get!(i64); let mut a = s; let mut m = 1; let mut dp = HashSet::new(); while !dp.contains(&a) { dp.insert(a); a = if a % 2 == 0 { a / 2 } else { 3 * a + 1 }; m += 1; } let ans = m; // 出力 println!("{}", ans); }
うーん、whileを使ったコードはあまり満足できないですね... 次回は、ここまで説明をサボってきた変数の所有権について向き合いたいと思います。 ではでは。
PythonistaがRustはじめました#003 -- 標準出力・max関数
昨日はM-SOLUTIONSプロコンおつかれさまでした。 PythonでModIntするたびに制限時間大丈夫か不安を感じながらSubmitしちゃうので、こういうのは確実にRustで通せるerになりたいですね。 そして本日はAGC! 2完しないといけないプレッシャーに負けず、3完目指して頑張るぞい。
前回の記事で、main関数と標準出力について、説明するのを完全に忘れていたので、補足します。 その後、ABC098-A を解くために、vec型のmax関数を使った話を書きます。
main関数
競技プログラミングのおいて、C++同様にmain関数の呼び出しからプログラムはスタートします。 したがって、任意の問題について必ず書くコードになります。 main関数の書き方は以下のとおりです。
fn main() { // 処理を書く }
returnは書く必要がないようです。
標準出力
標準出力をしない問題はおそらくないでしょう。 Rustでは println! マクロを使います。 フォーマット文字列の標準出力も可能です。 単一の値ansを標準出力する例は以下です。
println!("{}", ans)
複数の値を出力する場合や浮動小数点数を桁数いい感じにして出力するケースについてはいずれ説明します（まだ分かっていない）。
ABC098-A
入出力の概要は以下の通りです。
- 入力: 整数A, B
- 出力: max(A + B, A - B, AB)
元の問題: https://atcoder.jp/contests/abc098/tasks/abc098_a
max関数
さて、四則演算をマスターしている私にとっては、maxするだけの問題です。
そこで、 Rust max でググってみます。
それっぽいのがヒットしました。
https://doc.rust-lang.org/std/cmp/fn.max.html
よしよし、importっぽいのをしてはい終わり...と思いきや、よく見たら引数が二つに限定されているではありませんか。
さすがにn引数のmaxはどっかにあるやろ〜ｗと思いググるを続行しますが見つからず。
諦めて、 max(A + B, max(A - B, A * B)) のように書く手もありますが、今後の人生を考えると任意の個数の値に対するmaxをとれるようにならないと辛いのは間違いないです。
...ん、任意の個数といえばリストにmaxメソッドはないのだろうか？
少し調べてみると、PythonでいうリストはRustでいうVecのようです。
そして、Vecから変換可能なIterator型には、案の定maxをはじめした美味しそうな関数がたくさんありました！
https://doc.rust-lang.org/std/iter/trait.Iterator.html
したがって、以下の流れで解を得られそうです。
- getマクロ（前回導入したマクロ）を使ってA, Bを入力する
- (A + B, A - B, A * B) を要素とするVecを作成する
- 作成したVecをIteratorに変換する
- 変換したIteratorオブジェクトのmaxメソッドを呼び出す
しかし、注意点が二つありました。
注意点1: IterのmaxメソッドはOption型である
PythonのtypesやJavaを使ったことがある人なら推測できるかと思いますが、Optionというのは空値かもしれないことを表すデータ型です。 冷静に考えれば、戻り値の型としては理にかなっていますね。 Vecが空の場合にmaxが定義できないことをケアしているのです。 とはいえ今回の問題ではVecが空でないことは約束されているので、乱暴に値を取り出してしまいましょう。 値を取り出すにはunwrapというメソッドを使えばよさそうです。
https://doc.rust-lang.org/std/option/enum.Option.html#method.unwrap
注意点2: Iter型ではなくIntoIter型に変換する必要がある
注意点1を踏まえて、以下のコードを書きました。
fn main() { // 入力 let (A, B) = get!(i64, i64); let ans = vec![A + B, A - B, A * B].iter().max().unwrap(); // 出力 println!("{}", ans); }
すると、以下のコンパイルエラーが吐かれてしまいました...
$ rustc a.rs -o a.out error[E0597]: borrowed value does not live long enough --> a.rs:47:15 | 47 | let ans = vec![A + B, A - B, A * B].iter().max().unwrap(); | ^^^^^^^^^^^^^^^^^^^^^^^^^ - temporary value dropped here while still borrowed | | | temporary value does not live long enough ... 51 | } | - temporary value needs to live until here | = note: consider using a `let` binding to increase its lifetime = note: this error originates in a macro outside of the current crate (in Nightly builds, run with -Z external-macro-backtrace for more info) error: aborting due to previous error For more information about this error, try `rustc --explain E0597`.
どうもRustで難しいと言われている所有権とかその辺の問題っぽいです。 所有権の理解は今後の課題として、お手軽にmaxを取る方法を調べると、どうやらIteratorではなくIntoIteratorにすればよいようです（Iteratorはオリジナルに対して走査するのに対して、IntoIteratorはクローンを得るイメージなのかな？）。
したがって、コードを以下の通り変更します。
fn main() { // 入力 let (A, B) = get!(i64, i64); let ans = vec![A + B, A - B, A * B].into_iter().max().unwrap(); // 出力 println!("{}", ans); }
無事、通りました！ https://atcoder.jp/contests/abc098/submissions/5694071
次回はループを使った問題に挑戦したお話を書く予定です。 さて、AGC頑張るぞい！
PythonistaがRustはじめました#002 -- 標準入力と四則演算
3日ぶりのRust記事です。 一昨日は、がブリチキンで美味しい唐揚げを堪能し、漬け込みハイボール6種を制覇していました。 その結果、一昨日と昨日は犠牲になったのだ...
今日はRustインストール後、ABC128-Aを通すまでのお話です。
ABC128-A の問題
端的に言うと、入出力が以下である問題です。
- 入力: 非負整数 A, P
- 出力: floor((3A + P) / 2)
元の問題: https://atcoder.jp/contests/abc128/tasks/abc128_a
標準入力
さて、最初の関門はどの言語でもお馴染みの標準入力です。 ざっと調べてみましたが、きちんと理解するにはミュータブルな変数の扱い、型の解釈、Optionalな値の扱いなどの知識が必要そうです。 全部を理解してから始めると挫折しそうなので、今回は先人のマクロをコピペするだけに留めます。 マクロの理解は今後少しずつ進めようと思います。
さて、コピペしたマクロは以下です。 なお、Qiita - Rustで競技プログラミング スターターキット を参考にさせていただきました。 このような優秀なコードを共有いただき、本当にありがとうございます。
macro_rules! get { ($t:ty) => { { let mut line: String = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.trim().parse::<$t>().unwrap() } }; ($($t:ty),*) => { { let mut line: String = String::new(); std::io::stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( $(iter.next().unwrap().parse::<$t>().unwrap(),)* ) } }; ($t:ty; $n:expr) => { (0..$n).map(|_| get!($t) ).collect::<Vec<_>>() }; ($($t:ty),*; $n:expr) => { (0..$n).map(|_| get!($($t),*) ).collect::<Vec<_>>() }; ($t:ty ;;) => { { let mut line: String = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.split_whitespace() .map(|t| t.parse::<$t>().unwrap()) .collect::<Vec<_>>() } }; ($t:ty ;; $n:expr) => { (0..$n).map(|_| get!($t ;;)).collect::<Vec<_>>() }; }
ABC128-A のように二つの整数を受け取るときは以下の通りサクッと書けます。
let (A, P) = get!(usize, usize);
気持ちいですね。 なお、型にusizeを指定していますが、基本的にはi64で宣言するのが安定かもしれません。 これについては、またいずれ述べます。
Rustの四則演算
さて、無事に入力は受け取ることができるようになりました。 ABC128-A を解くために必要な知識は四則演算だけですね。
四則演算に限らず、演算子と記号は The Rust Programming Launguage 付録B に まとめられています。 興味深い演算子もありますが、とりあえず四則演算に着目すると、C++やJavaと変わらないようです。 なお、整数同士の除算はPythonとは異なり、デフォルトでfloorされるようです（参考: Trait Div）。
ABC128-A を解く
ABC128-A を解くための準備はすべて整いました！ 早速コーディングしましょう（getマクロの定義は割愛します。）。
fn main() { // 入力 let (A, P) = get!(usize, usize); let ans = (3 * A + P) / 2; // 出力 println!("{}", ans); }
はい、シンプルですね！ ちなみに、Rustのソースコードの拡張子はrsがメジャーっぽいです(https://doc.rust-jp.rs/book/second-edition/ch01-02-hello-world.html)。 AtCoderに提出するときは関係ないですけどね。
ローカルで実行するときは、忘れずにコンパイルします。コンパイルは rustc コマンドでできます。
↓の感じ。
$ rustc a.rs -o a.out warning: variable `A` should have a snake case name --> a.rs:45:10 | 45 | let (A, P) = get!(usize, usize); | ^ help: convert the identifier to snake case: `a` | = note: #[warn(non_snake_case)] on by default warning: variable `P` should have a snake case name --> a.rs:45:13 | 45 | let (A, P) = get!(usize, usize); | ^ help: convert the identifier to snake case: `p`
「大文字にしろ」という警告が出ていますが、無視します。 競技プログラミングでは問題文の通りに変数名を書きたくなるんですよねぇ。 コンパイル後は生成されたバイナリを実行するだけです。
$ ./a.out 1 3 3
$ ./a.out 0 1 0
$ ./a.out 32 21 58
サンプルは全てOKですね。 言語をPythonのままにしないように注意して提出。無事AC!! 提出結果は以下の通りです。
https://atcoder.jp/contests/abc128/submissions/5666954
上記の提出結果からも分かる通り、Qiita - Rustで競技プログラミング スターターキット によれば、実行時間に必ず2ms かかるみたいです。 まあだいたい制限時間は2000msなので、どうでもいいかな。
次回は、ABC098-Aを解く記事を書く予定です。 vecとmaxの使い方を習得していきます！
PythonistaがRustはじめました#001 -- インストール
突然ですが、Rustというプログラミング言語を触り始めました。 当面は競技プログラミングのサブウェポンとして使う予定です。 手に馴染んだら、サーバサイドのアプリケーションをRustで作ってみたいね。
触り始めた理由
競技プログラミングで実行時間制限がシビアな問題に対する回答として触り始めました。 メインウェポンはPythonなのですが、Python/PyPyでは時間計算量のオーダが想定解法通りでもTLEしてしまうケースがあります。 定数倍高速化を頑張って無理やり通すのも一興ですが、楽したい人なので実行時間が高速な言語で殴ります。
Why Rust?
文法に惹かれたからです。それだけです。 パターンマッチングいいよね。 Rustのウリの一つである安全性は（今のところ）眼中にないです。
競技プログラミングにおいて最も人気のあるC++は、文法がダルいと感じたのでやめておきました。 ダルい文法をフォローするためにマクロをゴリゴリ準備するのも楽しいとは思うのですけどね。
Rustのインストール
MacなのでHomebrewで一発でインストールしました。
$ brew install rust Updating Homebrew... Ignoring path homebrew-cask/ To restore the stashed changes to /usr/local/Homebrew/Library/Taps/homebrew/homebrew-cask run: 'cd /usr/local/Homebrew/Library/Taps/homebrew/homebrew-cask && git stash pop' ==> Auto-updated Homebrew! Updated 3 taps (homebrew/cask-versions, homebrew/core and homebrew/cask). ==> New Formulae ...
結構時間かかります（10〜20分くらい？）。
インストール終わったら、 rustc --version で無事インストールできたことを確認！
$ rustc --version rustc 1.35.0
OKですね。 次回は、最初の難問である標準入力と格闘したお話です。 ではでは。
AGC032 参加メモ
https://atcoder.jp/contests/agc032
A, Bの2完でパフォーマンスは1797でした。 青パフォ出たのは嬉しかったですが、もう少し早くA, Bを解きたかったという気持ちもあります。
A
逆順に考えて解きました。 つまり、最終状態からj番目の要素を削除する操作を繰り返して、全消しできるかを検証しました。 削除する過程で削除候補が複数ある場合、最も後ろの要素を削除しました（ここ、直観的ですが）。
逆順に考える、という発想が難産で解くのに23分かかりました。 ABC120-Dのように逆から操作を考えると簡単な問題は多いように思えるので、逆を試す習慣はつけておきたいところです。
B
結論は、Nが偶数のとき(1, N), (2, N - 1), (3, N-2), ... を除く辺をすべて使ったグラフ、Nが奇数のとき(1, N-1), (2, N-2), (3, N-3), ... を除く辺をすべて使ったグラフが解です。
ポイントは、
- Nが偶数のとき、1+2+...+Nは(N+1)の倍数なので、頂点の和がN+1になるようにグループを分けられる
- Nが奇数のとき、1+2+...+NはNの倍数なので、頂点の和がNになるようにグループを分けられる
グループ分けしてしまえば、他グループのすべての頂点との間に辺を張るだけです。
最初、2部グラフにするだけじゃんと思ったのですが、和が奇数の場合にどうするんだ？となって、そもそもN=5の解を見つけるのに苦労しました。 とはいえ、K部グラフにするという方針は合っていたので、もう少し落ち着いて問題に向き合っていればなあと感じました。
C
オイラー閉路の存在条件から、すべての頂点の次数が偶数であることが必要なのは分かりました。 さらに3つのサーキットを作るには、次数が6の頂点が存在する、または、次数が4の頂点が2つ以上存在するのどちらかを満たせばよいと考えたのですが、後者が不十分でした。
公式の解説の通りで、次数4の頂点が2つの場合が罠ですね。 ていねいに場合分けして考察すれば十分解ける余地のある問題だと思います（つまり、精進不足！）。
起きたら自分でもコードを書いて通したいですね。とくに、次数4の頂点が2つ存在するときに、それらの頂点間のパスが2つのみ存在するかの判定処理くらいはサクッと書けるようにしておきたいです。
AGC031 参加メモ
https://atcoder.jp/contests/agc031
ABC卒業して間もなく参加するか迷いましたが、相性のよい問題が多かったからか黄パフォ出せました！
A
問題文が難しかったです。 （（各アルファベットの個数+1）の総積） - 1 が解ですね。
B
石を2回以上塗り替えても意味ないことを利用して、数列Cから以下のグラフを作成しました。
- 頂点: 1, 2, ..., N
- 辺:
- 1->2->3->...->N
- i->j where i < j, C_i = C_j, C_k = C_i なる i < k < j は存在しない
あとは、頂点1からNまでの経路数をカウントするだけです。 カウントする際はDPすればよいです。
C
実装にすごく手こずりました。
まず、N=3の場合の立方体の頂点を訪問するイメージを浮かべました。 各頂点について、隣り合う頂点が異なる色になるように二色で彩色すると、AとBの異なるビットが奇数個の場合のみYESであることが分かります。
YESの場合、ルートを列挙する必要があるのですが、再帰により気合で通しました。 Bと異なるN-1次元を巡回->Bと同一の次元に移動->Bと異なるN-2次元を巡回->Bと同一の次元に移動->... というイメージです。
D, E, F
手付かず
ABC121 参加メモ
https://atcoder.jp/contests/abc121
1121->1214. 水色になりました！
A
100点問題で最も難しく感じました。
列と行はどこでもよいと言っているので、全て端に寄せると考えれば (H - h) * (W - w) が解と直感的に分かります。
B
実装ゲーです。 内包表記が気持ちよかったです。
C
安いものから順に買うだけです。
D
Aが1以上だと考えるのがしんどそうなので、A>=1のとき、 が成り立つことを利用しました。
（=zとおきます）は以下で求めました。
- zを二進数展開したときの下1桁目: xを4で割った余りが1または2ならば、1です
- zを二進数展開したときの下i桁目（i>=2）: xの下i桁目が1、かつ、xの下1桁目が0ならば、1です
400点問題にしては簡単なほうだと思いました。 しかし、なぜか心が焦ってしまい、上記の法則を見つけるのに時間がかかってしまいました...
