ARC101-D「Median of Medians」

シェアする

  • このエントリーをはてなブックマークに追加

「先輩、何見てるんですか?」

「ちょっと見かけた問題を考えてるんだけど解けなくて。この問題解いたことある?」

「えっと、『Median of Medians』、ですか。その回は出てなかったみたいです。その問題がどうかしたんですか?」

「この問題が、黄色コーダーの半分ぐらいが解ける*って言われてたから気になって。僕も考えて見たけど、とっかかりが分からないんだよね」

「じゃあ考えてみましょうか。」

* AtCoder(競技プログラミング)の色・ランクと実力評価、問題例 - chokudaiのブログ

「与えられた配列の、全ての連続する部分列について中央値を計算して、その中央値たちのさらに中央値が何になるか、ですか」

「元の配列が {10, 30, 20} なら、{10}, {30}, {20}, {10, 30}, {30, 20}, {10, 30, 20} の全部について中央値を計算するんだね。{10, 20} は連続していないから関係ないね」

「そうですね。中央値がそれぞれ 10, 30, 20, 30, 30, 30 になりますね。偶数個の場合、真ん中2つのうちの大きい方にすることに注意です。だから {10, 30} の中央値が 30 に」

「それで、中央値たちの中央値が今回は 30 になるんだね」

「はい。もちろん愚直に計算すると間に合わないですよね」

「部分列が N*(N+1)/2 個あって、中央値の計算がソートするなら O(NlogN) とかだから、O(N^3*logN) とかになるのか。N≦10^5 だから、到底間に合わないね」

「うーん、とりあえず中央値の定石を使ってみたいですね」

「中央値の定石?」

「中央値を『小さい方から M/2+1 番目』のように考えるのは、競プロでは筋が悪い場合が多いです」

「じゃあどう考えるの?」

『中央値が k 以下である』『 k 以下の数が M/2 個より多い』が同値であることを利用します。M は配列の長さです」

「えっと、確かに同値みたいだね。中央値が k 以下ってことは k 以下の数が半分より多くあるってことだし、 k 以下の数が半分より多かったら、ソートして真ん中の数は k 以下になるね」

「さらに、真の中央値は、この条件を満たす k の中で最小の数になります」

「中央値が k 以下で、かつ k-1 以下ではないってことだね」

「そうすると、二分探索が使えます」

「確かに。OK=とても大きい数, NG=0 とかにしておいて、OK-NG=1 になるまで二分探索で狭めたときの、OKの値が中央値だね」

「中央値の問題では、この考え方をベースにすると見通しが良くなる場合が多いです。」

「なるほど、勉強になるね」

「さて、今回の問題について考えましょう。全ての連続部分列の中央値のうち、k 以下の値がいくつあるのかが計算できれば良いです」

「つまり、『中央値が k 以下になるような連続部分列はいくつありますか』という問題に答えられたらいいんだね」

「はい。さらに、部分列の中央値についてもさっきの考え方を利用します」

今注目する部分列に含まれる k 以下の数の個数を数えれば良いんだね」

「区間についてカウントするので、累積和を使いましょう」

k 以下の値を 1、k より大きい値を 0 にした数列を用意して、累積和を計算すれば、引き算だけでカウントできるってことだよね」

「そうですね。例えば、入力例2 の数列 {a_n}={5, 9, 5, 9, 8, 9, 3, 5, 4, 3} について、k=7 として考えましょう」

「この場合、{b_n}={1, 0, 1, 0, 0, 0, 1, 1, 1, 1} という数列を考えるんだね」

「例えば、最初から3つ取り出すと、和は 2 になります。つまり、最初の 3 つの中に 7 以下の数は 2 個あるということです」

「長さが 3 で、その半分の 1.5(切り捨てると1)より大きいから、最初の 3 つの中央値は 7 以下になるってことか。実際、{5, 9, 5} の中央値は 5 だね」

「はい。i 番目から j-1 番目まで(半開区間で [i, j) )の総和は、累積和の配列 {c_n} を考えたときに、c_j - c_i で表されますよね」

$$c_0=0$$

$$c_i=\sum_{n=0}^{i-1} b_n$$

とすると、

$$\sum_{n=i}^{j-1}b_n=c_j-c_i$$

「それが、長さの半分より大きくなればいいから、これが条件かな」

$$c_j-c_i>\frac{j-i}{2}$$

「そうですね。分母を払って移項して、i ごと、j ごとにまとめるとこうなります」

$$2c_i-i<2c_j-j$$

「きれいな式になったね」

「この 2c_i-i を、新たな配列 {d_n} とします」

$$d_i=2c_i-i$$

「なるほど、こうすると、『区間 [i, j) の部分列の中央値が k 以下』という条件がこれと同値になるんだね」

$$d_i<d_j$$

「入力例2 だと、{d_n} が {0, 1, 0, 1, 0, -1, -2, -1, 0, 1, 2} になるから、この条件を満たす (i, j) の組は、i=0 のとき 4 つ、i=1 のとき 1 つで…… えーっと、24通りか。これが、55/2=27.5 よりも大きくないから、中央値たちの中央値は 7 以下ではないんだね」

「はい。こうなると、もう解けたようなものですね」

「もう解けたの? えっと、『中央値が k 以下になる連続部分列の個数』が知りたいんだよね。今の言い換えでこれが『d_i < d_j を満たす i, j (i < j) の組の個数』になったのか」

「良い感じですよ」

「うーん、どこかで見たことあるような…… そうか、これは転倒数か!」

「その通りです! 不等号の向きが逆ですが、数列を反転させれば大丈夫ですね」

「そうだね。数列 {d_n} の順番を逆にすると、 d_i > d_j (i < j) を満たす i, j の組の個数になって、これはまさに転倒数だね」

「転倒数は BIT やセグメント木、もしくはマージソートで計算できますね」

「そうだね。調べたらたくさん出てくるね」

「この転倒数が『中央値が k 以下になる連続部分列の個数』ですね」

「その値が、連続部分列の個数の半分より多ければいいんだね」

「連続部分列の個数は N*(N+1) / 2 なので、条件は 転倒数 > N*(N+1)/4 ですね」

「そうだね。この条件が真なら、中央値たちの中央値が k 以下になるんだね」

「あとは二分探索をするだけですね」

「『中央値が k 以下になる連続部分列の個数』を count(a, k) としておいて、count(a, k) > N*(N+1)/4 かどうかで場合分けして二分探索すればいいんだね」

「ということで、コードはこんな感じですね」

中央値の性質を利用した言い換えか、これは覚えておくべきだね」

「中央値が絡む問題では結構使える考え方ですからね」

「この問題は、中央値の言い換えによって見通しが良くなる典型って感じだね。勉強になる」

解説PDFの方はもうちょっとスマートな考え方みたいですね。そっちも読んでみると勉強になりそうです」

「これが黄色コーダーの半分が解く問題かぁ。まだまだ勉強しないといけないことが多いなぁ」

「私も橙コーダーの半分が解く問題に挑戦してみたいです!」

「まだ僕には着いていけないだろうなぁ……」

スポンサーリンク
レクタングル(大)
レクタングル(大)

シェアする

  • このエントリーをはてなブックマークに追加

フォローする