2024-01-08 TryInto の Infallible がときどき邪魔 / PAST #2 L

TryFrom や TryInto を引数に取る関数を書く。

pub async fn f<I, T>(iter: I) -> Result<Vec<X>, E>
where
    I: IntoIterator<Item = T>,
    T: TryInto<X>,

T: TryInto<T, Error = E> としないとエラーの扱いに困るけど、impl TryFrom<X> for X は Infallible を Error とするので困る。正しいのだけど。

呼び出し側で f(x.try_into()?)? としてもらうのも手だけど、 f(x)? と書けるようにしたい。

trait TryIntoX を追加すれば自動実装を避けられるので T: TryInto<T, Error = E> 相当の挙動を実現できる。ただ、面倒くさい。

うーん……。

追記: 2024-01-09 に続きを書いた。

成人の日。子どもの食欲が落ちていて気がかりだ。ご飯は食べないがヤッターめん (お菓子) は食べたがる。難しい。

PAST #2 第二回アルゴリズム実技検定過去問

L - 辞書順最小 https://atcoder.jp/contests/past202004-open/tasks/past202004_l
- 提出: https://atcoder.jp/contests/past202004-open/submissions/49169476
- 解説 AC 。 TLE, WA, RE を 1 回ずつ
- 個数・距離から一要素目が選択可能な範囲は決まる
- 辞書順最小なので先頭から最小を選んでいけば良い
- 最小を選んだら次の範囲はその範囲 + D を左端、右端は右端 + D で範囲をスライドさせる
- 各範囲の最小を高速に選ぶために BTreeMap を使うと良い

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

use proconio::input;

fn main() {
    input! {
        n: usize,
        k: usize,
        d: usize,
        a: [usize; n],
    };
    if (k - 1) * d >= n {
        println!("-1");
        return;
    }

    let mut map = BTreeMap::new();
    let mut ans = vec![];
    // [l, r)
    let mut l = 0_usize;
    let mut r = n - (k - 1) * d;
    for i in l..r {
        if i >= n {
            break;
        }
        map.entry(a[i]).or_insert_with(VecDeque::new).push_back(i);
    }
    for _ in 0..k {
        let (a_i, mut is) = map.pop_first().unwrap();
        let min_pos = is.pop_front().unwrap();
        if !is.is_empty() {
            map.insert(a_i, is);
        }
        ans.push(a_i);

        for i in r..r + d {
            if i >= n {
                break;
            }
            map.entry(a[i]).or_insert_with(VecDeque::new).push_back(i);
        }
        for i in l..min_pos + d {
            if i >= n {
                break;
            }
            if i == min_pos {
                continue;
            }
            let is = map.get_mut(&a[i]).unwrap();
            is.pop_front();
            if is.is_empty() {
                map.remove(&a[i]);
            }
        }
        l = min_pos + d;
        r += d;
    }
    if ans.len() != k {
        println!("-1");
        return;
    }

    for a in ans {
        println!("{}", a);
    }
}

今日のコミット。