AtCoder ABC155 メモ - 少ない学びをせめて記録する

ABCEを解きました。今回難しかったようでこれでも青パフォでした。

D Pairs

割とABC149EのHandshakeに近いです。今回はゼロとマイナスの要素があるので複雑度が大きくなっています。本番ではゼロを分けないといけないことに気づかず解けませんでした。終了後、他のバグにも気づいたのでどちらにしろ解けなかった可能性が高いです。

K以下のAi*Aj(i<j)の数をO(N)で数えることができれば二分探索でO(N*log(max(Ai+Aj)))でできます。次に数え方です。

i<jの条件を外して数えることにします。
配列Aの要素数をNとします。Aを正、ゼロ、負の要素に分けます。それぞれpA, zA, nAとします。またそれぞれ予めソートしているものとします。 pAi * pAj がK以下のものはpAiを固定してpAi*pAj<=Kとなるような境界のjを大きい方から探索すればいいです。i++すると次の境界jはさらに小さくなるので尺取り法で大丈夫です。 nAi * nAj についてはnAiを固定してnAjを小さい方から見ます。i--していきます。iの順もjの順も上と逆です。 pAi * nAj についてはiを小さい方、jも小さい方から見ていきます。nAi * pAj も同じ数になるはずなので2倍します。あとはゼロとなる数です。K<0の時は気にしなくていいです。K>=0の時はlen(zA) * N - len(zA)²の数がK以下の数です。

上記の和をとればいいです。そのあとAi * Ai <= K となる数を数えて引いて2で割ります。そうするとK以下の数になります。上の尺取のところ、上からなのか下からなのか迷いながらやっているのですが脳死でできるようになりたいです。

追記

ゼロは分ける必要がなかったです。。整理すると結構簡単な実装になりました。以下に貼っておきます。

N, K = map(int, input().split())
A = list(map(int, input().split()))
mA, nA = [], []
for a in A:
    if a < 0:
        mA.append(a)
    else:
        nA.append(a)
mA = sorted(mA)[::-1]
nA = sorted(nA)
lnA = len(nA)
lmA = len(mA)


def F(k):
    # k以下の数
    # positive positive
    r = 0
    i, j = 0, lnA-1
    while i < lnA:
        while j >= 0 and nA[j]*nA[i] > k:
            j -= 1
        r += j+1
        i += 1

    # negative negative
    i, j = 0, lmA-1
    while i < lmA:
        while j >= 0 and mA[j]*mA[i] > k:
            j -= 1
        r += j+1
        i += 1

    # positive negative
    i, j = 0, lmA-1
    while i < lnA:
        while j >= 0 and mA[j]*nA[i] <= k:
            j -= 1
        r += 2*(lmA-j-1)
        i += 1
    for a in A:
        if a*a <= k:
            r -= 1
    return r//2


mx, mn = 2*10**18, -2*10**18
idx = (mx+mn)//2
target = K
while mx - mn > 1:
    if F(idx) < target:
        mn = idx
    else:
        mx = idx
    idx = (mx+mn)//2
print(idx+1)

E Payment

貪欲で解こうとして30分くらい溶かしてdpで解きました。dp1とdp2は下からi桁見てぴったり払うのに必要な枚数と１つ上の桁のお金を1枚払うときのそれぞれの枚数を意味しています。更新式は以下です。（dp2 → dp2の更新が頭壊れそうになった。）

dp1[i+1] = min(dp1[i] + c, dp2[i] + c)
dp2[i+1] = min(dp1[i] + 11 - c, dp2[i] + 9 - c)

貪欲でも解けるらしい。解法を見て感心。要追記

F Perils in Parallel

まだ解いていないです。