「みんなのプロコン」本選 オープンコンテスト:B - チーム決め

問題

https://atcoder.jp/contests/yahoo-procon2017-final-open/tasks/yahoo_procon2017_final_b

考え方

差の最大値を最小化したい。これはよくある典型問題で、最小化したい値 x を二分探索することで最小値を求めることができる。問題を言い換えると

「差を x とするとき、\{A_N\}, \{B_N\} を用いてペアを K つ以上作ることができるかどうか判定し、この x の最小値を求めよ」となる。

x が決まれば、貪欲法で求めることができる。\{A_N\}, \{B_N\} はソートしておく。各 A_i について A_i - x 以上の最小の B_j とマッチングさせることが最善である。ただし B_j \gt A_i + x となる場合はマッチングできない。そのようにマッチングさせていったときにペアが K つ以上できるかどうか求めれば良い。

Submission #4277378 - 「みんなのプロコン」本選 オープンコンテスト

どこに着目して考察するべきだったか

最大値の最小化は二分探索で解けることは典型問題なので、ぱっと思いつけないといけない。

何がバグっていたか

得た知見(典型ポイント)

  • 最大値の最小化(最小値の最大化)

類題