bouzuya.hatenablog.com

ぼうずやのにっき

パナソニックプログラミングコンテスト2020 の A, B, C, D を解いた

パナソニックプログラミングコンテスト2020 の A, B, C, D を解いた。

use proconio::input;

fn f(s: &mut String, n: usize, c: u8) {
    if s.len() == n {
        println!("{}", s);
        return;
    }
    for i in b'a'..=c {
        s.push(i as char);
        f(s, n, c + if i == c { 1 } else { 0 });
        s.pop();
    }
}

fn main() {
    input! {
        n: usize,
    };
    f(&mut String::new(), n, b'a');
}

avr-rust 関連のドキュメントを読んでいる。前に触ったときよりかなり状況が良くなっているので簡単にできそう (まだ試していない) 。


今日のコミット。

2023-W04 ふりかえり

2023-W04 をふりかえる。

2023-W04 の目標 とその記事

目標。

  • ☐ bbn コマンドでの JSON ・ sitemap.xml 出力に対応する

記事。

つくったもの

その他

よんだもの。

(なし)

みたもの。

(なし)

勉強会。

おでかけ。

(なし)

ゲーム。

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

買い物。

(なし)

体調。

  • 疲れている

育児。

  • 上の子はスーパーマリオオデッセイで都市の国までたどり着いている
  • 下の子は何か言っているけど何も分からない (例: リロリロ!リロリロ!)
  • 下の子はおかわりを「アリアリ」と言う

2023-W04 はどうだったか。

先週同様うまく行っていない。いろいろあって疲れている。気持ちにきてる。

雪が降った。積もった。神戸ではめったにないことだ。子どもの送迎などいろいろ困った。

Steam Deck の交換を進めた。

AtCoder は ABC287 に参加した (2023-01-28) 。 1213 → 1230 (+17) (https://atcoder.jp/users/bouzuya/history/share/abc287) 。

sitemap-xml は変わらず保留している。 bbn は JSON の出力に意外と手間取っている。元の動きが悪い……。 twiq-light に reply 機能を追加した。

ラジオ体操・懸垂・フィットボクシング 2 を続けている。

2023-01 が終わる。うーん……。気持ち的には苦しいけど前向きに進めては居る。これじゃダメだなと思うことが多い。

2023-W05 の目標

  • bbn コマンドでの sitemap.xml 出力に対応する
  • L チカする

(TODO: 2023-01 ふりかえり)

twiq-light 0.3.0 をつくった / ABC287 に参加した

twiq-light 0.3.0 をつくった。 twiq-light は queue や検索などを提供するぼくの個人的な twitter クライアントで、ソースコードbouzuya/rust-sandbox の twiq-light/ にある。

0.3.0 での変更点は次のとおり。

  • twiq-light queue enqueue--reply を追加した
  • twiq-light tweet post を追加した

reply をつける機能が欲しかったので付けた。動作確認しづらかったのでツイートするコマンドを付けた。

あわせて cargo update したのだけど、 crates:base64 が 0.21.0 になっており、 API が変更されていて嫌な感じだった。また書くかもしれない。


ユニークビジョンプログラミングコンテスト2023 新春 ( ABC287 : AtCoder Beginner Contest 287) に参加した。

https://atcoder.jp/users/bouzuya/history/share/abc287 1213 → 1230 (+17) 。 C 問題のパスグラフの判定の条件が浮かばず手間取った。


今日のコミット。

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

ABC052 : AtCoder Beginner Contest 052 の A, B, C, D を解いた。

use proconio::input;

fn main() {
    input! {
        n: usize,
        a: usize,
        b: usize,
        x: [usize; n],
    };
    let mut sum = 0_usize;
    for i in 1..n {
        let d = x[i] - x[i - 1];
        sum += (d * a).min(b);
    }
    let ans = sum;
    println!("{}", ans);
}

疲れている。


今日のコミット。

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

ABC032 : AtCoder Beginner Contest 032 の A, B, C, D を解いた。

use std::collections::BTreeMap;

use proconio::input;
use superslice::Ext;

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

macro_rules! chmin {
    ($min_v: expr, $v: expr) => {
        if $v < $min_v {
            $min_v = $v;
            true
        } else {
            false
        }
    };
}

fn f(w: usize, vw: &[(usize, usize)]) -> Vec<(usize, usize)> {
    let n = vw.len();
    let mut map = BTreeMap::new();
    for bits in 0..1 << n {
        let mut sum_v = 0_usize;
        let mut sum_w = 0_usize;
        for i in 0..n {
            if ((bits >> i) & 1) == 1 {
                let (v_i, w_i) = vw[i];
                sum_v += v_i;
                sum_w += w_i;
            }
        }
        if sum_w <= w {
            let entry = map.entry(sum_w).or_insert(sum_v);
            *entry = (*entry).max(sum_v);
        }
    }
    let mut res = vec![];
    let mut maxv = 0;
    for (k, v) in map {
        maxv = v.max(maxv);
        res.push((k, maxv));
    }
    res
}

fn main() {
    input! {
        n: usize,
        w: usize,
        vw: [(usize, usize); n],
    };
    let ans = if n <= 30 {
        let wv1 = f(w, &vw[0..n / 2]);
        let wv2 = f(w, &vw[n / 2..n]);
        let mut ans = 0_usize;
        for (w1, v1) in wv1 {
            let i = wv2
                .lower_bound_by_key(&(w + 1 - w1), |(w2, _)| *w2)
                .saturating_sub(1);
            if i < wv2.len() {
                let (w2, v2) = wv2[i];
                if w1 + w2 <= w {
                    ans = ans.max(v1 + v2);
                }
            }
        }
        ans
    } else if vw.iter().copied().all(|(_, w_i)| w_i <= 1_000) {
        let mut dp = vec![0_usize; w + 1];
        for (v_i, w_i) in vw {
            let mut next = vec![0_usize; w + 1];
            for j in 0..=w {
                chmax!(next[j], dp[j]);
                if j + w_i <= w {
                    chmax!(next[j + w_i], dp[j] + v_i);
                }
            }
            dp = next;
        }
        *dp.iter().max().unwrap()
    } else if vw.iter().copied().all(|(v, _)| v <= 1_000) {
        let inf = 1 << 60;
        let mut dp = vec![inf; 1_000 * n + 1];
        dp[0] = 0_usize;
        for (v_i, w_i) in vw {
            let mut next = vec![inf; 1_000 * n + 1];
            next[0] = 0_usize;
            for j in 0..=1_000 * n {
                chmin!(next[j], dp[j]);
                if j + v_i <= 1_000 * n {
                    chmin!(next[j + v_i], dp[j] + w_i);
                }
            }
            dp = next;
        }
        dp.into_iter()
            .enumerate()
            .filter(|&(_, w_i)| w_i <= w)
            .map(|(v, _)| v)
            .max()
            .unwrap_or(0)
    } else {
        unreachable!()
    };

    println!("{}", ans);
}

今日のコミット。

タミヤのミニ水中モーターで遊ぶ / PAST #11 の F を解いた

タミヤ 楽しい工作シリーズ No.185 ミニ水中モーター 高速タイプ https://www.tamiya.com/japan/products/70185/index.html を買って遊んでいる。 2023-01-15 に買ったと書き、 2023-01-22 に上の子が遊んでいると書いたものだ。

組み立ては数分でできる。大した速度は出ない。単体では浮かばないので前からあった壁に貼り付けるタイプのおもちゃに貼り付けて遊んでいる。取扱説明書にはお風呂だとグリスが溶けたり、変形して浸水するなどと書いてあるが、せいぜい 500 円程度のものなので、あまり気にせず使っている。ニッケル水素電池は絶対に使うなと書いてあったのでそちらは指示通りにマンガン電池を買ってきた。一本で数日は持つ ( 1 日でせいぜい 30 分も動かさないので ) ようだ。

地味なおもちゃ (……というかほとんど部品) なのだが、子どもは思った以上に楽しんでいる。お風呂になるべくおもちゃの類を置かないようにしていたからかもしれない。

2023 に入ってからいろいろあって育児がほぼワンオペ状態で、風呂へスムーズに入れたり、一人を洗っている間のもう一人の動きを抑制したり、一定時間は浴槽内で待機させる必要があり、そのための道具として導入した。期待以上に機能している。前述の通り、お風呂に動きのあるおもちゃがないのもすこし気になっていた。自身の小さいころに近所のパン屋 (?) で船を買ってもらい気に入って遊んでいた記憶があったので、そういうものがあればいいなとも思っていた。


PAST #11 : 第11回 アルゴリズム実技検定 過去問 の F を解いた。

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

fn main() {
    input! {
        h: usize,
        w: usize,
        mut s: [[usize; w]; h],
        n: usize,
        rc: [(Usize1, Usize1); n],
    };
    for (r, c) in rc {
        if s[r][c] == 0 {
            continue;
        }
        for i in (0..r).rev() {
            s[i + 1][c] = s[i][c];
        }
        s[0][c] = 0;
    }

    for i in 0..h {
        for j in 0..w {
            print!("{}{}", s[i][j], if j == w - 1 { '\n' } else { ' ' });
        }
    }
}

Steam Deck の交換手続きがようやく進んだので、箱詰めしたのだけど、雪の影響で集荷されなかった。


今日のコミット。

markdown-link-helper 0.3.1 をつくった / ABC069 A, B, C, D を解いた

markdown-link-helper 0.3.1 をつくった。 bouzuya/rust-sandbox に置いてある。

markdown-link-helper は指定された Markdown ファイルに含まれる参照リンクのうちリンク参照定義の欠けているものについて、ルールファイルに従って追記すべきリンク参照定義を出力するコマンドラインツール。

分かりにくそうなので具体例で書くと Markdown[2023-01-24] があって [2023-01-24]: https://blog.bouzuya.net/2023/01/24/ が欠けている場合で、ルールファイルに [YYYY-MM-DD]https://blog.bouzuya.net/YYYY/MM/DD/ へと変換するルールが書いてあれば、 [2023-01-24]: https://blog.bouzuya.net/2023/01/24/ を出力する。

0.3.0 から 0.3.1 ではクレートのバージョンアップとドキュメントの更新とテストの追加をした。

そもこれをした経緯は bbn コマンドの機能追加に伴って、 markdown-link-helper で Markdown をどう処理していたかを思い出すため。 crates:pulldown-cmark を使って壊れているリンクを拾っていたようだった。ただ結局 bbn では crates:regex で雑に処理することにした。


ABC069 : AtCoder Beginner Contest 069 の A, B, C, D を解いた。

use proconio::input;

fn main() {
    input! {
        h: usize,
        w: usize,
        n: usize,
        mut a: [usize; n],
    };
    let mut index = 0_usize;
    let mut ans = vec![vec![0_usize; w]; h];
    for i in 0..h {
        let range = if i % 2 == 0 {
            (0..w).collect::<Vec<usize>>()
        } else {
            (0..w).rev().collect::<Vec<usize>>()
        };
        for j in range {
            if a[index] == 0 {
                index += 1;
            }
            ans[i][j] = index + 1;
            a[index] -= 1;
        }
    }

    for i in 0..h {
        for j in 0..w {
            print!("{}{}", ans[i][j], if j == w - 1 { '\n' } else { ' ' });
        }
    }
}

今日のコミット。