ABC 128 D - equeue 緑コーダーですが何か？その２

しいだよ緑だよ、緑コーダーですが何か？第2回目だよ。すごい！素数回まで続けれるとはおもってなかったから感動だよ。。。しかも素数唯一の偶数の素数。これは記念回だ。。。（）

問題

ABC 128 D - equeue

https://atcoder.jp/contests/abc128/tasks/abc128_d

問題分からしてあれだね。これ何回も解いてるけどいつも実装汚くなる。特に後ろからリスト取るのとかほんとに添字管理が複雑になっちゃうのがネック。一度まとめないと。。！

解法

今回の問題で大事なことは１つ

”入れ直す作業は最後にまとめてやってもええやんか”

そうです、これです。途中にやっても最後にやっても同じならまとめてやっちゃいましょう。

基本的な方針は

T個取り出す。（TはK以下の変数）
K-Tしてみてまだ操作が残っていたらできるだけ負の値の宝石を返す。

負の宝石はあるだけ邪魔なのでできるだけ戻したいっすね。逆に正の宝石は個数制限がないのであればあるほどありがたい。

2.のやり方は色々あって、

ソートして残り操作回数分pop()する
heapqに入れてheappoq
にぶたんぷにぷに

1.が一番簡単かな、わたしは最初２思いついたけど１のほうが記述量少ないし両方書いとくね

実装１

    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    m = min(N,K) #KがNより大きい場合を防ぐ
    M = 0 
    for i in range(m+1):
        for j in range(m-i+1):
            A1 = A[:i] #前から取る
            A3 = A[N-j:] #後ろから取る
            new_A = A1+A3
            new_A.sort(reverse=True)
            h = K - len(new_A)
            while h >0 and new_A:
                if new_A[-1] > 0:
                    break
                else:
                    new_A.pop()
                    h-=1
            M = max(M,sum(new_A))
    print(M)

実装２(heapqを使ったもの)

    import heapq 
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    m = min(N,K) #KがNより大きい場合を防ぐ
    M = 0 
    for i in range(m+1):
        for j in range(m-i+1):
            A1 = A[:i] #前から取る
            A3 = A[N-j:] #後ろから取る
            new_A = A1+A3
            heapq.heapify(new_A)
            h = K - len(new_A)
            while new_A  and h >0:
                q = heapq.heappop(new_A)
                h-=1
                if q > 0:
                    heapq.heappush(new_A,q)
                    break
            M = max(M,sum(new_A))
    print(M)

あとがき

途中で性の宝石とかいうパワーワード誤変換で出てきてた、新しい正確のほめことばかな？（ぴゅあ）