naoya_t@hatenablog

いわゆるチラシノウラであります

〈蟻本拾い読み〉対称性のある数え上げ(p.268), スタックの利用(p.298)

蟻本拾い読み

続きを読む

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);
}

VecSTLvectorにあたる、のかな。splitしてmapしてcollectしたらVecが出来るのか。便利。
{:?} とすると Vec<i32> も表示できる。

qiita.com
に、こうした入力を便利関数にまとめたものが載っている。(2次元配列への入力なんてのもある)
split(' ') の代わりにsplit_whitespace() なんてのもあるのね。
とりあえずスニペットにしておこう。

(以下、ここにある read_なんとか() は略)

続きを読む

中央値の中央値 (median of medians)

ABC100の解説で触れられていた「中央値の中央値 (median of medians)」のことを調べたメモ。

厳密なmedian値でなくていいのでそれっぽい値をO(n)で求める方法。少なくとも上下に\frac{3}{10}n個ずつ、それより小さい(or 大きい)値が存在することが示せる。

真のmedianの近似として、適当なpivotの選択に使える。
(配列の中でk番目に小さい値を選ぶときに使える。k=n/2とすれば当然真のmedianも求まる。quicksortのpivotにも使えるけど乱数でやったほうが速いとか。最悪計算量は減らせるけど)

原理は割と簡単

続きを読む

期待値の線形性(が腑に落ちるまでの長い軌跡)

「期待値の線形性」について、けんちょん先生ふるやん先生の解説を参考にしながら自分の理解を整理するためのメモ。(随時加筆修正)

期待値の線形性そのもの
$$ \mathbb{E}[ax+b] = a\mathbb{E}[x] + \mathbb{E}[b] $$
は分かってるし、「\mathbb{E}[\sum f(x)] の形で書けるものは\sum\mathbb{E}[f(x)] に書き換えて解ける」という事実にも別に疑問はない。というか、

f(x) is 何

という式が(都合よく)立てられる問題なのかを判別できるかどうかとか、式が立てられたとしても前後の文脈を無視して計算しても大丈夫なのか(どうも気持ち悪いし納得しづらい)とかいう話か。

続きを読む

Microsoft Q# Coding Contest - Summer 2018

MSのQ#を使った量子コンピューティングのプログラミングコンテスト(本選)。
Microsoft Q# Coding Contest - Summer 2018
週末の3日間で15問を解く。
練習ラウンド

12完で151位。
量子コンピューティングの授業の演習問題、みたいな教育的な感じだなと思った。
ところどころトリッキーではあるけれど難しすぎるというほどでもない。(Q#歴0日から始めた割に善戦したが全完したかった)

f:id:n4_t:20180710024132p:plain:w500
f:id:n4_t:20180710042715p:plain:w500

公式Editorialはこちら

続きを読む