po

CSAcademy 10 D. Subarray Medians

問題

https://csacademy.com/contest/round-10/task/subarray-medians/

問題概要

与えられた数列に対して、全ての連続した部分列(奇数長)を考えl×r×([l, r]のmedian)の総和を求める。

方針

medianを更新しながら、l=1..N, r=l..Nとして部分列を全通り考えます。

要素がちょっとずつ増えたり、減ったりしたくらいでmedianは大きく変わらないだろうという気持ちを持ちます。すると、部分列に含まれる各要素に対して、自分の次に大きい要素・自分の次に小さい要素を覚えておけばよさそうです。つまり、部分列をソートしたときの各要素について、自分の右隣・左隣の要素を覚えておきます。

要素を追加するときの操作を考えるとmedianから順に辿っていくことになって、これは最悪(今の部分列の長さ/2)回くらい辿らなければいけません。そこで、要素を削除するほうを考えます。いま、削除したい要素の両隣の要素はわかっているので、削除したい要素をxとすると

  • xの右の左=xの左
  • xの左の右=xの右

と更新すれば良いと分かります(図を見て察してください)。

f:id:poyopoyoyon:20170806155626p:plain

部分列の長さが偶数のときは2つのmedianの候補のうち、小さいほうをmedianとします*1。つまり、1 2 3 4のmedianを2ということにします。要素を削除したあとmedianを更新するかどうかは、削除した要素とmedianとの大小・部分列の長さの偶奇によって適当に場合分けします。たとえば、長さ5でmedianが3の数列 1 2 3 4 5 から要素を削除すると

  • 1 or 2のとき・・・更新しない
  • 3のとき・・・med=4と更新する
  • 4 or 5のとき・・・med=2と更新する

のように場合分けできます。

解答例

CSAcademy Round #10: D.Subarray Medians

おわりに

はじめ解説のdoubly-linked listの意味が分からなかった。

CSAcademy、問題文が壮大な物語になったりしないので好きです。

*1:大きいほうとしてもいいです