Problem:


J - 刺身

  
問題文

きつねのしえるは川で釣りをしていた．黒くて細長い魚を手に入れることができたので，その場で切り刻んで刺身にして食べることにした．

魚は体長が N センチメートルある．奇妙なことに，この魚は身体の部分ごとに密度が異なっていた．
魚の身体を頭から 1 センチメートルごとに区切って番号を 1, 2, ..., N と付けるとき，身体の i 番目の部分の重みは w_i であった．
魚の i 番目から j 番目までの部分を [i..j] と表すことにする．
最初，しえるは魚の身体 [0..N-1] を 1 枚だけ持っていると見なせる．しえるはこれを切っていき最終的に N 個に分割された魚の身体 [0..0], [1..1], ..., [N-1..N-1] を得たい．

しえるは今野外におり，まな板などを持っていないので，次のようなアクロバティックな方法で魚の身体を切っていくことにした ： まず，魚の身体を 1 枚取る．これを [i..j] とする．この魚の身体は長さが少なくとも 2 センチメートル以上でなければならない．すなわち， j-i ≥ 1 でなければならない．次に，それを空中に投げる．そして日本刀を手に持ち，宙に舞う魚を真っ二つに切る．このとき，しえるは強靭な運動神経によって任意の位置でこの魚を切ることができるが，必ず 1 センチメートル区切りの位置で切るものとする．これにより，元の魚の身体 [i..j] を，任意の切断位置 k (i ≤ k < j) によって，[i..k] と [k+1..j] の 2 つに分割するのである．
このアクロバティックな方法で魚の身体を 2 つに切るとき，元の身体の重さ (=wi+wi+1+...+wj) だけコストがかかる．

しえるは，魚のすべての部分を 1 センチメートル区切りに切るのにかかるコストの合計値を最小にしたい．

入力形式

入力は以下の形式で与えられる．

N
w1 w2 ... wN

N は魚の体長である．wi は魚の i 番目の部分の重さである．

出力形式

魚を N 個に切り分けるのにかかるコストの合計の最小値を出力せよ．

制約

  
2 ≤ N ≤ 4,000

  
1 ≤ wi ≤ 1010

  
入力値はすべて整数である．

  
この問題の判定には，3 点分のテストケースのグループが設定されている． このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす．

  
1 ≤ N ≤ 100

入出力例

入力例 1

3
1 2 3

出力例 1

9

まず，魚全体を 2 番目と 3 番目の部分の間で切る．これには 1+2+3 = 6 のコストがかかる．
次に，1 番目と 2 番目の部分の間で切る．これには 1+2=3 のコストがかかる．合計で 6+3=9 のコストがかかり，これが最善手である．

入力例 2

6
9876543210 9876543210 9876543210 9876543210 9876543210 9876543210

出力例 2

158024691360

入力例 3

10
127 131 137 139 149 151 157 163 167 173

出力例 3

5016

Writer: 楠本充
Tester: 花田裕一朗

Sample input:
3
1 2 3


Sample output:
9

Submission status: Accepted

Solution code:
def main():
    import heapq
    
    def root_find(i):
        if uni[i][0]==i:return i
        else:
            uni[i][0]=root_find(uni[i][0])
            return uni[i][0]
            
    def union(a,b,flag=0):
        i=root_find(a)
        j=root_find(b)
        if i!=j:
            if flag==0:
                if uni[i][1]>=uni[j][1]:
                    uni[j][0]=i
                    uni[i][1]=max(uni[i][1],uni[j][1]+1)
                else:
                    uni[i][0]=j
                    uni[j][1]=max(uni[i][1]+1,uni[j][1])
            else:
                uni[i][0]=j
                uni[j][1]=max(uni[i][1]+1,uni[j][1])
    
    def left_find(i,j,r):
        if j-i<2:
            if root_find(i)==r:
                return i
            else:
                if root_find(i+1)==r:
                    return i+1
                else:
                    return i+2
        else:
            k=(i+j)//2
            if root_find(k)==r:
                return left_find(i,k-1,r)
            else:
                return left_find(k,j,r)
    
    def right_find(i,j,r):
        if j-i<2:
            if root_find(j)==r:
                return j
            else:
                if root_find(j-1)==r:
                    return j-1
                else:
                    return j-2
        else:
            k=(i+j)//2
            if root_find(k)==r:
                return right_find(k,j,r)
            else:
                return right_find(i,k-1,r)

    n=int(input())
    w=list(map(int,input().split()))
    
    uni=[[i,0] for i in range(n)]
    d=dict()
    ans=0
    merge_s=set()
    h=[[j,i] for i,j in enumerate(w)]
    heapq.heapify(h)

    while h:
        i,j=heapq.heappop(h)
        r=root_find(j)
        left=left_find(0,j,r)
        right=right_find(j,n-1,r)

        #同じツリー内の結合の場合
        if r in d.keys():
            ans+=d[r]+i
            heapq.heappush(h,[d[r]+i,r])
            del d[r]
            continue

        #どこと結合するか考える、4種類ある
        left_key1,right_key1=-1,-1
        left_key2,right_key2=-1,-1
        left_val1,right_val1=-1,-1
        left_val2,right_val2=-1,-1
        memory_right,memory_left=True,True
        if left!=0:
            rl=root_find(left-1)
            if rl in d.keys():
                left_key1=rl
                left_val1=d[left_key1]
            if rl in merge_s:
                left2=left_find(0,rl,rl)
                if left2!=0:
                    rl2=root_find(left2-1)
                    if rl2 in d.keys():
                        left_key2=rl2
                        left_val2=d[left_key2]
                
        if right!=n-1:
            rr=root_find(right+1)
            if rr in d.keys():
                right_key1=rr
                right_val1=d[right_key1]
            if rr in merge_s:
                right2=right_find(rr,n-1,rr)
                if right2!=n-1:
                    rr2=root_find(right2+1)
                    if rr2 in d.keys():
                        right_key2=rr2
                        right_val2=d[right_key2]
    
        #左で場合分け
        if left_key1==left_key2==-1:
            memory_left=False
            left_key=-1
            left_val=-1
        elif left_key1==-1:
            left_key=left_key2
            left_val=left_val2
        elif left_key2==-1:
            left_key=left_key1
            left_val=left_val1
        else:
            if left_val1>left_val2:
                left_key=left_key2
                left_val=left_val2
            else:
                left_key=left_key1
                left_val=left_val1
    
        #右で場合分け
        if right_key1==right_key2==-1:
            memory_right=False
            right_key=-1
            right_val=-1
        elif right_key1==-1:
            right_key=right_key2
            right_val=right_val2
        elif right_key2==-1:
            right_key=right_key1
            right_val=right_val1
        else:
            if right_val1>right_val2:
                right_key=right_key2
                right_val=right_val2
            else:
                right_key=right_key1
                right_val=right_val1
        
        #左右を併合
        
        #ない場合
        if memory_right==False and memory_left==False:
            d[r]=i
            continue
        #ある場合    
        #別のツリー間での結合
        elif memory_right==False:
            key=left_key
            val=left_val
        elif memory_left==False:
            key=right_key
            val=right_val
        else:
            if right_val>left_val:
                key=left_key
                val=left_val
            else:
                key=right_key
                val=right_val
    
        del d[key]
        #マージする
        r=root_find(r)
        left=left_find(0,r,r)
        right=right_find(r,n-1,r)
        union(r,key)
        r=root_find(r)
        merge_s.add(r)
        
        if left!=0:
            if root_find(left-1) in merge_s:
                union(r,left-1,1)
                    
        if right!=n-1:
            temp=root_find(right+1)
            if temp in merge_s:
                if temp in d.keys():
                    union(r,right+1,1)
                else:
                    union(right+1,r,1)
                    
        r=root_find(r)
        left=left_find(0,r,r)
        right=right_find(r,n-1,r)
        
        if left!=0:
            temp=root_find(left-1)
            if temp in merge_s:
                if temp in d.keys():
                    union(r,left-1,1)
                else:
                    union(left-1,r,1)
                    
        if right!=n-1:
            temp=root_find(right+1)
            if temp in merge_s:
                if temp in d.keys():
                    union(r,right+1,1)
                else:
                    union(right+1,r,1)
    
        ans+=val+i
        heapq.heappush(h,[val+i,r])
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
fin = sys.stdin.readline
from random import randint
from heapq import heappush, heappop


class Node(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None


# Meldable Heap implementation
def merge(h1, h2):
    if h1 is None:
        return h2
    if h2 is None:
        return h1
    if h2.val < h1.val:
        h1, h2 = h2, h1
    if randint(0, 1):
        h1.left = merge(h1.left, h2)
        h1.left.parent = h1
    else:
        h1.right = merge(h1.right, h2)
        h1.right.parent = h1
    return h1


def push(root, x):
    u = Node(x)
    root = merge(u, root)
    root.parent = None
    return root


def pop(root):
    x = root.val
    root = merge(root.left, root.right)
    if root is not None:
        root.parent = None
    return x, root


def find_min(root):
    return root.val if root else float('inf')


def find_second_min(root):
    return min(find_min(root.left), find_min(root.right)) if root else float('inf')


INF = 2**64 - 1
N = int(fin())
w_list = [int(elem) for elem in fin().split()]

hpq = [0] * (N + 1)
mpq = []
rig = [0] * (N + 1)
cst = [0] * (N + 1)
lef = [0] * (N + 1)

for i in range(N - 1):
    hpq[i] = None
    rig[i] = i + 1
    lef[i] = i - 1
    cst[i] = w_list[i] + w_list[i + 1]
    heappush(mpq, (cst[i], i))

ans = 0
for k in range(N - 1):
    c, i = heappop(mpq)
    while rig[i] == -1 or cst[i] != c:
        c, i = heappop(mpq)
    
    ml = mr = False
    if w_list[i] + find_min(hpq[i]) == c:
        _, hpq[i] = pop(hpq[i])
        ml = True
    elif w_list[i] + w_list[rig[i]] == c:
        ml = mr = True
    elif find_min(hpq[i]) + find_second_min(hpq[i]) == c:
        _, hpq[i] = pop(pop(hpq[i])[1])
    else:
        _, hpq[i] = pop(hpq[i])
        mr = True
    
    ans += c
    hpq[i] = push(hpq[i], c)
    if ml:
        w_list[i] = INF
    if mr:
        w_list[rig[i]] = INF
    if ml and i > 0:
        j = lef[i]
        hpq[j] = merge(hpq[j], hpq[i])
        rig[j] = rig[i]
        rig[i] = -1
        lef[rig[j]] = j
        i = j
    if mr and rig[i] + 1 < N:
        j = rig[i]
        hpq[i] = merge(hpq[i], hpq[j])
        rig[i] = rig[j]
        rig[j] = -1
        lef[rig[i]] = i
    cst[i] = w_list[i] + w_list[rig[i]]
    cst[i] = min(cst[i], min(w_list[i], w_list[rig[i]]) + find_min(hpq[i]))
    cst[i] = min(cst[i], find_min(hpq[i]) + find_second_min(hpq[i]))
    heappush(mpq, (cst[i], i))

print(ans)