yukicoder No.919 You Are A Project Manager のテスターをしました
初めてyukicoderのテスターをしました。
問題: https://yukicoder.me/problems/no/919
やったこと
- 問題を解く
- 「愚直にやると になってTLEしますね」
- 「想定解は より低いです」
- 「まじで」
- 数時間睨むと解法が生える
- 1secくらいで通る
- writer解と解法もorderも違うことが判明する
large2_4.txt, large2_5.txtを追加する
- large2_4.txt: (奇数) のときに最大値となるケース
- large2_5.txt: (偶数) のときに最大値となるケース
writer解がTLEする (multiset::countのオーダー問題)
- (前日夜に) Javaでもなんとか通ることを確認する (2.8sec)
- は整数という制約を入れる (忘れてた)
- と だけ調べればACすることがわかったため、急遽テストケースを追加 (large2_6.txt, large2_7.txt)
- 当日夕方にJava解がgeneratorによるテストケースに落とされる
- JavaのPriorityQueue#eraseが線形であると気づく
- それでも3秒切ってるしもう時間ないしまぁいいか
自分の解法
愚直解:
まずは、要素数に対して で要素を追加および中央値の取得ができるデータ構造が必要となります。これは、C++のstd::priority_queueやstd::multisetを2個使うことでできます。RBST(Randomized Binary Search Tree)のようなデータ構造で殴っても大丈夫です。このようなデータ構造があれば、 で左右から区間中央値の累積和の最大値を取っていくことで で解けますが、TLに間に合いません。
Tester解:
たとえば、 と の場合を考えてみましょう。すると、 が大きい場合は上記のようなデータ構造を毎回作り直すよりもスライドさせたほうが計算量が小さくなりそうです。スライドするためには で要素を削除する必要があり、これはstd::priority_queueではできないですがstd::multisetだとできます。 から にスライドさせる場合、データ構造の数を とおくと要素追加および削除の計算量は になります。ここで、 は愚直解の方法で、はスライドさせて解くと、前半部分の計算量は、後半部分も よりとなり、 でもぎりぎり間に合います。
また、この問題では中央値の取得でしたが、k番目の値を取得するためのデータ構造については以下の記事にまとまっています。 qiita.com
(追記)
コンテストの提出を見ていたらWavelet Matrixでより高速に解けることがわかりました。勉強になる。