sima(mu)*雑記

print(f"{雑多なこと}")

ARC101参加記

競プロ参加記

AtCoder Regular Contest 101 - AtCoder
2018-08-25(土) 21:00 ~ 2018-08-25(土) 22:40
f:id:awaawa4423:20180825230920p:plain
一完だったけどRated内236位，perf1887
配点的にCが0WA＆まあまあ早解きできたので許された感

C - Candles

ABC-095 D - Static Sushiの類題って感じ？(今回の方が簡単め)
・K本のろうそくの選び方は連続したk本以外ありえない
・移動する向きを変えるのは高々一回
ということを考えると，とりうる区間を全探索して高々N通りで，左端と右端の位置から移動距離はO(1)で求まるので間に合う．

見覚えのある問題だったので無駄に考察に時間かけずに解けたのは良かった

コンテスト中に通した駄コード
Submission #3073099 - AtCoder Regular Contest 101

D - Median of Medians

解けへんが？？？？？？？？？
なんか最初a列がソート済みだと思って余裕やんけって思ったけどそんなことはなかった
x以上の数とx以下の数とかちょっと考えてたけど二分探索は出てこんわ… 100分考えたけどN2解法しか浮かばなくて詰み
以下解説読んだうえでのほぼどeditionalまんまの自己満アウトプット

解答

最終的に部分列の中央値の全体の中央値を求めるという問題． ここで中央値の性質を考えると
xが長さMの列Aの中央値である⇔x以上の要素が列A中に半分以上(M+1//2個以上)含まれるものの中で最大の整数
なので，二分探索が有効(x以上の要素の数はxに関して広義単調減少なので，二分探索すれば最大のxが求まる)
終わった後中央値なので二分探索は典型って言われててそっかーってなった
つまり，今回の問題は以下の部分問題が解きたい

a[l,r]の中央値のうちx以上となるのは何個か．(l<=r)

ここでさらに先ほど中央値の性質を用いて言い換えると，

a[l,r]のうち，x以上の要素が半分以上となる(l,r)の組は何通りか．(l<=r)

ここまで言い換えるとaの要素はx以上か，x未満かということだけを見ればよいので，例えばx未満をA，x以上の数をBと置き換えると

a[l,r]のうち，{Aの数}<={Bの数}となる(l,r)の組は何通りか．(l<=r)

(Bではない数がAなので，Bの数が半分以上 ⇔ Aの数<=Bの数) さらにA=-1,B=+1としてしまえば，a[l,r]の総和に着目すると

sum( a[l,r] ) >= 0となる(l,r)の組は何通りか．(l<=r)

こう考えると連続部分列の総和という話ですが，これは端からの累積和でやると扱いやすい．sum( a[0,k] ) = S_kと書くと sum( a[l,r] ) = S_r - S_{l-1}のように簡単に計算できる．
これは頻出，最近だとD - Candy Distributionとか

S_r - S_{l-1} >= 0となる(l,r)の組は何通りか．(l<=r)

少しだけ見通しが悪いのでl'=l-1として言い換えると

S_r - S_l' >= 0 (S_l' <= S_r) となる(l',r)の組は何通りか．(l' < r)

となる．

これは数列Sの転倒数を求める問題とほぼ同じらしい(何それ…

転倒数を求める(クロッシング問題)

参考資料
inversion counting
転倒数を求めるのは愚直にバブルソート(O(N2))とか分割統治法(O(NlogN))とかあるらしいけど，今回は一番実装簡単そうで早そうなBIT(O(NlogN))を用いる．
今回求めるのは順列Sのある要素S_iから左を見た時にS_iより小さいものは何個あるか？という問題なので，左から順に探索していき今まで出てきた中でS_iより小さい値をカウントできればいい
->BITにS_iの値を順に追加していけばS_i以下の値はlogNで求められる．
(参考AtCoder Regular Contest 043 解説の29P～)

実装

中身

二分探索の中身であるx以上の要素の数のカウントの部分．

N = 10
aa = [5, 9, 5, 9, 8, 9, 3, 5, 4, 3]
x = 5
def calc(x):
    aa_dush = [-1]*N
    for i in range(N):
        if aa[i] >= x:
            aa_dush[i] = 1
    #aa_dush = [1, 1, 1, 1, 1, 1, -1, 1, -1, -1]

    S = [0] #S_0 = 0を忘れずにつける
    tmp = 0
    MIN = MAX = 0
    for i in range(N):
        tmp += aa_dush[i]
        MIN = min(tmp,MIN)
        MAX = max(tmp,MAX)
        S.append(tmp)
    #S = [0, 1, 2, 3, 4, 5, 6, 5, 6, 5, 4]
    #MIN = 0 , MAX = 6

    L = (MAX-MIN+1) #BITのサイズ L=7
    bit = [0]*(L+1) #1indexで扱うのでL+1の長さで取る
    ans = 0
    for S_i in S:
        S_i -= (MIN-1) #S_iの最小値が1となるように調整

        #BITで既出の要素のうちS_i以下の要素数をカウント
        tmp = 0
        x = S_i
        while x > 0:
            tmp += bit[x]
            x -= x & -x
        ans += tmp

        #BITのS_iに1を加算して更新
        x = S_i
        while x <= L:
            bit[x] += 1
            x += x & -x

    return ans #中央値がx以上となる(l,r)の組の数

自分がわかりやすいようにサンプル3でx=5とした時の具体的な結果をつけている．
aa_dushが列Aをx以上の値を1，x未満の値を-1としたもの．
Sがaa_dushの左端からの累積和を取ったもの(S_0=0をちゃんとつける)．
MINとMAXはそれぞれSの最小，最大値で， BITを扱うときは最小値を1にしておきたいが今回はSの要素が負になりうるのでS_i-=MIN-1として調整する．(大小関係だけ見るので全ての要素を同じ値で引いても問題はない)
またBITのサイズは最小値～最大値の範囲の長さLだけで作っておけばよい．(1indexで使いたいのでBITの配列はL+1で持つ)
これで無事に中央値がx以上となる(l,r)の組の数が返ってくる．

二分探索

上のcalc(x)を使って二分探索をする．
l<=rとなる(l,r)の取り方は(N+1)*N/2通りあるので，calc(x)とした時これの半分以上の値が返ってくるxの内最大値を求める．

border = ( (N+1)*N//2 ) //2+1
OK = 0
NG = 10**9+3

while NG - OK > 1:
    mid = (OK+NG)//2
    if calc(mid) >= border:
        OK = mid
    else:
        NG = mid

print(OK)

どっかで誰かのを見てパクった参考にしたけどOKとNGってするとわかりやすい

提出コード

Submission #3082640 - AtCoder Regular Contest 101
このコードだとPythonだとTLEで，PyPyで通りました(599ms)．(ちゃんとPythonで通してる人もいるので逃げ)
計算量はBITでの転倒数の計算がO(NlogN)で，二分探索がO(logA)なのでまあ間に合わなさそうとは思った．

感想

xを数えるよりx以上になるものを数える方が簡単になるっていうのは典型発想らしいです，特に中央値の問題だと． 一つずつ部分問題に分解していくと比較的簡単なものを組み合わせて解けるっていう問題解法聞くと感動する(解けんが)
ARC101としてはもう配点的にC早解きが目標だったのでそれは達成できたのは良かった (0WAで6:43) f:id:awaawa4423:20180826110554p:plain
水色になりましたわーい

E,Fはそのうち復習します…