伯準2517号競走(分割征服)

アルゴリズムタイプ:分割征服
一人で解けたの?O...
問題自体はそんなに複雑ではなく、一度に理解できる問題ですが、なぜか一日中つかんでいる問題が・・・(まずmerge sortを実現すること自体がHelで、いいえ、概念はすべて知っていて、人類)おかげで、頭が落ちて、本当に疲れて、この問題を解く時、私は後で伯俊を解く時どのように解くべきかを意識しました.
いくら長くても一度に1つの問題を3時間以上捕まえてはいけない.1時間に3回、1回に3回見たほうがいいです.

変数またはリストの作成は避けないでください.これらの値を将来の表示のために保存する必要がある場合は、変数またはリストに保存します.

質問リンク:https://www.acmicpc.net/problem/2

問題を解く

これは分割征服によって接近する問題である.分割征服ではmerge sortを用いて,最初の与えられた配列を降順に並べ替えた.2、8、10、7、1、9、4、15が与えられると、15、10、9、8、7、4、2、1の順に並べ替えられていればよい.
分割征服は,大きさnの問題をn/xの分割段階とそれを再結合する統合段階に大別する.ここでの目的は最終的にソートではなく等号を求めることであるため、この等号はマージフェーズ、すなわちmerge sortにおけるmergeフェーズで発生する.
等級を更新する方法は簡単です.前のフェーズの自己インデックスと現在のフェーズの自己インデックスを比較した後、現在のフェーズのインデックスが前のフェーズのインデックスより大きい場合、差異が加算されます.今の段階でインデックスが増えています.つまり、私の前に誰かが入ってきたので、私のインデックスが大きくなりました.つまり、遅れています(降順でソートするように注意してください).インデックスは0から始まりますが、番号は1から始まるので、最後に出力するときはすべて+1を忘れないでください.
ここで重要な点は,相違を蓄積するプロセスを比較することにより,jインデックスの順序でのみ行うことである.(スライス征服はn個の配列から,前半iインデックス,後半jインデックス,ここではjインデックス)i,jはいずれも現在のレベルのインデックスがいくらであるか,前のレベルのインデックスがいくらであるかを記憶する必要があるが,この2つを比較して計算するとjのみである.iインデックスの前には誰もいないようなものがあるからです.2位は小数でも一番前に来ると前に人がいないので1位のようです.もしあなたが理解していないなら、自分で例を描いてもいいです.

例

3 1 2 4
順を追って走る.答えは1 2 1でしょう.
分割プロセス
3 1 2 4
3 1 | 2 4
3 | 1 | 2 | 4
連結プロセス
3|1|2|4の場合
間隔を基準にして、競走チームが分かれていることを考えてみましょう.今はみんな自分で走って、自分のインデックスはすべて0で、すべて1位です.
3 1|2 4の場合、->3 1|4の降順に並べます
ここでiインデックスの子は3,2,jインデックスの子は1,4である.したがって、1、4の更新のみを考慮する必要があります(もちろん、iの要素も現在のインデックスを記録する必要があります.次のステップでjに進むと、インデックスを比較することができるからです).
考えてみろ彼は前の段階で1位で、今は2位です.インデックスは0で、1です.その違いを保存してください.
2位も1位から2位に遅れていますが、彼はiなので差を更新する必要はありません
3 1 2 4時->4 3 2 1降順
jインデックス2,4を考慮するだけでよい.2の上位レベルのインデックスは1で、現在は2です.やはり違いが累積します.4は、前のレベルのインデックスが0であり、現在も0です.ずっと1位って言ってた更新は不要です.
ソートが終わりました.0、1、1、2、4の順で累計します.ここにもう一つ追加すると、私たちが要求した級数と一致します.

コード#コード#

n = int(input())
arr = [[0, 0, 0] for _ in range(n)] # 값, 현재등수, 원래 값 인덱스
for i in range(n):
    arr[i][0] = int(input()) 
    arr[i][2] = i
temp = [[0, 0, 0] for _ in range(n)] 
rank = [0 for i in range(n)] # 누적 등수 

print(arr)
def div(l, r):

    if(l < r): 
        m = (l + r) // 2 
        div(l, m)
        div(m+1, r) 
        
        combine(l, m, m+1, r) # 0 3 4 7 

def combine(l, m, s, r):

    i = l
    j = s
    k = l # 여기 조심
    cnt = 0                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       
 
   
    while (i <= m and j <= r): 
        if (arr[i][0] > arr[j][0]):
            temp[k] = arr[i]                                                                                                            
            arr[i][1] = cnt
            i = i + 1
            
        else: # j 갱신하는 부분만 확인
            temp[k] = arr[j]                                                                                                                                        
            if (arr[j][1] < cnt):
                rank[arr[j][2]] += cnt - arr[j][1] # 최종 rank 갱신
            arr[j][1] = cnt
            j = j + 1

        k = k+1
        cnt = cnt + 1

    if (i == m+1):
        for rest in range(j, r+1): # j 갱신하는 부분만 확인
            temp[k] = arr[rest] 
            if (arr[rest][1] < cnt):
                rank[arr[rest][2]] += cnt - arr[rest][1]
            arr[rest][1] = cnt
            k =  k + 1
            cnt = cnt + 1

    elif (j == r+1): 
        for rest in range(i, m+1):
            temp[k] = arr[rest]
            arr[rest][1] = cnt
            k =  k + 1
            cnt = cnt + 1

    for idx in range(l ,r+1):
        arr[idx] = temp[idx]
    
div(0, n-1)

for i in range(n):
    print(rank[i]+1)

arr配列には3つの値が格納されます.[初期入力値、現在の値のインデックス、値の元のインデックス]の順に格納します.値の元のインデックスは、入力順に出力する必要があります.現在の値のインデックスには、インデックス情報が含まれています.rankという名前の配列では、差異を計算することによって蓄積された値が格納されます.
これは、値のインデックスと前のステップのインデックス値を別々に格納することを考慮していないため、非常に困難な問題です.引き続き理解する必要があるデータがあれば、すぐに変数や配列を作成して格納することを考慮します.