log 2021-07-02

---

• sport
  • cf 1471A Strange Partition
• meta

sport

cf 1471A Strange Partition

http://codeforces.com/problemset/problem/1471/A

rust solution

임의 두 원소를 합치면?

x 3 기준, 2,4 = 6 2,4 = 6 = 2, 1,2 3,4 = 7 = 3, 1,2 2,3 = 5 = 2, 1,1

어떤 규칙이 있는걸까? 어떻게 합쳐야 최대가 되고, 어떻게 해야 최소가 되는지 알아야 할 듯하다.

n이 크기 때문에 모든 경우를 시도할 수 없다.

[ a/x ] + [ b/x ] ~ [ (a+b)/x ] 를 비교하는 것 아닌가? [ 2/3 ] + [ 4/3 ] ~ [ (2+4)/3 ] 1 + 2 ~ 2

1. a/x, b/x가 전부 정수라면 값이 변하지 않을 것이다.
2. a/x 하나만 정수가 아닌 경우;

a/x = m+k라고 하자, [ a/x ] = m+1이 된다. (a+b)/x = (a/x) + (b/x) = (m+k)+(b/x) => [ (a+b)/x ] = [ (m+k+b/x )] = m+1 + [ b/x ] 즉 왼쪽과 식이 같아진다. (b/x가 정수이므로) 3. 둘 다 정수가 아닌 경우; a/x = m+j, b/x = n+k라 하자. 좌변은 m+n+2가 되고, 우변은 [ m+j+n+k ] = m+n+[ j + k ]가 된다. 따라서, j+k가 01이면 우변이 작아지고 (즉 합친 쪽이 작아지고), 12 이면 값이 같아진다.

위 경우들로 나눠 보면, 합치면 작아질 수는 있어도 커질 수는 없다. 따라서 다 합친 것과 다 냅둔 것을 계산?? 아마도 맞을 듯.

오버플로 문제로 1번, 나눠서 더해봤지만 소수 합 문제로 1번 틀림. 그냥 i32 -> i64로 바꿔서 맞음.

안전한 소수 합에 대해 검색한 결과 Kahan sum이라는 알고리즘 찾음.

fn solve<R: io::BufRead, W: io::Write>(scan: &mut Scanner<R>, out: &mut W) {
    let cases = ri32(scan);

    fn get_div_x_ceil(val:i64, x:i64) -> i64 {
        let val_float = val.to_string().parse::<f64>().unwrap();
        let x_float = x.to_string().parse::<f64>().unwrap();
        let val_div = (val_float / x_float).ceil() as i64;
        val_div.to_string().parse::<i64>().unwrap()
    }
    
    for _case in 0..cases {
        let (n,x) = (ri32(scan), ri64(scan));
        let mut vec = vec![];
        let mut sep_sum = 0;

        for _i in 0..n {
            let item = ri64(scan);
            vec.push(item);
            sep_sum = sep_sum + get_div_x_ceil(item, x);
        }
        let sum = vec.iter().sum::<i64>();
        
        // dbg!(n,x, sum, get_div_x_ceil(sum, x), sep_sum);
        writeln!(out, "{} {}", get_div_x_ceil(sum, x), sep_sum).ok();
    }
}

meta

문제를 어떻게 풀고 공부하는 것이 효율적일지 고민된다. 일단 기본적인 테크닉과 개념들은 강의로 공부하는게 좋을 듯 하긴 하다.

rust solve에 아래 모듈 적용하기 https://github.com/EbTech/rust-algorithms/blob/master/src/scanner.rs

---