人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

AtCoder Regular Contest 032 : D - アットコーダーモンスターズ

問題

D - アットコーダーモンスターズ

N 匹のモンスターには攻撃値と防御値がそれぞれ決まっていて,この中から K 匹選んでチームを作りたい.このチームの「不安定度」はチーム内のモンスター同士の攻撃値の差と防御値の差の min の max で定義される.この時,「不安定度」の最小値と,このときのモンスターの選び方の通り数を求める問題.

解法

攻撃値と防御値を二次元配列にプロットして考える.そうすれば,この問題は「二次元配列上で K 個点を含むような正方形の四方の長さの最小値とは?」に言い換えられる.これは,二分探索を用いて求められる.

この時の通り数は,この正方形の中にある点の選び方の総和になる.重複が生じる場合があるので注意.

解答

Submission #3219197 - AtCoder Regular Contest 032

f:id:babcs2035:20180918143634p:plain