かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ZONeエナジープログラミングコンテスト C - MAD TEAM

問題はこちら

問題概要

{N}人に{A,B,C,D,E}{5}つの能力値がある.この中から3人選んだときの{\min{(\max{A},\max{B},\max{C},\max{D},\max{E})}}の最大値を求めよ.

{2\leq N \leq 3000\\
1\leq A_i,B_i,C_i,D_i,E_i\leq 10^9}

解説

最初に思いつくのは{3}人の選び方の全探索.これは{O(N^3)}なので間に合わない.

{2}人決めたときにもう{1}人を高速に決められたら解けそう.

決めた{2}人を{i,j}とすると,今のチーム総合力({S})は
{S=\min{(\max{(A_i,A_j)},\max{(B_i,B_j)},\max{(C_i,C_j)},\max{(D_i,D_j)},\max{(E_i,E_j)})}}であり,{\max{(X_i,X_j)}=S}となる{X\in\{A,B,C,D,E\}}が存在する.

(説明分かりづらいので追記します 05/02/05:00頃)
この{X}が総合力のネックになっているため,あと一人追加して{\max X}をできるだけ大きくしたい.({X}以外が大きい人をチームに入れても{X}が小さいままなので無駄)
(ここまで追記)

なので,{X}が一番大きい値をもつ人を選べばよさそう.ちゃんと実装すれば{O(N^2)}

たぶんこの解法は要素が{5}つだからできるけど,{6}つ以上だとできない?(知らんけど)
(本当っぽい)


提出プログラム

https://atcoder.jp/contests/zone2021/submissions/22237266

感想