문제

요지

$i, j, k ∈ { 1, 2, ..., N }$
$min(max(A_i, A_j, A_k), max(B_i, B_j, B_k), ..., max(E_i, E_j, E_k))$ 최대화

생각

$N$이 최대 3,000이므로, 전체 탐색이라고 $_{3000}P_3$ = 4,495,501,000 으로 TLE.
중앙값을 찾을 때처럼 이분 탐색법이 좋을 것 같다.
작은 문제는 종합력을 $k$ 이상으로 할 수 있을지 어떨지.

만약 5명 선택해도 된다면, A부터 E 각각에 대한 최강 멤버를 모으면 좋지만, 실제로는 3명이므로 겸임이 필요하다. 5종류의 능력을 3명(이하)으로 담당할 필요가 있다.

여기서 능력 담당의 나누는 방법을 축으로 다시 생각한다.
예를 들어 나누는 방법을 AB | CD | E 에 고정했을 경우, N명 중 누군가가 AB를, 누군가가 CD를, 누군가가 E를 채우면 조건을 채운다. 이 "누군가"는 중복이 가능하며, 예를 들어 ABCDE의 모든 능력을 1명이 담당하는 경우도 커버하고 있다.
$\{0 (=A), 1 (=B), 2 (=C), 3 (=D), 4 (=E)\}$ 로 구성된 순열을 전체 열거하고, 예를 들어 {2, 0 , 4, 3, 1}라면 능력의 분담을 CA | ED | B에 대응시켜 판정하고, 나누는 방법 중 하나라도 요건을 충족하면 OK이다. 할 수 있었다!!!!샘플도 다녔다. GO!!!!! → WA

c.rs [WA!!!]

use itertools::Itertools;

fn main() {
    proconio::input! { n: usize, abcde: [[i64; 5]; n], };

    let mut left = 1;
    let mut right = 1_000_000_001;
    while right - left > 1 {
        let mid = (left + right) / 2;
        let mut res = false;
        for i in (0usize..=4).permutations(5) {
            let mut flag = [false; 3];
            for v in &abcde {
                flag[0] |= v[i[0]] >= mid && v[i[1]] >= mid;
                flag[1] |= v[i[2]] >= mid && v[i[3]] >= mid;
                flag[2] |= v[i[4]] >= mid;
            }
            res |= flag[0] && flag[1] && flag[2]; 
        }
        if res {
            left = mid;
        } else {
            right = mid;
        }
    }
    println!("{}", left);
}

어쩐지 코너 케이스로 걷어차는 것 같다. 프로덕션 중에는 더 이상의 진전이 없어, D도 풀리지 않고 차 파포 정지가 되었다.

패인

목욕에 들어가면서 생각했다. 능력의 분담 방법을 전체 열거한다.

1인 5역

1인 4역, 1인 1역

1인 3역, 1인 2역

1 인 3 역, 1 인 1 역, 1 인 1 역

1 인 2 역, 1 인 2 역, 1 인 1 역

2-2-1 포메이션에서는 3-1-1에 대한 대책이 되어 있지 않았다(그 외는 모두 커버하고 있다).

발전

또한, 능력의 분담 방법을 고정한 상태에서는 종합력의 최선치를 직접 구하는 것이 가능(이분 탐색법이 불필요)인 것을 깨달았다. 예를 들면 ABC|D|E의 나누는 방법이면, ABC의 최저치가 제일 큰 사람, D가 제일 큰 사람, E가 제일 큰 사람을 중복을 허락해 데려와 최저치를 취하면, 그것이 그 나누는 방법에서의 최선의 스코어가 된다.
모든 분할 방법을 스캔하여 최대 값을 취하면 그것이 그대로 대답이됩니다.
$O(N×5!)$이며, 얼마만큼 고속이다.

c.rs [AC!!!]

use itertools::Itertools;
fn main() {
    proconio::input! { abcde: [[i64; 5]], };
    let mut ans = 0;
    for i in (0usize..=4).permutations(5) {
        let (mut s01, mut s23, mut s4) = (0, 0, 0);
        let (mut s012, mut s3) = (0, 0);
        for v in &abcde {
            let f = |x| v[i[x]];
            s01 = s01.max( f(0).min(f(1)) );
            s23 = s23.max( f(2).min(f(3)) );
            s4 = s4.max( f(4) );
            s012 = s012.max( f(0).min(f(1)).min(f(2)) );
            s3 = s3.max( f(3) );
        }
        ans = ans.max( s01.min(s23).min(s4) ).max( s012.min(s3).min(s4));
    }
    println!("{}", ans);
}

포부

결과에 드물지 않고, 내 페이스로 최상의 알고리즘을 추구하는 것을 계속한다.
(그러니까 점을 잡을 수 없다는데)
이것이 기사의 첫 공개입니다. 앞으로도 잘 부탁드립니다.