4bitにっき

ぽよ

【うぃんじー Advent Calendar 2016】部内JOI予選対策コンテスト6問目

www.adventar.org
この記事はうぃんじーAdventCalendarの8日目の記事として書かれています

6日目の記事で言っていた、作問を担当した6問目の問題の解説です。

問題文

めっちゃ金魚

(この問題はフィクションです.)
(一部グロテスクな表現があります.)
今日はごちそうである.
tera君がおいしい金魚を$M$匹も取ってきたのだ.
これをtera君以外のN人で食べようと思う.
金魚にも色々あり, i匹目の金魚は柔らかさがS_{i}である.
i人目の人は柔らかさL_{i}の金魚が最も好きなため, 柔らかさS_{i}の金魚を食べたときの悲しみは|L_{i}-S_{i}| である.
1人1匹の金魚を食べ, 余った金魚はtera君が全ておいしく食べてくれる.
それぞれの人が食べる金魚を決め, tera君以外の人々の悲しみの総和を最小化し、最小値を求めよ.

入力

N \ M
L_{1}
...
L_{N}
S_{1}
...
S_{M}

出力

tera君以外の悲しみの総和の最小値を1行に出力せよ.

制約

2 \leq N+1 \leq M \leq 10^3
0 \leq L_{I},S_{I} \leq 10^9

解法

数直線的なものを書いて絶対値を可視化すると多分分かり易いが、人がL[i]についての昇順になっているとして、人々が選んだ金魚順にS[i]を並べた列をTとすると、Tは明らかに単調増加になっているべきである。
もう少し厳密には、Lが単調増加なのにT[i] > T[i+1]だとすると、T[i]とT[i+1]を入れ替えることで必ず悲しみが小さくなることから確認できる。
これで解が随分絞れたので、まずLとSを昇順に並べて、
dp[i][j] = Lをiまで、Sをjまで使ってうまくマッチングした時の悲しみの最小値
dp[i][j] = min(dp[i-1][j-1]+|L_{i}-S_{j}|, \ dp[i][j-1])
という感じのDPをするとO(NM)で間に合う。

感想

コンテスト途中までN=10^5, M=10^5としてしまうミスがあって、誰も解けない問題になっていた。(この場でも謝罪しておきます)
それは置いといて、コンテスト中誰も手を出さないので解かれないのかなーと思っていたが、ふなちさんがコンテストの最後辺りで突然通して簡単だったとか言っていたので地頭が強いと思った。(こなみ)
ちなみにこの問題、らて君に読ませたら見たことがあると言われたが、部員は誰も知らないだろうとのことだったので採用した。