[O(N×5!)] C - MAD / TEAM ZONeエナジー プログラミングコンテスト “HELLO SPACE”

12789 ワード
AtCoder 順列 Rust Rust テキストリンク

問題

要旨

$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$ 以上にすることが可能かどうか。

仮に５人選んでよいのであれば、AからEそれぞれについての最強メンバーを集めればよいのであるが、実際には３人であるので兼任が必要となる。５種類の能力を３人（以下）で担当する必要がある。

ここで能力担当の分け方を軸に考え直す。
例えば分け方を AB | CD | E に固定した場合、N人の内の誰かがABを、誰かがCDを、誰かがEを満たせば条件を満たす。この「誰か」は重複が可能であり、例えばABCDEの能力全てを１人が担当するケースもカバーしている。
$\{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も解けず茶パフォ止まりとなった。

敗因

風呂に入りながら考えた。能力の分担方法を全列挙する。

  • １人５役
  • １人４役、１人１役
  • １人３役、１人２役
  • １人３役、１人１役、１人１役
  • １人２役、１人２役、１人１役

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);
}

抱負

結果にめげず、マイペースで最良のアルゴリズムを追求し続ける。
（だから点が取れないというのに）
これが記事の初公開です。今後ともよろしくお願いします。