blog.bouzuya.net

2023-07-21 bouzuya/genpi に --halfwidth を追加 / ABC217 E を解いた

bouzuya/genpi に機能を追加。

  • --halfwidth を追加
  • rustls へ切り替え (Docker化を見据えて)
$ genpi --halfwidth --katakana | jq .
{
  "date_of_birth": "1909-10-13",
  "first_name": "大喜",
  "first_name_kana": "ﾋﾛｷ",
  "last_name": "佐藤",
  "last_name_kana": "ｻﾄｳ",
  "sex": "male"
}
  • Sorting Queries (AtCoder Beginner Contest 217:E問題) https://atcoder.jp/contests/abc217/tasks/abc217_e
    • https://atcoder.jp/contests/abc217/submissions/43787504
    • 償却計算量・ならし計算量の章
    • 章と問題の関係性をあまり理解できていない
    • 3 が出るたびにソートすると間に合わない
    • 取り出すのは最小の要素ではなく最初の要素なのでソート後に末尾に要素を追加したところでほとんど場合は無視できる
    • もしこれが最小の要素だと最後尾に追加されたものも含めて調べないといけなくなってしまう
    • ソート済みの分とそうでないもの (挿入順で管理する分) を分けてクエリ 3 がきたらソート済み側に移し替えれば良い
use std::{
    cmp::Reverse,
    collections::{BinaryHeap, VecDeque},
};

use proconio::input;

fn main() {
    input! {
        q: usize,
    };
    let mut pq = BinaryHeap::new();
    let mut deque = VecDeque::new();
    for _ in 0..q {
        input! {
            t: usize,
        }
        match t {
            1 => {
                input! {
                    x: usize,
                }
                deque.push_back(x);
            }
            2 => {
                let x = if let Some(Reverse(x)) = pq.pop() {
                    x
                } else {
                    deque.pop_front().unwrap()
                };
                println!("{}", x);
            }
            3 => {
                while let Some(x) = deque.pop_front() {
                    pq.push(Reverse(x));
                }
            }
            _ => unreachable!(),
        }
    }
}

今日のコミット。