bouzuya.hatenablog.com

ぼうずやのにっき

ABC028 の A, B, C, D を解いた / quick-xml の Reader を試している

ABC028 : AtCoder Beginner Contest 028 の A, B, C, D を解いた。

sitemap-xml 0.3.0 に向けて bouzuya/rust-examples の quick_xml1 で Reader を試している。 crates:xml-rs のように素朴に持つ方針を取れば Iterator も実装できるし、扱いやすい。ただ、せっかくなので今回は crates:quick-xml のように参照 (Cow<'a, str>) を持つ方針を取ろうと思っている。

のどが痛いのとなぜかお腹を壊している。

風邪の強い日だった。

今日のコミット。

2023-W02 ふりかえり

2023-W02 をふりかえる。

2023-W02 の目標 とその記事

目標。

  • ☑ Yew を使った Web アプリケーションを何か公開する
  • ☐ bouzuya.net に genuuid / date-to-week-date を追記する
  • ☑ 『詳解 Rust プログラミング』を読みはじめる

記事。

つくったもの

よんだもの

(なし)

『詳解 Rust プログラミング』を読んでいる。

みたもの

(なし)

その他

勉強会。

おでかけ。

(なし)

ゲーム。

  • フィットボクシング 2 31 + 1 + 111 + 55 日目 (2 + 2 + 2 + 1 日抜け)

買い物。

  • 水中モーター

体調。

  • のどが痛い

育児。

  • 上の子はストライダーで公園の同じところをぐるぐるしている
  • 下の子はキラキラとブーブーばかり言う

2023-W02 はどうだったか。

イベント参加を増やしている。オンラインイベントなので「聞きながら何かする」みたいな雑な参加もわりとしている。用事で ABC285 に参加できず、フィットボクシングもできなかった。

sitemap-xml 0.1.0 および 0.2.0 をつくった。 sitemap.xml を書く crate 。 reader を足してみて良さそうなら crates.io への登録も考えている。 online-sitemap-builder 0.1.0 をつくった。「 Yew を使った Web アプリケーションを何か公開する」という目標にあわせたやっつけのもの。 sitemap-xml 0.1.0 を使っている。

AtCoder の過去問題を解いている。 ABC285 には参加できなかった。

ラジオ体操・懸垂を続けている。フィットボクシング 2 は 1 日途切れてしまった。またのどが痛い。

Steam Deck の件での Komodo からの連絡はまだない。最悪のサポートだ。 Steam Deck の購入を検討している人はやめたほうが良いかもしれない。

2023-W03 の目標

  • sitemap-xml 0.3.0, 0.4.0 をつくる
  • 『詳解 Rust プログラミング』を第 4 章まで読み進める

online-sitemap-builder 0.1.0 をつくった / ABC015 の A, B, C, D を解いた

online-sitemap-builder 0.1.0 をつくった。 https://bouzuya.net/lab/online-sitemap-builder 。ソースコードは bouzuya/rust-sandbox の online-sitemap-builder に置いてある。

週の目標の達成と crates:yew の最低限の動作確認と bouzuya/rust-sandbox の sitemaps 改め sitemap-xml を試すためのもの。正直なところ、やっつけなので出すのが恥ずかしい。

sitemap-xml は 0.4.0 くらいまで上げるつもりで良さそうなら crates.io に公開することも考えている。それに合わせて online-sitemap-builder も lastmod などの指定などある程度のバージョンアップはすると思う。

そも sitemap.xml はおそらく手書きするものではなく自動生成されるものだと思うので、このアプリケーションには実用性がほとんどない。あえて sitemap 関連で何かやるならクローラーをつくって探索・生成させるようなものとか何か特殊なことをしないとまずそう。入力してボタンで追加みたいな UI をつけるよりも、優れた既存の editor コンポーネントを使って XML を編集可能にするほうが良いまでありそう。

ABC015 : AtCoder Beginner Contest 015 の A, B, C, D を解いた。

use proconio::input;

macro_rules! chmax {
    ($max_v: expr, $v: expr) => {
        if $v > $max_v {
            $max_v = $v;
            true
        } else {
            false
        }
    };
}

fn main() {
    input! {
        w: usize,
        n: usize,
        k: usize,
        ab: [(usize, usize); n],
    };
    let mut dp = vec![vec![0_usize; k + 1]; w + 1];
    for (a, b) in ab.iter().copied() {
        let mut next = vec![vec![0_usize; k + 1]; w + 1];
        for j in 0..=k {
            for l in 0..=w {
                chmax!(next[l][j], dp[l][j]);
                if j + 1 <= k && l + a <= w {
                    chmax!(next[l + a][j + 1], dp[l][j] + b);
                }
            }
        }
        dp = next;
    }
    let ans = dp
        .iter()
        .map(|dp_i| dp_i.iter().max().unwrap())
        .max()
        .unwrap();
    println!("{}", ans);
}

今日のコミット。

ABC037 の A, B, C, D を解いた

ABC037 : AtCoder Beginner Contest 037 の A, B, C, D を解いた。

use std::collections::BinaryHeap;

use proconio::{input, marker::Usize1};

fn main() {
    input! {
        h: usize,
        w: usize,
        a: [[usize; w]; h],
    };

    let mut pq = BinaryHeap::new();
    for i in 0..h {
        for j in 0..w {
            pq.push((a[i][j], i, j));
        }
    }

    let mut dp = vec![vec![1_usize; w]; h];
    while let Some((_, i, j)) = pq.pop() {
        let dir = vec![(-1, 0), (0, -1), (0, 1), (1, 0)];
        for (dr, dc) in dir {
            let (nr, nc) = (i as i64 + dr, j as i64 + dc);
            if !(0..h as i64).contains(&nr) || !(0..w as i64).contains(&nc) {
                continue;
            }
            let (nr, nc) = (nr as usize, nc as usize);
            if a[nr][nc] >= a[i][j] {
                continue;
            }
            dp[nr][nc] += dp[i][j];
            dp[nr][nc] %= 1_000_000_007;
        }
    }

    let mut ans = 0_usize;
    for i in 0..h {
        for j in 0..w {
            ans += dp[i][j];
            ans %= 1_000_000_007;
        }
    }
    println!("{}", ans);
}

今日のコミット。

ABC057 の A, B, C, D を解いた / Iterator::position の複数回呼び出し

ABC057 : AtCoder Beginner Contest 057 の A, B, C, D を解いた。

use proconio::input;

fn choose(n: usize, r: usize) -> usize {
    if n < r {
        return 0;
    }
    if r == 0 {
        return 1;
    }
    let mut m = 1;
    for i in 0..r {
        m *= n - i;
        m /= i + 1;
    }
    m
}

fn main() {
    input! {
        n: usize,
        a: usize,
        b: usize,
        mut v: [usize; n],
    };

    v.sort();
    v.reverse();

    let avg = v.iter().take(a).sum::<usize>() as f64 / a as f64;

    let mut count_eqmin = 0_usize;
    let mut count_fixed = 0_usize;
    for (i, v_i) in v.iter().copied().enumerate() {
        if v_i == v[a - 1] {
            count_eqmin += 1;
            if i < a {
                count_fixed += 1;
            }
        }
    }

    let count = if v[0] == v[a - 1] {
        (a..=b).map(|x| choose(count_eqmin, x)).sum::<usize>()
    } else {
        choose(count_eqmin, count_fixed)
    };

    println!("{}", avg);
    println!("{}", count);
}

Iterator::position は &mut self で iter を進める。複数回呼び出すと前回の最後に見つかった位置の次の位置から探索できることを知った。

fn main() {
    let v = vec![1, 1, 1];
    let mut iter = v.iter();
    assert_eq!(iter.position(|x| x == &1), Some(0)); // next が v[0] を指す iter から探して 0 の位置
    assert_eq!(iter.position(|x| x == &1), Some(0)); // next が v[1] を指す iter から探して 0 の位置
    assert_eq!(iter.position(|x| x == &1), Some(0)); // next が v[2] を指す iter から探して 0 の位置
    assert_eq!(iter.position(|x| x == &1), None);
}

今日のコミット。

ABC084 の A, B, C, D を解いた

ABC084 : AtCoder Beginner Contest 084 の A, B, C, D を解いた。

use proconio::input;

fn sieve_of_eratosthenes(n: usize) -> Vec<bool> {
    let mut p = vec![];
    let mut b = vec![true; n + 1];
    for i in 2.. {
        if i * i > n {
            for j in i..=n {
                if b[j] {
                    p.push(j);
                }
            }
            break;
        }
        if b[i] {
            p.push(i);
            for j in (i + i..=n).step_by(i) {
                b[j] = false;
            }
        }
    }
    b
}

fn main() {
    input! {
        q: usize,
        lr: [(usize, usize); q],
    };
    let max = 100_000;
    let sieve = sieve_of_eratosthenes(max);
    let mut count = vec![0_usize; max + 1];
    for i in 3..=max {
        count[i] = if i % 2 != 0 && sieve[i] && sieve[(i + 1) / 2] {
            1
        } else {
            0
        };
    }
    for i in 1..max {
        count[i + 1] += count[i];
    }
    for (l, r) in lr {
        println!("{}", count[r] - count[l - 1]);
    }
}

昼に https://findy.connpass.com/event/268897/ に参加した。聞いた。

夜に https://forkwell.connpass.com/event/270393/ に参加した。聞いた。

イベント参加もうちょっと増やしてみようかと。

Kindle Oasis が壊れた。画面を誰かに踏まれた (?) くさい。

今日のコミット。

Rust での Docker イメージのサイズの削減 / ABC049 A, B, C, D を解いた

2022-07-25 に rust-musl-builder (https://github.com/emk/rust-musl-builder) の使用について書いた。 Rust を使った Docker イメージのサイズの削減のために rust-musl-builder を使った。

しかし ekidd/rust-musl-builder の Docker イメージはもう更新されていない (2022-11-25) ので避けたほうが良い。そもコンパイルが通らないこともある。 https://github.com/emk/rust-musl-builder/issues/147

代替手段は必要なライブラリを入れた上で cargo build などのオプションに --target=x86_64-unknown-linux-musl を指定すれば良い。これは rust-musl-builder でやっていたことを自分でやっているだけではある。

bouzuya/rust-sandbox で言うと date-to-week-date, genuuid, twiq, twiq-light あたりでこの方法を使っている。 genuuid の場合は↓のような感じ。 musl-dev を入れておかないとたぶんビルドできない。

FROM rust:1.66-alpine as builder

WORKDIR /usr/src/genuuid
RUN apk update && apk add --no-cache musl-dev
COPY ./Cargo.lock ./Cargo.lock
COPY ./Cargo.toml ./Cargo.toml
RUN mkdir src/
RUN touch src/lib.rs
RUN cargo build --release --target=x86_64-unknown-linux-musl
COPY . .
RUN cargo install --path . --target=x86_64-unknown-linux-musl

FROM scratch
ENV PORT=8080
COPY --from=builder /usr/local/cargo/bin/genuuid /usr/local/bin/genuuid
ENTRYPOINT ["genuuid"]

genuuid は 7.02MB 。以前は 86MB だったのでぼちぼちのサイズになっている。

$ docker pull ghcr.io/bouzuya/rust-sandbox/genuuid:0.4.2
# ...

$ docker image list genuuid
REPOSITORY   TAG       IMAGE ID       CREATED          SIZE
genuuid      0.4.2     761d70ce66ac   56 minutes ago   7.02MB

ABC049 : AtCoder Beginner Contest 049 の A, B, C, D を解いた。

use std::collections::{HashMap, VecDeque};

use proconio::{input, marker::Usize1};

fn adjacency_list(n: usize, uv: &[(usize, usize)]) -> Vec<Vec<usize>> {
    let mut e = vec![vec![]; n];
    for (u, v) in uv.iter().copied() {
        e[u].push(v);
        e[v].push(u);
    }
    e
}

fn bfs(n: usize, edges: &[Vec<usize>]) -> Vec<usize> {
    let mut color = 0_usize;
    let mut colors = vec![n; n];
    for start in 0..n {
        if colors[start] == n {
            let mut deque = VecDeque::new();
            deque.push_back(start);
            colors[start] = color;
            while let Some(u) = deque.pop_front() {
                for v in edges[u].iter().copied() {
                    if colors[v] == n {
                        colors[v] = color;
                        deque.push_back(v);
                    }
                }
            }
            color += 1;
        }
    }
    colors
}

fn main() {
    input! {
        n: usize,
        k: usize,
        l: usize,
        pq: [(Usize1, Usize1); k],
        rs: [(Usize1, Usize1); l],
    };

    let e1 = adjacency_list(n, &pq);
    let e2 = adjacency_list(n, &rs);

    let c1 = bfs(n, &e1);
    let c2 = bfs(n, &e2);

    let mut count = HashMap::new();
    for zipped in c1.iter().copied().zip(c2.iter().copied()) {
        *count.entry(zipped).or_insert(0) += 1;
    }

    for zipped in c1.iter().copied().zip(c2.iter().copied()) {
        println!("{}", count.get(&zipped).unwrap());
    }
}

今日のコミット。