Ccmmutty logo
Commutty IT
2 min read

RustとAtCoderを勉強する(typical90_af)

https://cdn.magicode.io/media/notebox/08656685-cef8-4e75-b3c3-502fcef56ca7.jpeg

はじめに

AtCoder の問題を Rust で解いていきます。AtCoder も Rust も初心者ですが、温かい目で成長を見守っていただけるとありがたいです。
今回は、競プロ典型90問032 - AtCoder Ekiden(★3)を解きました。

提出コード

rust
use itertools::Itertools;
use proconio::input;
use std::collections::HashSet;

fn main() {
    input! {
        n: usize,
        a: [[usize; n]; n],
        m: usize,
        xy: [(usize, usize); m],
    }

    let xy: HashSet<(usize, usize)> = xy.into_iter().map(|(x, y)| (x - 1, y - 1)).collect();

    let mut ans = std::usize::MAX;
    for runner in (0..n).permutations(n) {
        if runner
            .iter()
            .zip(&runner[1..])
            .all(|(x, y)| !xy.contains(&(*x.min(y), *x.max(y))))
        {
            let time = runner.into_iter().enumerate().map(|(j, i)| a[i][j]).sum();
            ans = ans.min(time);
        }
    }

    if ans == std::usize::MAX {
        println!("{}", -1);
    } else {
        println!("{}", ans);
    }
}

解説

N 人の選手が N 個の区画を重複なく走り、仲が悪い人が前後にならないような組み合わせを考える問題です。このような問題では permutations() を使います。

まとめ

  • 組み込み型 T の最大値・最小値は std::T::MIN, std::T::MAX で定義されている

Discussion

コメントにはログインが必要です。