〈蟻本拾い読み〉対称性のある数え上げ(p.268), スタックの利用(p.298)
蟻本拾い読み
〈Rust入門〉ABC 105の問題をRustで解いてみる
昨日のABC 105の問題(A〜D)をRustで解いてみた。
続きを読むAtomパッケージ自作入門記
int N, K; string s;
まで書いたら
int N, K; string s; cin >> N >> K >> s;
とか、
N,K,s
まで書いたら
#ifdef DEBUG cerr << "N=" << N << ", " << "K=" << K << ", " << "s=" << s << endl; #endif
みたいな補完をしてくれるやつを作った。
GitHubに置いておくので
GitHub - naoyat/procon-support: A procon support package for Atom
作りたいツールの叩き台にどうぞ
Rust入門記(チュートリアルからABSまで)
そろそろRustじゃないかなと思ったのでちゃんと入門してみる。
(前にも一度そう思ってhomebrewでRustを入れたんだけど何もしてなかった)
(再)インストール
homebrew版は捨てて、rustupでインストール。
和訳ドキュメントをビルドしたいけれどrustbookが入らない。。。
→ここにあるrustbook入りDockerイメージを利用して解決。
第1段階
チュートリアルの「数あてゲーム」を写経して動かしてみる。
$ cargo new kazuate $ cd kazuate ; vi src/main.rs $ cargo run Compiling kazuate v0.1.0 (file:///Users/naoyat/work/rust/kazuate) Finished dev [unoptimized + debuginfo] target(s) in 10.76s Running `target/debug/kazuate` 数字を当ててみて! 予想値を入力してください ...
cargo便利。
// main.rs extern crate rand; use std::io; use std::cmp::Ordering; use rand::Rng; fn main() { println!("数字を当ててみて!"); let secret_number = rand::thread_rng().gen_range(1, 101); // println!("秘密の数字: {}", secret_number); println!("予想値を入力してください"); loop { let mut guess = String::new(); io::stdin().read_line(&mut guess).expect("行の読み取りに失敗しました"); let guess: u32 = match guess.trim().parse() { Ok(num) => num, Err(_) => continue, }; println!("あなたの予想値: {}", guess); match guess.cmp(&secret_number) { Ordering::Less => println!("小さすぎます!"), Ordering::Greater => println!("大きすぎます!"), Ordering::Equal => { println!("あなたの勝ちです!"); break; } } } }
文字列リテラルに日本語をそのまま書いても大丈夫みたいだ。
第2段階
ABS (AtCoder Beginners Selection)あたりをRustで解きながら色々見ていこう。
その前に、標準入出力についてさらっておく。
標準出力
println!("テキスト");
でテキストが表示され(た後に改行され)る。ln
なしの print!("文字列")
で(想像通り)改行なしで表示される。
プレースホルダ {}
を置いて、変数の内容を表示させることもできる。
fn main() { let name = "Rust"; print!("Hello. "); println!("My name is {}.", name); }
print!()
の文字列を返す版(何も表示しない)が format!()
である。
標準入力
文字列には std::string::String
と &str
の2種類があるらしい。
(前者はmutableで後者は定数?)
標準入力から文字列を1行読み取るには
fn main() { let mut s = std::string::String::new(); std::io::stdin().read_line(&mut s).ok(); println!("Your input is \"{}\"", n); }
ダブルクオートのエスケープは他の多くの言語同様バックスラッシュを用いればよい。
これだと行末の改行も含まれるので、ダブルクオートが次の行に飛ばされて表示される。
fn main() { let mut s = std::string::String::new(); std::io::stdin().read_line(&mut s).ok(); let s = s.trim_right(); println!("Your input is \"{}\"", n); }
これで余分な改行が消える。
数値として入力するには?
fn main() { let mut s = std::string::String::new(); std::io::stdin().read_line(&mut s).ok(); let n = s.trim_right().parse().ok().unwrap(); println!("Your input is {}", n); }
unwrap()
は結果の値を得るための何か。(これがないと std::option::Option
が来る)
でもこれでは parse()
が型推論ができなくて怒られる。
$ rustc foo.rs error[E0282]: type annotations needed --> foo.rs:4:9 | 4 | let n = s.trim_right().parse().ok().unwrap(); | ^ | | | cannot infer type for `_` | consider giving `n` a type
受ける変数n
に型を指定すれば良いらしい。あるいはparse()
の方に型を指定しても行ける。
fn main() { let mut s = std::string::String::new(); std::io::stdin().read_line(&mut s).ok(); let n:i32 = s.trim_right().parse().ok().unwrap(); // let n = s.trim_right().parse::<i32>().ok().unwrap(); println!("Your input is {}", n); }
i32
は言うまでもなく32ビット符号付き整数。
競プロでよくある、沢山の整数がスペース区切りで1行に入っているやつを読み取るには?
fn main() { let mut s = std::string::String::new(); std::io::stdin().read_line(&mut s).ok(); let a:Vec<i32> = s.trim_right().split(' ').map(|s| s.parse().ok().unwrap()).collect(); println!("Your input is {:?}", a); }
Vec
がSTLのvectorにあたる、のかな。splitしてmapしてcollectしたらVecが出来るのか。便利。
{:?}
とすると Vec<i32>
も表示できる。
qiita.com
に、こうした入力を便利関数にまとめたものが載っている。(2次元配列への入力なんてのもある)
split(' ')
の代わりにsplit_whitespace()
なんてのもあるのね。
とりあえずスニペットにしておこう。
(以下、ここにある read_なんとか()
は略)
中央値の中央値 (median of medians)
ABC100の解説で触れられていた「中央値の中央値 (median of medians)」のことを調べたメモ。
〜
厳密なmedian値でなくていいのでそれっぽい値をO(n)で求める方法。少なくとも上下に個ずつ、それより小さい(or 大きい)値が存在することが示せる。
真のmedianの近似として、適当なpivotの選択に使える。
(配列の中でk番目に小さい値を選ぶときに使える。k=n/2とすれば当然真のmedianも求まる。quicksortのpivotにも使えるけど乱数でやったほうが速いとか。最悪計算量は減らせるけど)