読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

2016 TCO Algorithm Medium. EllysSocks

問題文

数列 a が与えられ、P 個の独立したペアを作る。

できるだけ絶対値の最大値が小さくなるようにペアを構成したとき、差の絶対値の最大値はいくつになるだろうか。

解法

数列の並びは関係ないのでソートしておこう。このようにすると、隣接する要素同士だけをペアにすればよくなる。

なぜなら、次のようなペアは改善できるし、

f:id:pekempey:20160327172339p:plain:w450

次のようなペアも改善できるからである。

f:id:pekempey:20160327172346p:plain:w400

これで問題が簡単になった。この問題は大きく分けて、

の 2 つがあるので、それぞれ説明する。

動的計画法による解法

  • dp[i][j] := i-1 番目までを使って j 個のペアを作るときの「差の絶対値の最大値」の最小値

という DP テーブルを考えればいい。遷移パターンは、

  • i 番目と i+1 番目をペアにする
  • i 番目は使わない

という 2 通り。それぞれをコードで表せば次の通り。

dp[i+2][j+1] = max(dp[i+2][j+1], max(dp[i][j], a[i+1]-a[i]))
dp[i+1][j] = max(dp[i+1][j], dp[i][j])

最終的な答えは dp[n][P] となる。

2016 TCO Algorithm Medium. EllysSocks DP 解

二分探索による解法

「差の最大値を x 以下としたとき P 個のペアを作れるか」で二分探索する。

i 番目と i+1 番目の差が x 以下ならペアにするという処理を i=0 から n-1 まで行い、最終的にできるペアの数が P より多ければ可能と判定できる。

貪欲がうまくいく理由
差が x 以下の隣接要素を辺で繋いでグラフを作ってみると次のようになる。

f:id:pekempey:20160327175941p:plain

同じ色の要素だけを見れば、左から貪欲にペア組すればペア数が最大になることが分かる。

2016 TCO Algorithm Medium. EllysSocks 二分探索解

素直な問題だった。