2021-11-16

2021/11/16

ABC155E - Payment

桁DPは前の桁から、という思い込みがあって全然見えなかった…頭が固い……

const INF: usize = 1 << 60;
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: Vec<usize> = sc
        .read::<String>()
        .bytes()
        .map(|b| b as usize - b'0' as usize)
        .collect();

    let mut dp = vec![0, INF];
    for d in n.into_iter().rev() {
        let mut next = vec![INF; 2];
        for carry in 0..2 {
            let pay = carry + d;
            if pay < 10 {
                next[0] = next[0].min(dp[carry] + pay);
            }
            next[1] = next[1].min(dp[carry] + 10 - pay);
        }
        dp = next;
    }

    let ans = dp[0].min(dp[1] + 1);
    println!("{}", ans);
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

AGC037D - Sorting a Grid

atcoder.jp

各列ごとに順番にマッチングをしていくと終盤で詰んでしまわないか？というところから先に進まなかった。具体的に詰むような終盤の状態を構築しようとするとできないことはすぐに分かるので、具体例を考えてみるべきだった。

use crate::dinitz::Dinitz;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let m: usize = sc.read();
    let mut a: Vec<Vec<usize>> = vec![vec![0; m]; n];
    for i in 0..n {
        for j in 0..m {
            a[i][j] = sc.usize0();
        }
    }

    let mut used = vec![vec![false; m]; n];
    let mut edge_id = vec![vec![0; m]; n];
    let mut columns = vec![];
    for _ in 0..m {
        let mut graph = Dinitz::new(2 * n + 2);
        let source = 2 * n;
        let sink = 2 * n + 1;
        for i in 0..n {
            graph.add_edge(source, i, 1);
            graph.add_edge(i + n, sink, 1);
        }

        for i in 0..n {
            for j in 0..m {
                if used[i][j] {
                    continue;
                }

                let target_row = a[i][j] / m;
                edge_id[i][j] = graph.g[i].len();
                graph.add_edge(i, target_row + n, 1);
            }
        }

        let flow = graph.max_flow(source, sink);
        assert_eq!(flow as usize, n);

        let mut column = vec![];
        for i in 0..n {
            for j in 0..m {
                if used[i][j] {
                    continue;
                }

                let ej = edge_id[i][j];
                if graph.g[i][ej].cap == 0 {
                    used[i][j] = true;
                    column.push(a[i][j]);
                }
            }
        }

        assert_eq!(column.len(), n);
        columns.push(column);
    }

    for i in 0..n {
        for j in 0..m {
            if j > 0 {
                sc.write(' ');
            }
            sc.write(columns[j][i] + 1);
        }
        sc.write('\n');
    }

    for column in columns.iter_mut() {
        column.sort();
    }
    for i in 0..n {
        for j in 0..m {
            if j > 0 {
                sc.write(' ');
            }
            sc.write(columns[j][i] + 1);
        }
        sc.write('\n');
    }
}
pub mod dinitz {
    const INF: i64 = 1 << 60;
    pub struct Edge {
        pub to: usize,
        pub rev: usize,
        pub is_reversed: bool,
        pub cap: i64,
    }

    pub struct Dinitz {
        pub g: Vec<Vec<Edge>>,
    }

    impl Dinitz {
        pub fn new(v: usize) -> Dinitz {
            let mut g: Vec<Vec<Edge>> = Vec::new();
            for _ in 0..v {
                g.push(Vec::new());
            }
            Dinitz { g }
        }

        pub fn add_edge(&mut self, from: usize, to: usize, cap: i64) {
            let to_len = self.g[to].len();
            let from_len = self.g[from].len();
            self.g[from].push(Edge {
                to,
                rev: to_len,
                is_reversed: false,
                cap,
            });
            self.g[to].push(Edge {
                to: from,
                rev: from_len,
                is_reversed: true,
                cap: 0,
            });
        }

        fn dfs(
            &mut self,
            v: usize,
            sink: usize,
            flow: i64,
            level: &[i32],
            iter: &mut [usize],
        ) -> i64 {
            if v == sink {
                return flow;
            }
            while iter[v] < self.g[v].len() {
                let flow = std::cmp::min(flow, self.g[v][iter[v]].cap);
                let to = self.g[v][iter[v]].to;
                if flow > 0 && level[v] < level[to] {
                    let flowed = self.dfs(to, sink, flow, level, iter);
                    if flowed > 0 {
                        let rev = self.g[v][iter[v]].rev;
                        self.g[v][iter[v]].cap -= flowed;
                        self.g[to][rev].cap += flowed;
                        return flowed;
                    }
                }
                iter[v] += 1;
            }
            0
        }

        fn bfs(&self, s: usize) -> Vec<i32> {
            let v = self.g.len();
            let mut level = vec![-1; v];
            level[s] = 0;
            let mut deque = std::collections::VecDeque::new();
            deque.push_back(s);
            while let Some(v) = deque.pop_front() {
                for e in self.g[v].iter() {
                    if e.cap > 0 && level[e.to] < 0 {
                        level[e.to] = level[v] + 1;
                        deque.push_back(e.to);
                    }
                }
            }
            level
        }

        pub fn max_flow(&mut self, s: usize, t: usize) -> i64 {
            let v = self.g.len();
            let mut flow: i64 = 0;
            loop {
                let level = self.bfs(s);
                if level[t] < 0 {
                    return flow;
                }
                let mut iter = vec![0; v];
                loop {
                    let f = self.dfs(s, t, INF, &level, &mut iter);
                    if f == 0 {
                        break;
                    }
                    flow += f;
                }
            }
        }
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

2021-11-14

2021/11/14

ABC227G - Divisors of Binomial Coefficient

atcoder.jp

ついに区間篩を知らなかったことが仇に…

$[2, X$ ] の素数を求めながら $[Y, X^{2}$ ] の素因数分解もできるの、言われてみればそうなんだけど、すごい。

use crate::mod_int::ModInt;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let k: usize = sc.read();

    let from = n - k + 1;
    let to = n;

    let sq_n = (n as f64).sqrt() as usize + 1;
    let l = k.max(sq_n);
    let mut divisors = vec![vec![]; l + 1];
    let mut divisors_big = vec![vec![]; k];
    for p in 2..=l {
        if divisors[p].is_empty() {
            let mut cur = p;
            while cur <= l {
                divisors[cur].push(p);
                cur += p;
            }

            let mut cur = (from + p - 1) / p * p;
            while cur <= to {
                divisors_big[cur - from].push(p);
                cur += p;
            }
        }
    }

    let mut big_primes = 0;
    let mut count = vec![0; l + 1];
    for i in 1..=k {
        let mut lower = i;
        for &prime in divisors[i].iter() {
            while lower % prime == 0 {
                lower /= prime;
                count[prime] -= 1;
            }
        }

        let mut upper = n - i + 1;
        for &prime in divisors_big[n - i + 1 - from].iter() {
            while upper % prime == 0 {
                upper /= prime;
                count[prime] += 1;
            }
        }

        if upper > 1 {
            big_primes += 1;
        }
    }

    let mut ans = ModInt::from(1);
    for c in count {
        assert!(c >= 0, "{}", c);
        ans *= c + 1;
    }
    ans *= ModInt::from(2).pow(big_primes);
    println!("{}", ans.value());
}

pub mod mod_int {
    type ModInternalNum = i64;
    thread_local!(
        static MOD: std::cell::RefCell<ModInternalNum> = std::cell::RefCell::new(0);
    );

    pub fn set_mod_int<T: ToInternalNum>(v: T) {
        MOD.with(|x| x.replace(v.to_internal_num()));
    }
    fn modulo() -> ModInternalNum {
        998244353
    }

    pub struct ModInt(ModInternalNum);
    impl Clone for ModInt {
        fn clone(&self) -> Self {
            Self(self.0)
        }
    }
    impl Copy for ModInt {}

    impl ModInt {
        fn internal_new(mut v: ModInternalNum) -> Self {
            let m = modulo();
            if v >= m {
                v %= m;
            }
            Self(v)
        }

        pub fn internal_pow(&self, mut e: ModInternalNum) -> Self {
            let mut result = 1;
            let mut cur = self.0;
            let modulo = modulo();
            while e > 0 {
                if e & 1 == 1 {
                    result *= cur;
                    result %= modulo;
                }
                e >>= 1;
                cur = (cur * cur) % modulo;
            }
            Self(result)
        }

        pub fn pow<T>(&self, e: T) -> Self
        where
            T: ToInternalNum,
        {
            self.internal_pow(e.to_internal_num())
        }

        pub fn value(&self) -> ModInternalNum {
            self.0
        }
    }

    pub trait ToInternalNum {
        fn to_internal_num(&self) -> ModInternalNum;
    }
    impl ToInternalNum for ModInt {
        fn to_internal_num(&self) -> ModInternalNum {
            self.0
        }
    }
    macro_rules! impl_primitive {
        ($primitive:ident) => {
            impl From<$primitive> for ModInt {
                fn from(v: $primitive) -> Self {
                    let v = v as ModInternalNum;
                    Self::internal_new(v)
                }
            }
            impl ToInternalNum for $primitive {
                fn to_internal_num(&self) -> ModInternalNum {
                    *self as ModInternalNum
                }
            }
        };
    }
    impl_primitive!(u8);
    impl_primitive!(u16);
    impl_primitive!(u32);
    impl_primitive!(u64);
    impl_primitive!(usize);
    impl_primitive!(i8);
    impl_primitive!(i16);
    impl_primitive!(i32);
    impl_primitive!(i64);
    impl_primitive!(isize);

    impl<T: ToInternalNum> std::ops::AddAssign<T> for ModInt {
        fn add_assign(&mut self, rhs: T) {
            let mut rhs = rhs.to_internal_num();
            let m = modulo();
            if rhs >= m {
                rhs %= m;
            }

            self.0 += rhs;
            if self.0 >= m {
                self.0 -= m;
            }
        }
    }

    impl<T: ToInternalNum> std::ops::Add<T> for ModInt {
        type Output = ModInt;
        fn add(self, rhs: T) -> Self::Output {
            let mut res = self;
            res += rhs;
            res
        }
    }
    impl<T: ToInternalNum> std::ops::SubAssign<T> for ModInt {
        fn sub_assign(&mut self, rhs: T) {
            let mut rhs = rhs.to_internal_num();
            let m = modulo();
            if rhs >= m {
                rhs %= m;
            }
            if rhs > 0 {
                self.0 += m - rhs;
            }
            if self.0 >= m {
                self.0 -= m;
            }
        }
    }
    impl<T: ToInternalNum> std::ops::Sub<T> for ModInt {
        type Output = Self;
        fn sub(self, rhs: T) -> Self::Output {
            let mut res = self;
            res -= rhs;
            res
        }
    }
    impl<T: ToInternalNum> std::ops::MulAssign<T> for ModInt {
        fn mul_assign(&mut self, rhs: T) {
            let mut rhs = rhs.to_internal_num();
            let m = modulo();
            if rhs >= m {
                rhs %= m;
            }
            self.0 *= rhs;
            self.0 %= m;
        }
    }
    impl<T: ToInternalNum> std::ops::Mul<T> for ModInt {
        type Output = Self;
        fn mul(self, rhs: T) -> Self::Output {
            let mut res = self;
            res *= rhs;
            res
        }
    }

    impl<T: ToInternalNum> std::ops::DivAssign<T> for ModInt {
        fn div_assign(&mut self, rhs: T) {
            let mut rhs = rhs.to_internal_num();
            let m = modulo();
            if rhs >= m {
                rhs %= m;
            }
            let inv = Self(rhs).internal_pow(m - 2);
            self.0 *= inv.value();
            self.0 %= m;
        }
    }

    impl<T: ToInternalNum> std::ops::Div<T> for ModInt {
        type Output = Self;
        fn div(self, rhs: T) -> Self::Output {
            let mut res = self;
            res /= rhs;
            res
        }
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

ARC067F - Yakiniku Restaurants

atcoder.jp

[from, to) で利用できるものについて、N x N の2次元平面上にプロットしてみると、長方形領域の集合になっているという問題。直線上を移動する問題を2次元にプロットするところに発想の飛躍があるように感じたが、典型的な考え方かもしれない。ものにしたい。

use crate::sparse_table::SparseTable;
use std::collections::VecDeque;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let m: usize = sc.read();
    let a: Vec<i64> = sc.vec(n - 1);
    let mut pos = vec![0; n];
    for i in 1..n {
        pos[i] = pos[i - 1] + a[i - 1];
    }

    let b: Vec<Vec<i64>> = (0..n).map(|_| sc.vec(m)).collect();

    let mut available = vec![vec![]; n];

    for ticket_id in 0..m {
        let b = (0..n).map(|j| (b[j][ticket_id], j)).collect::<Vec<_>>();
        let st = SparseTable::from(&b, (0, n), |a, b| a.max(b));

        let mut segments = VecDeque::new();
        segments.push_back((0, n));
        while let Some((from, to)) = segments.pop_front() {
            let (x, i) = st.get(from, to);
            available[from].push((i, ticket_id, x));
            if from < i {
                segments.push_back((from, i));
            }
            if i + 1 < to {
                segments.push_back((i + 1, to));
            }
        }
    }

    let mut ans = 0;
    let mut events = vec![vec![]; n];
    for from in 0..n {
        for &(i, ticket_id, x) in available[from].iter() {
            events[i].push((ticket_id, x));
        }

        let mut tickets = vec![0; m];
        let mut sum = 0;
        for i in 0..m {
            tickets[i] = b[from][i];
            sum += tickets[i];
        }
        for to in from..n {
            for &(i, x) in events[to].iter() {
                sum -= tickets[i];
                tickets[i] = x;
                sum += tickets[i];
            }

            let d = pos[to] - pos[from];
            ans = ans.max(sum - d);
        }
    }

    println!("{}", ans);
}
pub mod sparse_table {
    pub struct SparseTable<T, F> {
        data: Vec<Vec<T>>,
        op: F,
    }

    impl<T, F> SparseTable<T, F>
    where
        T: Copy,
        F: Fn(T, T) -> T,
    {
        pub fn from(v: &[T], init: T, op: F) -> Self {
            let size = v.len().next_power_of_two();
            let count = size.trailing_zeros() as usize + 1;
            let mut data = vec![vec![init; size]; count];
            for (i, v) in v.iter().cloned().enumerate() {
                data[0][i] = v;
            }
            for c in 1..count {
                for i in 0..size {
                    let next = std::cmp::min(size - 1, i + (1 << (c - 1)));
                    data[c][i] = op(data[c - 1][i], data[c - 1][next]);
                }
            }

            Self { data, op }
        }

        /// get the result for [l, r)
        pub fn get(&self, l: usize, r: usize) -> T {
            assert!(l < r);
            let length = r - l;
            if length == 1 {
                return self.data[0][l];
            }
            let block_size = length.next_power_of_two() >> 1;
            let c = block_size.trailing_zeros() as usize;
            let left = self.data[c][l];
            let right = self.data[c][r - block_size];
            (self.op)(left, right)
        }
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

2021-10-18

ABC223 G - Vertex Deletion

問題

atcoder.jp

解法

まず、木の最大マッチングは葉から貪欲に取っていくことで作れる。これは深さ優先探索で根付き木で (ある頂点vを含むサブツリーのマッチングの個数, vがマッチングに含まれているか) を再帰的に求めることで求まる。

この要領で、全方位木DPをして、全ての頂点について、その頂点を含まない（含むかどうか決める前の）マッチングの個数を求める。

コード

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let mut graph = vec![vec![]; n];
    for _ in 1..n {
        let a = sc.usize0();
        let b = sc.usize0();
        graph[a].push(b);
        graph[b].push(a);
    }

    let mut dp = vec![vec![]; n];
    let (greedy, _) = dfs(0, 0, &graph, &mut dp);

    let mut ans = vec![0; n];
    dfs2(0, 0, &graph, &mut dp, (0, false), &mut ans);

    let mut count = 0;
    for ans in ans {
        if ans == greedy {
            count += 1;
        }
    }
    println!("{}", count);
}

fn dfs(
    v: usize,
    p: usize,
    graph: &Vec<Vec<usize>>,
    dp: &mut Vec<Vec<(usize, bool)>>,
) -> (usize, bool) {
    let mut requested = false;
    let mut sum = 0;
    let deg = graph[v].len();
    dp[v] = vec![(0, false); deg];
    for (i, &next) in graph[v].iter().enumerate() {
        if next == p {
            continue;
        }

        let (count, prev_requested) = dfs(next, v, graph, dp);
        sum += count;
        requested |= prev_requested;
        dp[v][i] = (count, prev_requested);
    }

    if requested {
        (sum + 1, false)
    } else {
        (sum, true)
    }
}

fn dfs2(
    v: usize,
    p: usize,
    graph: &Vec<Vec<usize>>,
    dp: &mut Vec<Vec<(usize, bool)>>,
    dp_p: (usize, bool),
    ans: &mut [usize],
) {
    for (i, &next) in graph[v].iter().enumerate() {
        if next == p {
            dp[v][i] = dp_p;
        }
    }

    let deg = graph[v].len();
    let mut left_dp = vec![(0, false); deg + 1];
    let mut right_dp = vec![(0, false); deg + 1];

    for i in 0..deg {
        let (p_count, p_requested) = left_dp[i];
        let (dp_count, dp_requested) = dp[v][i];
        left_dp[i + 1] = (p_count + dp_count, p_requested || dp_requested);
    }
    for i in (0..deg).rev() {
        let (p_count, p_requested) = right_dp[i + 1];
        let (dp_count, dp_requested) = dp[v][i];
        right_dp[i] = (p_count + dp_count, p_requested || dp_requested);
    }

    ans[v] = left_dp[deg].0;
    for (i, &next) in graph[v].iter().enumerate() {
        if next == p {
            continue;
        }

        let (left_count, left_requested) = left_dp[i];
        let (right_count, right_requested) = right_dp[i + 1];

        let add = if left_requested || right_requested {
            1
        } else {
            0
        };

        dfs2(
            next,
            v,
            graph,
            dp,
            (left_count + right_count + add, add != 1),
            ans,
        );
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

全方位木DPは問題によって自由度が高いのでライブラリにしにくく感じる（一般にDPはライブラリにしにくい）ので、こうやって経験が積めるのは助かる。

2021-06-27

EC2 Amazon Linux を PostgreSQL インスタンスとして立ち上げる

#!/bin/bash -xe
amazon-linux-extras install postgresql11 -y
yum install postgresql-server postgresql-devel postgresql-contrib -y
postgresql-setup initdb
systemctl enable postgresql.service --now
sudo -u postgres createdb ${DatabaseName}
sudo -u postgres psql -U postgres -c "CREATE ROLE ${DatabaseUser} WITH LOGIN PASSWORD '${DatabasePassword}'"
sudo -u postgres psql -U postgres -c "GRANT ALL PRIVILEGES ON DATABASE ${DatabaseName} TO ${DatabaseUser}"
echo 'host all all 0.0.0.0/0 password' > /var/lib/pgsql/data/pg_hba.conf
echo 'local all all password' >> /var/lib/pgsql/data/pg_hba.conf
echo "listen_addresses = '*'" >> /var/lib/pgsql/data/postgresql.conf
systemctl restart postgresql.service