ABC302Dを解いた

筆者はレート600前後の茶色コーダ

AtCoder ProblemsでRecommendationの中から選んだ以下の問題を解いていく

実装コード

解説みずにとりあえずしゃくとり法で行けそうと思い実行してみた結果。
WAやTLEのオンパレードで、うまく実行できなかった。

しゃくとり法を試したコード(TLE+WA)

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

def main():
    N, M, D = rLI()
    A = rLI()
    B = rLI()
    
    A.sort()
    B.sort()
    
    l = 0
    r = 0
    ans = -1
    for a in A:
        while l < M and abs(a - B[l]) > D:
            l += 1
        while r < M and abs(a - B[r]) <= D:
            r += 1
        if l == M:
            break
        for j in range(l,r):
            # err(a,B[j],a+B[j],abs(a - B[j]), ans)
            if a+B[j] > ans:
                ans = a+B[j]
    print(ans)
if __name__ == '__main__':
    main()

ここで解説を見てしまったが、
最大値を試して、条件を満たさない場合、大きい方を解から除外するような処理をすればよかったようだ。
最大値を出すにはソートして後ろから消せばいいと書いてあったが
折角なのでheapqを使った最大値の優先度付きキューを使用してみた。

import sys
import heapq
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

class Maxheapq:
    def __init__(self):
        self.q = []

    def push(self, v):
        heapq.heappush(self.q, v * -1)

    def pop(self):
        return heapq.heappop(self.q) * -1

    def get(self):
        return self.q[0] * -1

    def values(self):
        for _q in self.q:
            yield -_q

def main():
    N, M, D = rLI()
    A = rLI()
    B = rLI()
    
    Aq = Maxheapq()
    Bq = Maxheapq()
    
    for a in A:
        Aq.push(a)
    for b in B:
        Bq.push(b)
    
    if abs(Aq.get() - Bq.get()) <= D:
        print(Aq.get() + Bq.get())
        return    
    while True:
        if N==0 or M==0:
            print(-1)
            break
        a = Aq.get()
        b = Bq.get()
        if abs(a - b) <= D:
            print(a+b)
            break
        if a > b:
            Aq.pop()
            N -= 1
        else:
            Bq.pop()
            M -= 1
        
if __name__ == '__main__':
    main()

まとめ

ABC302Dを解いた、実装には最大値の取り出しを行い、それには優先度付きキューを使用した。

感想

適当に解法を選び、実装して駄目だったらすぐ解説を見てしまった。
他になにか実装方法がないか考える力が足りないからだと思うので、次から気を付けていきたい。