ABC416

Fみたいな問題は全人類解いているだろうなと思っていたが意外と解かれておらず、思ったより良い順位に落ち着いた。

A - Vacation Validation

言われたとおりに。Rustだと区間に対してゴニョゴニョできるので、フラグ変数を持って～とかは考えなくてよくて楽。提出

use library::utils::input::Input;

fn solve(ip: &mut Input) {
    let (n, l, r) = ip.triple::<usize, usize, usize>();
    let l=l-1;
    let s = ip.next::<String>();
    println!("{}", if s[l..r].chars().all(|c| c=='o') { "Yes" } else { "No"} );

}

fn main() {
    static IS_MULTI_TEST_CASE :bool = false;
    let mut ip = Input::new();

    let t = if IS_MULTI_TEST_CASE {
        ip.next::<usize>()
    } else {
        1
    };

    for _ in 0..t {
        solve(&mut ip);
    }
}

B - 1D Akari

Daily Akariかな？#.を#oに置換して行けばよい。ただし、.始まりの場合には条件を満たせないため、それは別途処理する。提出

use library::utils::input::Input;

fn solve(ip: &mut Input) {
    let s = ip.next::<String>();
    let mut s = s.replace("#.", "#o").chars().collect::<Vec<_>>();
    if s[0] == '.' {
        s[0] = 'o';
    }
    println!("{}", s.iter().collect::<String>());
}

fn main() {
    static IS_MULTI_TEST_CASE :bool = false;
    let mut ip = Input::new();

    let t = if IS_MULTI_TEST_CASE {
        ip.next::<usize>()
    } else {
        1
    };

    for _ in 0..t {
        solve(&mut ip);
    }
}

C - Concat (X-th)

制約が全探索してください、といっているのでする。K重ループ(Kは入力値によって変わる)が必要だな、という場合は再帰を書くのが有効なことが多い¹。また、この手の問題は最大ケースが簡単に作れるので、適当に作って試してから提出するのがいい。提出

use library::utils::input::Input;

fn dfs(idx: usize, k: usize, v: String, s: &Vec<String>, res: &mut Vec<String>) {
    if idx >= k {
        res.push(v);
        return;
    }

    for i in 0..s.len() {
        dfs(idx+1, k, format!("{}{}", v, s[i]), s, res);
    }
}

fn solve(ip: &mut Input) {
    let (n,k,x) = ip.triple::<usize,usize,usize>();
    let vs = ip.vector::<String>(n);
    let mut ans = Vec::new();
    dfs(0, k, String::new(), &vs, &mut ans);
    ans.sort();
    println!("{}", ans[x-1]);
}

fn main() {
    static IS_MULTI_TEST_CASE :bool = false;
    let mut ip = Input::new();

    let t = if IS_MULTI_TEST_CASE {
        ip.next::<usize>()
    } else {
        1
    };

    for _ in 0..t {
        solve(&mut ip);
    }
}

D - Match, Mod, Minimize 2

はじめ最大化だと思っておりびっくりしたが、最小化だった。$A_i + B_j \geq M$となるペアをできるだけ作りたくて、「$A$に含まれる値で、まだペアが作られていないもののうち最大のもの」と「$B$に含まれる値で、$M$を超えさせるのに必要な値で最小のもの」を貪欲にマッチングさせれば良い。 実装は色々あるが、Aを降順にソートして、$B$は二分木ベースの辞書型に値をkey, 登場回数をvalueとしてゴニョゴニョするのが楽だと思う。C++ならmultisetなど。提出

use std::collections::BTreeMap;

use library::utils::input::Input;

fn solve(ip: &mut Input) {
    let (n, m) = ip.pair::<usize, u64>();
    let mut a = ip.vector::<u64>(n);
    let b = ip.vector::<u64>(n);

    let mut ans = a.iter().sum::<u64>() + b.iter().sum::<u64>();

    let mut map = BTreeMap::new();
    for bi in b {
        *map.entry(bi).or_insert(0u64) += 1;
    }

    a.sort();
    
    for ai in a.iter().rev() {
        let nd = m-*ai;
        let mut del = None;
        if let Some((k,v)) = map.range_mut(nd..).next() {
            ans -= m;
            *v -= 1;
            if *v==0 {
                del = Some(*k);
            }
        } else {
            break;
        }

        if let Some(key) = del {
            map.remove(&key);
        }
    }

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

fn main() {
    static IS_MULTI_TEST_CASE :bool = true;
    let mut ip = Input::new();

    let t = if IS_MULTI_TEST_CASE {
        ip.next::<usize>()
    } else {
        1
    };

    for _ in 0..t {
        solve(&mut ip);
    }
}

E - Development

全頂点対最短経路を求める必要があるため、ワーシャルフロイドを疑う。

クエリ1は、ワーシャルフロイド法では辺追加クエリは頂点数を$N$として$O(N^2)$でできることが知られており、十分高速にできる。クエリ3は毎回愚直に計算して良い。

問題はクエリ2。手元で計算ミスをしており愚直にやってもいいと思っていたが、そんな訳は無い($N^4$とかになって全然ダメ)。空港同士はすべて同じ時間で行き来できることを用いて、「ワープポイント」となる(超頂点の)空港を追加し、行きはコスト$T$、帰りはコスト$0$で移動できるように辺を追加するとうまく動作する。

これで全部解けた。入力ライブラリが遅いのか1000msを超えているが、気にしない。提出

use library::{graph::warshall_floyd::{DefaultWFelm, WFelm, WarshallFloyd}, utils::input::Input};

fn solve(ip: &mut Input) {
    let (n, m) = ip.pair::<usize, usize>();
    let mut g = ip.weighted_graph::<u64>(n, m, false, true);
    g.push(vec![]);
    
    let (k, t) = ip.pair::<usize, u64>();
    let d = ip.vector::<usize>(k).iter().map(|i| *i-1).collect::<Vec<_>>();
    for i in 0..k {
        g[d[i]].push((n, t));
        g[n].push((d[i], 0));
    }

    let mut wf = WarshallFloyd::new(&g, DefaultWFelm);
    let elm= DefaultWFelm;

    let q = ip.next();
    for _ in 0..q {
        let qt :i32 = ip.next();

        if qt == 1 {
            let (x,y,w) = ip.triple::<usize,usize,u64>();
            wf.add(x-1, y-1, w);
            wf.add(y-1, x-1, w);
        } else if qt == 2 {
            let x :usize = ip.next();
            let x = x-1;

            wf.add(x, n, t);
            wf.add(n, x, 0);
        } else {
            let mut res = 0;

            for i in 0..n {
                for j in 0..n {
                    let ret = wf.get(i, j);
                    if ret != elm.infinity() {
                        res += ret;
                    }
                }
            }
            println!("{}", res);
        }
    }
}

fn main() {
    static IS_MULTI_TEST_CASE :bool = false;
    let mut ip = Input::new();

    let t = if IS_MULTI_TEST_CASE {
        ip.next::<usize>()
    } else {
        1
    };

    for _ in 0..t {
        solve(&mut ip);
    }
}

1年ほど前にRoad Blocked 2でワーシャルフロイドでは辺追加クエリが頂点数に対して2乗でできることを教えてもらって、ライブラリにしておいた甲斐があった。