NYPC 2025 R2B 코드

문제는 https://nypc.github.io/2025 에서 확인하실 수 있습니다.

제가 짠거 올립니다. 공통적으로 다음 FastIO 코드를 썼습니다.

mod fio {
    use std::{
        cell::RefCell,
        convert::TryInto,
        fmt::Debug,
        io::{stdin, stdout, BufRead, BufWriter, StdinLock, StdoutLock},
        str::FromStr,
    };
    thread_local! {
        pub static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
        pub static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
    }
 
    #[allow(dead_code)]
    pub fn read<T: FromStr>() -> T
    where
        <T as FromStr>::Err: Debug,
    {
        read_line().parse().unwrap()
    }
 
    #[allow(dead_code)]
    pub fn read_vec<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        read_line()
            .split_whitespace()
            .map(|x| x.parse().unwrap())
            .collect()
    }
 
    #[allow(dead_code)]
    pub fn read_tuple<T, const N: usize>() -> [T; N]
    where
        T: FromStr + Debug,
        <T as FromStr>::Err: Debug,
    {
        read_vec::<T>().try_into().unwrap()
    }
 
    /// whitespace at the end of the line is ignored
    pub fn read_line() -> String {
        let mut s = String::new();
        STDIN.with(|cell| {
            cell.borrow_mut().read_line(&mut s).unwrap();
        });
        String::from_str(s.trim_end()).unwrap()
    }
}
 
#[macro_export]
macro_rules! print {
    ($($t:tt)*) => {
        fio::STDOUT.with(|cell|{
            use std::io::Write;
            write!(cell.borrow_mut(), $($t)*).unwrap()
        })};
}
 
#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        fio::STDOUT.with(|cell| {
            use std::io::Write;
            writeln!(cell.borrow_mut(), $($t)*).unwrap()
        })
    };
}
 
#[macro_export]
macro_rules! flush {
    () => {
        fio::STDOUT.with(|cell| {
            use std::io::Write;
            cell.borrow_mut().flush().unwrap()
        });
    };
}

1번

 

앞에서 i번만큼, 뒤에서 j번만큼 바꿨을 때, i+j <= K 가 되도록 교환횟수를 정하면 되므로, 해당하는 (i, j)에 대해서 앞쪽 최댓값, 뒤쪽 최솟값을 구해 가장 큰 차이를 구해줍니다. 단, 앞과 뒤를 교차해서 가져올 때(K >= N-1)는 교환 횟수를 한 번 아낄 수 있다는 점에 주의하면서 코딩합니다.

use fio::*;

fn main() {
    let [n, k] = read_tuple::<usize, 2>();
    let a = read_vec::<i32>();
    let k = (if k >= n - 1 { k + 1 } else { k }).min(2 * n - 2);

    let mut pref_min = a.clone();
    let mut suff_max = a.clone();
    for i in 1..n {
        pref_min[i] = pref_min[i].min(pref_min[i - 1]);
    }
    for i in (0..n - 1).rev() {
        suff_max[i] = suff_max[i].max(suff_max[i + 1]);
    }

    let mut ans = a[n - 1] - a[0];
    for i in k.saturating_sub(n - 1)..=k.min(n - 1) {
        let j = k - i;
        ans = ans.max(suff_max[n - 1 - i] - pref_min[j]);
    }
    println!("{ans}");
}

2번

 

모든 노드의 서브트리의 노드 개수 합 = 모든 조상 - 자손 쌍의 개수 = 모든 노드의 높이 합입니다.

모든 노드의 높이 합은 각 높이에 노드가 몇 개 있는지를 가지고 문제를 해결하면 되고, 기본적으로는 k배씩 늘어납니다. mod (특히 p가 2의 배수인 경우) 와 k=1인 경우 등에 유의합시다.

use fio::*;

fn solve(n: u64, k: u64, p: u64) -> u64 {
    if k == 1 {
        let n = n % (2 * p);
        n * (n + 1) / 2 % p
    } else {
        let mut ans = 0;
        let mut rem = n;
        let mut cur = 1;
        let mut lev = 1;
        while rem > 0 {
            ans += (lev % p) * (cur % p);
            ans %= p;

            rem -= cur;
            cur = cur.saturating_mul(k).min(rem);
            lev += 1;
        }

        ans
    }
}

fn main() {
    let t = read();
    for _ in 0..t {
        let [n, k, p] = read_tuple::<u64, 3>();
        println!("{}", solve(n, k, p));
    }
}

 

3번

(낭비하지 않고) 보낼 수 있는 로봇들의 집합은 매트로이드 구조를 이루기 때문에, 거리가 긴것부터 차례대로 보내보는 그리디가 성립합니다. 로봇들을 보낼 수 있는 조건은 k들을 뽑아서 정렬했을 때, i번째 원소가 i보다 작거나 같은 것이고, 이 판단은 set을 이용해서 쉽게 최적화 할 수 있습니다.

use std::collections::BTreeSet;
use std::iter::FromIterator;
 
use fio::*;
fn main() {
    let n = read::<usize>();
    let mut a = vec![];
    for _ in 0..n {
        let [k, d] = read_tuple::<usize, 2>();
        a.push((d, k));
    }
    a.sort_unstable();
    let mut ans = 0;
    let mut bs = BTreeSet::from_iter(0..=n);
    for (d, k) in a.into_iter().rev() {
        if let Some(&x) = bs.range(..=k).next_back() {
            ans += d;
            bs.remove(&x);
        }
    }
    println!("{ans}");
}

4번

LP를 이용하여 해결할 수 있습니다. 각 변수를 레벨 i에서 레벨 N까지 강화하는데 소요하는 비용의 기댓값이라고 잡으면 LP식을 세울 수 있고, 이를 scipy의 솔버를 이용해서 풀면 됩니다.

from scipy.optimize import linprog


def solve(N, C, D, P):
    A, b = [], []

    for i in range(N):
        for j in range(-1, i):
            # use coupon on i -> j
            arr = [0] * N
            arr[i] = 1
            for k in range(N):
                arr[max(j + 1, k)] -= P[i][k]
            A.append(arr)
            b.append(C[i] + (0 if j == -1 else D[i][j]))

    return -linprog([-1] + [0] * (N - 1), A, b).fun


def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        C = list(map(float, input().split()))
        D = [[]]
        for i in range(1, N):
            D.append(list(map(float, input().split())))
        P = [list(map(lambda x: float(x) / 1e6, input().split())) for _ in range(N)]
        print(f"{solve(N, C, D, P)}")


if __name__ == "__main__":
    main()