ABC097

published: 2020/9/7 update: 2020/9/9

ABC097 A-D

前提

#![allow(non_snake_case)]
#![allow(unused_imports)]

use proconio::{input, fastout};
use proconio::marker::*;
use whiteread::parse_line;
use std::collections::*;
use num::*;
use num_traits::*;
use superslice::*;
use std::ops::*;

use itertools::Itertools;
use itertools_num::ItertoolsNum;

A

#[fastout]
fn solve() {
    const MOD: usize = 1_000_000_007;
    const INF: usize = std::usize::MAX;
 
    input!{ a: isize, b: isize, c: isize, d: isize, }
 
    let flag = if (a - c).abs() <= d {
        true
    } else if (a - b).abs() <= d && (b - c).abs() <= d {
        true
    } else {
        false
    };
 
    if flag {
        println!("Yes");
    } else {
        println!("No");
    } 
}
 
fn main() {
    solve();
}

B

pub fn prime_factorize<T: PrimInt + NumAssign>(mut n: T) -> Vec<(T, T)> {
    let mut res: Vec<(T, T)> = Vec::new();
    let mut i: T = one::<T>().signed_shl(1);
    while i * i <= n {
        if n % i == zero() {
            let mut ex = zero::<T>();
            while n % i == zero() {
                ex += one();
                n = n / i;
            }
            res.push((i, ex));
        }
        i += one();
    }
    if n != one() {
        res.push((n, one()))
    }
    res
}

#[fastout]
fn solve() {
    input!{
        n: usize,
    }
 
    let mut ans = 1;
 
    for i in (1..=n).rev() {
        let primes = prime_factorize(i);
        if primes.iter().map(|x| x.1).any(|x| x == 1) { continue; }
        if primes.iter().map(|x| x.1).all_equal() {
            ans = i;
            break;
        }
    }
 
    println!("{}", ans);
}
 
fn main() {
    solve()
}

素因数分解して、素因数の数が1のものがあったらアウト。

C

fn solve() {
    input!{
        s: Chars,
        K: usize,
    }

    let mut length = if s.len() < 5 { s.len() } else { 5 };
    let mut bset_all: BTreeSet<String> = BTreeSet::new();

    while length > 0 {
        // dbg!(&bset_all);
        let mut tmp_bset: BTreeSet<String> = BTreeSet::new();
        for i in 0..(s.len()-length+1) {
            let tmp_string = s[i..i+length].iter().map(|c| *c).collect::<String>();
            if !bset_all.contains(&tmp_string) {
                tmp_bset.insert(tmp_string);
            }
        }

        bset_all.append(&mut tmp_bset);
        length -= 1;
    }

    for (i, str) in bset_all.iter().enumerate() {
        if i == K-1 { println!("{}", str); return; }
    }
}

fn main() {
    solve()
}

小さい方から見ればよくなので、明らかに長さ5以下のsubstring（部分文字列）のみを見れば良い。

D

#[derive(Debug, Clone)]
pub struct UnionFind<K> {
    // For element at index *i*, store the index of its parent; the representative itself
    // stores its own index. This forms equivalence classes which are the disjoint sets, each
    // with a unique representative.
    parent: Vec<K>,

    // size vector
    size: Vec<usize>,
    // group_num
    group_num: usize,
}

#[inline]
unsafe fn get_unchecked<K>(xs: &[K], index: usize) -> &K {
    debug_assert!(index < xs.len());
    xs.get_unchecked(index)
}

#[inline]
unsafe fn get_unchecked_mut<K>(xs: &mut [K], index: usize) -> &mut K {
    debug_assert!(index < xs.len());
    xs.get_unchecked_mut(index)
}

impl<K> UnionFind<K>
where
    K: PrimInt + std::hash::Hash,
{
    /// Create a new `UnionFind` of `n` disjoint sets.
    pub fn new(n: usize) -> Self {
        let size = vec![1; n];
        let parent = (0..n).map(|x| K::from(x).unwrap()).collect::<Vec<K>>();
        let group_num = n;
        Self { parent, size, group_num }
    }

    /// Return the representative for `x`.
    ///
    /// **Panics** if `x` is out of bounds.
    pub fn find(&self, x: K) -> K {
        assert!(x.to_usize().unwrap() < self.parent.len());
        unsafe {
            let mut x = x;
            loop {
                // Use unchecked indexing because we can trust the internal set ids.
                let xparent = *get_unchecked(&self.parent, x.to_usize().unwrap());
                if xparent == x {
                    break;
                }
                x = xparent;
            }
            x
        }
    }

    /// Return the representative for `x`.
    ///
    /// Write back the found representative, flattening the internal
    /// datastructure in the process and quicken future lookups.
    ///
    /// **Panics** if `x` is out of bounds.
    pub fn find_mut(&mut self, x: K) -> K {
        assert!(x.to_usize().unwrap() < self.parent.len());
        unsafe { self.find_mut_recursive(x) }
    }

    unsafe fn find_mut_recursive(&mut self, mut x: K) -> K {
        let mut parent = *get_unchecked(&self.parent, x.to_usize().unwrap());
        while parent != x {
            let grandparent = *get_unchecked(&self.parent, parent.to_usize().unwrap());
            *get_unchecked_mut(&mut self.parent, x.to_usize().unwrap()) = grandparent;
            x = parent;
            parent = grandparent;
        }
        x
    }

    /// Returns `true` if the given elements belong to the same set, and returns
    /// `false` otherwise.
    pub fn equiv(&self, x: K, y: K) -> bool {
        self.find(x) == self.find(y)
    }

    /// Unify the two sets containing `x` and `y`.
    ///
    /// Return `false` if the sets were already the same, `true` if they were unified.
    ///
    /// **Panics** if `x` or `y` is out of bounds.
    pub fn union(&mut self, x: K, y: K) -> bool {
        if x == y {
            return false;
        }
        let xrep = self.find_mut(x);
        let yrep = self.find_mut(y);

        if xrep == yrep {
            return false;
        }

        let xrepu = xrep.to_usize().unwrap();
        let yrepu = yrep.to_usize().unwrap();
        let xsize = self.size[xrepu];
        let ysize = self.size[yrepu];

        // The rank corresponds roughly to the depth of the treeset, so put the
        // smaller set below the larger
        if xsize > ysize {
            self.parent[yrepu] = xrep;
            self.size[xrepu] += ysize;
        } else {
            self.parent[xrepu] = yrep;
            self.size[yrepu] += xsize;
        }
        self.group_num -= 1;
        true
    }

    /// Return a vector mapping each element to its representative.
    pub fn into_labeling(mut self) -> Vec<K> {
        // write in the labeling of each element
        unsafe {
            for ix in 0..self.parent.len() {
                let k = *get_unchecked(&self.parent, ix);
                let xrep = self.find_mut_recursive(k);
                *self.parent.get_unchecked_mut(ix) = xrep;
            }
        }
        self.parent
    }

    pub fn size(&self, x: K) -> usize {
        let xrep = self.find(x);
        let xrepu = xrep.to_usize().unwrap();

        self.size[xrepu]
    }

    pub fn member(&self, x: K) -> HashSet<K> {
        // O(n)
        let xrep = self.find(x);
        let mut set: HashSet<K> = HashSet::new();

        for i in 0..self.parent.len() {
            let i_k = K::from(i).unwrap();
            if self.find(i_k) == xrep {
                set.insert(i_k);
            }
        }

        set
    }

    pub fn member_map(&self) -> HashMap<K, HashSet<K>> {
        // O(n^2)
        let mut map: HashMap<K, HashSet<K>> = HashMap::new();
        for i in 0..self.parent.len() {
            map.entry(K::from(i).unwrap()).or_insert(self.member(K::from(i).unwrap()));
        }
        map
    }
}


#[fastout]
fn solve() {
    input!{
        n: usize, m: usize,
        p_vec: [usize; n],
        xy_vec: [(usize, usize); m]
    }

    let mut un: UnionFind<usize> = UnionFind::new(n);

    for &(x, y) in xy_vec.iter() {
        un.union(x-1, y-1);
    }

    let mut ans = 0;

    for (i, p) in p_vec.iter().enumerate() {
        if i == *p-1 { 
            ans += 1;
            continue;
        }

        if un.equiv(p-1, p_vec[p-1]-1) {
            ans += 1;
        }
    }

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

swapできる対象をエッジとするグラフだと考えると、同じ連結成分に属していればそのindex同士は交換可能になる。union-findで正しい場所にある値同士が交換可能かどうか判定していけば答えは求まる。

memberに属しているかどうかを判定したくてmemberメソッドみたいなのを作成したが明らかに遅いのでデバッグ以外に使うことはなさそう。基本的にこれを使いそうになったらeqivを使うことを考えるべき。

これABC177-Dと対して難易度変わらない気がするんだけど水色...？