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にも使えるけど乱数でやったほうが速いとか。最悪計算量は減らせるけど)
原理は割と簡単
Microsoft Q# Coding Contest - Summer 2018
MSのQ#を使った量子コンピューティングのプログラミングコンテスト(本選)。
Microsoft Q# Coding Contest - Summer 2018
週末の3日間で15問を解く。
→練習ラウンド
12完で151位。
量子コンピューティングの授業の演習問題、みたいな教育的な感じだなと思った。
ところどころトリッキーではあるけれど難しすぎるというほどでもない。(Q#歴0日から始めた割に善戦したが全完したかった)
公式Editorialはこちら。
続きを読むMicrosoft Q# Coding Contest - Summer 2018 - Warmup
MSのQ#を使った量子コンピューティングのプログラミングコンテスト(の練習ラウンド)。
Microsoft Q# Coding Contest - Summer 2018 - Warmup
→本選
Mac*1に環境入れるのとか面倒で、Warmupラウンドをやってたのは知ってたけどスルーしてた。
本戦開始まで2時間切ったあたりで急にやる気になったので、Visual Studio CodeとQ#環境をセットアップして、過去問のWarmupに本戦前にいくつか投げてみた(とりあえず6AC+1WA)。
Warmupというだけに、チュートリアルっぽい問題が並ぶ。
Q#触るのは今回が初めてだけど
- H(アダマール)ゲートは
H()
- CNOTゲートは
CNOT()
- Xゲートは
X()
- 計測は
M()
とか、そのまんまなので書きやすい。
【追記】本戦の途中ですがwarmup全完(7/8 13:14)
*1:只今修理入院中につきレンタル代替機を使用中
高速ゼータ変換/高速メビウス変換
高速ゼータ変換・高速メビウス変換が気になっていたところにタイムリーに先日のARC 100のE問題が来て(ちゃんと解けなかったので)折角なのでこの機会にマスターしようと思い競プロ有識者の皆さんのブログやツイートを漁ってみました。
- はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
- 高速ゼータ変換 - とどの日記
- 高速メビウス変換について - lan496の日記
- https://pekempey.hatenablog.com/entry/2016/10/30/205852
- ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】 - prime's diary
- 競技プログラミングにおける畳み込み問題まとめ(FFT,アダマール変換,メビウス変換,ゼータ変換) - はまやんはまやんはまやん
- 高速ゼータ変換、高速メビウス変換 - omochan's diary
- 競技プログラミングをするフレンズ on Twitter: "ギンギツネ「ちょっと調べてみたけど、高速ゼータ変換は「S⊂TなるTに関する和」を求める操作みたいね。今回みたいに「T⊂SなるTに関する和」を求める操作は高速メビウス変換って言うらしいわ」"
- 昼休みにAPを消化しろ on Twitter: "俺は「Sに対して、S⊂Tである全てのTに渡る和」を求めるのをゼータ変換、その包含関係が逆になった「T⊂Sである全てのTに渡る和」を求めるのがメビウス変換、メビウス変換の逆変換をメビウス逆変換と呼んでるんのだけど、競プロ界隈ではメビウス逆変換のことをメビウス変換と呼んでいるらしい"
・・・・・・
ゼータ変換/メビウス変換が互いに逆変換の関係なのはわかったんだけど…どっちがどっち?