naoya_t@hatenablog

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

AtCoderで青になるまでにやったこと／黄色になるためにやるべきこと

AtCoder neta

備忘録。
f:id:n4_t:20181019221646p:plain:w500

AtCoderで○○色になるまでにやったこと

灰

  • ARCに1回参加

茶

  • AGCに1回参加

緑

  • AGCに1回参加

水

  • ABCに1回参加、だけでは足りなくて
  • AGCに1回参加

青

  • ARCに1回参加

AtCoderで○○色になるためにやるべきこと

黄

【追記】
ガヴリール・ドロップアウト観ました。
ガヴ・タプが同級生になる二期はまだですか？

橙

  • 生まれ変わる

赤

  • 2回生まれ変わる

Future Meets You Contest - ふみこんオンサイト

Programming Contest AtCoder Marathon Match

9/29(土) 13:30〜16:30 フューチャー株式会社 ＠アートヴィレッジ大崎セントラルタワー にて

マラソン形式、と言っていいのか分からないですが3時間のコンテストでした。
作問はchokudaiさんで、今回は謎の植物が生える系ではありませんでした。

オンサイト参加登録の際に、オファー金額提示を求めるか否か、という選択肢があり、ガチ勢と冷やかし勢の間に明確に線を引いてきます。
tsukammoさんや_tanzaku_くんに会うためだけにオンサイトを選択した完全な冷やかし勢なので、オファー金額提示不要の方で登録しました。

続きを読む

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

Algorithms 蟻本

蟻本拾い読み

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
posted with amazlet at 18.08.20
秋葉拓哉 岩田陽一 北川宜稔
マイナビ
売り上げランキング: 20,173
Amazon.co.jpで詳細を見る

続きを読む

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 AtCoder 過去問

そろそろRustじゃないかなと思ったのでちゃんと入門してみる。
（前にも一度そう思ってhomebrewでRustを入れたんだけど何もしてなかった）

(再)インストール

homebrew版は捨てて、rustupでインストール。

和訳ドキュメントをビルドしたいけれどrustbookが入らない。。。
→ここにあるrustbook入りDockerイメージを利用して解決。

第１段階

チュートリアルの「数あてゲーム」を写経して動かしてみる。

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

文字列リテラルに日本語をそのまま書いても大丈夫みたいだ。

第２段階

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)

Algorithms

ABC100の解説で触れられていた「中央値の中央値 (median of medians)」のことを調べたメモ。
〜
厳密なmedian値でなくていいのでそれっぽい値をO(n)で求める方法。少なくとも上下に\frac{3}{10}n個ずつ、それより小さい（or 大きい）値が存在することが示せる。

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

原理は割と簡単

続きを読む