ABC395

6完で+7、まぁDで詰まってしまったとはいえかなり苦しいなぁと思います。一応暖まってはいるらしいですが...

A - Strictly Increasing?

問題文を読むと、

\(A\) が狭義単調増加であるとは \(1\leq i

と丁寧に説明されているので、これを愚直に判定すればよいです。 提出

use itertools::Itertools;
use proconio::input;

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

    println!("{}", if a.iter().tuple_windows().all(|(a, b)| a < b) {
        "Yes"
    } else {
        "No"
    });
}

B - Make Target

概要を読むと、既視感のある図が出てきます。いつだかの回に出てきた気がしますが見つかりません。えーん...
構築法は問題文に乗っていますが、実装ではその回の記憶を元に「外側からの距離」に着目することで \(O(N^2)\) で構築をしました。 提出

use itertools::{iproduct, Itertools};
use proconio::input;

fn main() {
    input!{
        n: usize,
    }
    let mut res = vec![vec!['.'; n]; n];
    for (i, j) in iproduct!(0..n, 0..n) {
        let di = i.min(n-i-1);
        let dj = j.min(n-j-1);
        
        if di.min(dj) % 2 == 0 {
            res[i][j] = '#';
        }
    }
    println!("{}", res.iter().map(|v| v.iter().join("")).join("\n"));
}

C - Shortest Duplicate Subarray

\(i\neq j\) であるような \(i, j\) であって \(A_i\neq A_j\) を満たす場合は、同じ値が無いため条件を満たす連続部分列は存在しません。
同じ値が複数個ある場合、両端が同じ値であるような部分列を取るべきです 。よって、各値が直前にいつでてきたか？を保持しておくことで、 \(O(N)\) で求めることができます。 提出

use std::collections::BTreeMap;
use proconio::input;

pub static INF: u64 = 1e18 as u64;

fn main() {
    input!{
        n: usize,
        a: [u64; n],
    }
    let mut map = BTreeMap::new();

    let mut ans = INF as usize;
    for (i, &ai) in a.iter().enumerate() {
        if let Some(&j) = map.get(&ai) {
            ans.chmin(i-j+1);
        }
        map.insert(ai, i);
    }
    println!("{}", if ans == INF as usize{
        "-1".to_string()
    } else {
        ans.to_string()
    });
}

D - Pigeon Swap

難しすぎます。操作の種類2が明らかに大変で、代わりに「巣の位置を入れ替える」という操作を行うことで高速化を図りたいです。しかし、巣の位置を入れ替えてしまうと操作の種類1: 鳩を指定された巣に移動させる、が高速に処理できなくなります 。そこで、新たに仮想indicateを作って管理することで高速にできるようにする、という典型です。
典型なんですが、頭をバグらせてしまい...1ペナでしかもかなりの時間を掛けました...
提出

use itertools::Itertools;
use proconio::{input, marker::Usize1};

fn main() {
    input!{
        n: usize,
        q: usize,
    }

    let mut su = (0..n).collect_vec();
    let mut p = (0..n).collect_vec();
    let mut hato = (0..n).collect_vec();
    for _ in 0..q {
        input! {
            t: u8,
        }
        if t == 1 {
            input! {
                a: Usize1,
                b: Usize1,
            }
            let b = su[b];
            hato[a] = b;
        } else if t == 2 {
            input! {
                a: Usize1,
                b: Usize1,
            }
            let ai = su[a];
            let bi = su[b];
            p.swap(ai, bi);
            su[p[ai]] = ai;
            su[p[bi]] = bi;
        } else {
            input! {
                a: Usize1,
            }
            println!("{}", p[hato[a]] + 1);
        }
    }
}

E - Flip Edge

愚直にグラフを反転する操作をするのは大変なので、代わりに反転済みのグラフを別途用意しておくことを考えます。元のグラフを \(G_表\) 、反転後のグラフを \(G_裏\) と呼びます。こうすると、「コスト \(X\) でグラフを反転する」という操作は「各頂点 \(p\) において、 \(G_{表,p}\) と \(G_{裏, p}\) を相互につなぐ重み \(X\) の辺を貼る」というように言い換えることが可能で、こうすることで問題は頂点 \(G_{表, 1}\) から \(G_{表, N}\) あるいは \(G_{裏, N}\) への最短経路問題に帰着することができます。
よって、Dijkstra法を用いることでこの問題が解けます。 提出

use std::{cmp::Reverse, collections::BinaryHeap};
use proconio::{input, marker::Usize1};

pub static INF: u64 = 1e18 as u64;

fn main() {
    input!{
        n: usize,
        m: usize,
        x: u64,
        e: [(Usize1, Usize1); m],
    }

    let g = e.iter()
        .fold(vec![vec![vec![]; n]; 2], |mut g, &(u, v)| {
            g[0][u].push(v);
            g[1][v].push(u);
            g
        });

    let mut seen = vec![vec![INF; n]; 2];
    let mut pq = BinaryHeap::new();
    pq.push(Reverse((0, 0, 0)));
    while let Some(Reverse((c, i, p))) = pq.pop() {
        if seen[i][p] != INF { continue; }
        seen[i][p] = c;

        for &ni in g[i][p].iter() {
            if seen[i][ni] == INF {
                pq.push(Reverse((c+1, i, ni)));
            }
        }

        if seen[1-i][p] == INF {
            pq.push(Reverse((c+x, 1-i, p)));
        }
    }
    println!("{}", seen[0][n-1].min(seen[1][n-1]));
}

F - Smooth Occlusion

条件を見ると、 \(H\) を定めることでそのような構成が可能か？を判定できそうです。これは、 \(H\) を決めておくと \(U_i\) が取りうる範囲が \([\max(H-D_i, 0), H)\) と限定されるからです。
そして、そのような判定が可能であれば、 \(H\) を二分探索して \(H\) としてあり得る最大値を求めることでこの問題を解くことができます 。
よって、考えるべきは判定問題です。各歯を見たときの \(U_i\) の取りうる範囲は前述の通りであり、これに直前の歯の取りうる範囲を組み合わせてandを取ることで、条件を満たすような取り方のうち可能な範囲が撮れるので、判定問題を解くことができました。
よって、 \(O(N\log \max(U_i+D_i))\) でこの問題を解くことができます。 提出

use proconio::input;

fn judge(key: i64, x: i64, v: &[(i64, i64)]) -> bool {
    let mut prev_range = (0, 1e10 as i64);

    for &(a, b) in v {
        let range = ((key-b).max(0), (key+b).min(a));
        let low = range.0.max(prev_range.0-x);
        let high = range.1.min(prev_range.1+x);
        if high < low {
            return false;
        }
        prev_range = (low, high);
    }
    true
}

fn main() {
    input!{
        n: usize,
        x: i64,
        v: [(i64, i64); n],
    }

    let mut ok = 0;
    let mut ng = 1e10 as usize;

    while ng - ok > 1 {
        let mid = (ok + ng) / 2;
        if judge(mid as i64, x, &v) {
            ok = mid;
        } else {
            ng = mid;
        }
    }

    println!("{}", v.iter().map(|&(a, b)| (a+b)-ok as i64).sum::<i64>());   
}