[テストエンコーディング]Unique Numbersリスト

ソース:https://www.acmicpc.net/problem/13144

釈義の前に言うこと

この問題は標準のGold 3に相当する.簡単ではないという意味ですよね?
まず問題を分析しようまず、メモリは32 MBに制限されており、提供された容量が不足していることがわかります.これは、この問題を解決する際に、変数の割り当てをできるだけ減らすことを意味します.ではDPの解が必要ですよね?
時間は1秒に制限され、数列長Nは100000に制限される.これはO(N^2)の複雑さを使用することができず,線形ナビゲーションが必要であるか,O(Nlogn)の複雑さで解決しなければならないことを意味する.
しかし、この問題は二重ポインタ技術で解決するのは骨が折れるように見えます.2つの針で解こうとしたが、結局1時間もかかった.これは秘密ではない.
二重ポインタで解くには、二分検索で重複する数字を見つける必要がありますが、問題は、解く状況が想像以上に多ければ、かなり増えるということです.
また、デュアルポインタを使用して解く方法にかかわらず、複雑さは自然に増加するため、失敗する確率が非常に高いです.

import sys

input = sys.stdin.readline

N = int(input())
number_list = list(map(int, input().split()))
checked = [False] * 100001 # 0부터 100000까지 숫자가 check 되었는지 검사하기 위한 리스트
count = 0

for i, number in enumerate(number_list):
    start, end = i + 1, N - 1
    mid = 0
    signal = False
    checked[number] = True
    
    while start <= end:
        mid = (start + end) // 2
        target_idx = 0
        
        for j in range(start, mid + 1):
            if checked[number_list[j]] == True:
                signal = True
                target_idx = j
                break
            else:
                checked[number_list[j]] = True
                
        # 탐색을 종료시킨다
        if signal == True:
            count += (j - i)
            checked = [False] * 100001
            break
        
        else:
            start = mid + 1 # 기존에 탐색하지 않았던 범위를 탐색하기 때문에 checked를 초기화하지 않는다
            
    # 겹치는 숫자들 찾지 못하는 경우
    if start > end:
        count += (N - i)
        checked = [False] * 100001
        
print(count)

上の問題は私がこの検索問題を利用して上のプールはO(Nlogn)の複雑さではなく、O(N 2 logn)O(N^2 logn)O(N 2 logn)の複雑さです.O(N 2)O(N^2)O(N 2)の複雑さは許されませんが、O(N 2 logn)O(N^2 logn)O(N 2 logn)O(N 2 logn)を使用した複雑さは、当然間違っているのでしょうか?
だから私は考えを変えた二つの針に縛られないように私の考えを説明します.

どうやって解いたの?

上の問題は線形探索で解決したと思います.解法は次のとおりです.
1-1. 前から数字を読み込みます.取得した数値がナビゲートされていない場合は、可能なため、シーケンスに追加します.
1-2. 検索されていない数値が追加された場合は、数列(シーケンス)に含まれる数値であるため、アクセスするタグが残ります.
2-1. 取得した数値は、これまでの数列の長さをcountに反映します.
2-2. 次に、次の数列の一番前の数字をポップアップします.また、popの数字は数列にないのでcheckedで解放されます.
上の答えは合理的だ.例を挙げて理由を説明します.
🌈 入力例

6
1 2 3 5 2 1

上のように入力してきました次に、次の手順に従います.
1.シーケンス[1,2,3,5]に保存され、シーケンス2に移動します.
2.2を探索してみると、2はすでにシーケンス中であることが分かった.したがってcountに4,pop 1を加える.
3.次に、2を検索し、2もシーケンスにすでに存在します.したがってcountは3,pop 2を加える.
4.今は2を追加できます.したがって、シーケンスに2を追加します.ここまでの順番は[3,5,2]です.
5.1シーケンスにないので、1を追加します.ナビゲーションを終了します.
6.今から時間を割いて処理します.
上記プロセスは,全O(N)O(N)O(N)O(N)複雑度を有する.
でもこんな疑問がある時間を割いて処理する過程で、複雑度が上昇するのではないでしょうか.一方,ギャップ処理過程はO(1)O(1)O(1)O(1)O(1)))複雑度を有する.ギャップ処理では、次の式が使用されます.
(1/2)n(n+1)(1/2)n(n+1)(1/2)n(n+1)
ギャップ処理結果の数列に重複する数字はないので,1から数列までの長さの総和をcountに加算すればよい.
今、私のコードを楽しんでください.

コードをお楽しみください。虚無かもしれない!

import sys

input = sys.stdin.readline

N = int(input())
number_list = list(map(int, input().split()))
checked = [False] * 100001 # 0부터 100000까지 숫자가 check 되었는지 검사하기 위한 리스트
count = 0

start, end = 0, N - 1
sequence = [] # 수열을 담을 리스트

while start <= end:
    # 기존에 check된 숫자인지 검사
    if checked[number_list[start]] == False:
        checked[number_list[start]] = True
        sequence.append(number_list[start])
        start += 1
    else:
        count += len(sequence) # 길이만큼 카운트 수 증가
        removed_number = sequence.pop(0) # 제일 앞의 숫자를 pop
        checked[removed_number] = False # checked 해제
        
# 마지막에 남은 sequence 짬처리
remained = len(sequence)
count += remained * (remained + 1) // 2

print(count)

数列に数字が含まれている場合はcheckedに情報を記録します.次にwhile文を迂回してcheckedに数字を表示させ、ナビゲートするインデックス(start)に数字がすでに存在するかどうかを確認します.
他のメカニズムは前述の通りである.
上記のコードにより,O(N)O(N)O(N)O(N)の複雑さで問題を解決した.