圧縮

問題

配列 $A=[A_1, A_2, … , A_N]$ が与えられます。

大小関係を崩さないように、配列をできるだけ圧縮してください。

ここでの圧縮とは、以下の条件を全て満たす配列 $B=[B_1, B_2, … , B_N]$ を求める操作です。

なお、このような配列 $B$ は1通りに決まります。

🔹条件１ $B_1,B_2, … , B_N$ は1以上の整数である。
🔹条件２ $A_i < A_j$ であるような組 $(i,j)$ については、$B_i<B_j$ である。
🔹条件３ $A_i = A_j$ であるような組 $(i,j)$ については、$B_i=B_j$ である。
🔹条件４ $A_i > A_j$ であるような組 $(i,j)$ については、$B_i>B_j$ である。
🔹条件５ 条件１～条件４を満たす中で、配列 $B$ の最大値をできるだけ小さくする。

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 1 \leqq A_i \leqq 10^9 $

解き方

この問題はソートして重複を消す方法で解くことができます。

手順は以下の通りです。

１．配列 $A$ を昇順にソートします。
２．ソート後の配列 $A$ について、重複を除いた配列 $C$ を作成します。
３．配列 $C$ の要素に対して、$C_i$ が元の配列 $A$ の何番目の要素であったかを示す配列 $P$ を作成します。
　　つまり、$A_{P_i} = C_i$ となるような配列 $P$ を作成します。
４．配列 $B$ を用意し、$B_i$ を $P_i$ 番目の要素とすることで、配列 $B$ を求めます。

この方法で求められる配列 $B$ も、与えられた条件を満たす圧縮された配列となります。

ソースコード

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#-------- 入力例１ ---------
N = 5                       # 整数の数
A = [46, 80, 11, 36, 46]    # 配列A
#---------------------------
import bisect

# 配列 T の作成（重複も消す）
T = list(set(A))
T.sort()

# 答えを求める
B = [None] * N
for i in range(N):
    B[i] = bisect.bisect_left(T, A[i])
    B[i] += 1

# 答え
print("解：", [str(i) for i in B])

このコードは、配列 $A$ をできるだけ圧縮するために、配列 $T$ を作成し、各要素に対応する圧縮された値を求めるものです。

まず、配列 $T$ を作成するために、set()関数を使い、重複を消した後、list()関数でリスト化しています。

その後、sort()メソッドを使い、要素を昇順に並べ替えています。

この $T$ 配列は、$A$ 配列を圧縮するための目印となるもので、条件２と３において、大小関係を崩さずに圧縮することができます。

次に、None で初期化した $B$ 配列を作成します。その後、for ループを用いて、配列 $A$ の各要素に対応する圧縮された値を求めます。

この圧縮された値は、配列 $T$ の中で、$A_i$ が何番目に小さいかを示しています。

bisect_left() 関数を使うことで、$A_i$ が $T$ 配列の中でどの位置にあるかを求めています。

bisect_left() 関数は、二分探索を行い、挿入するべきインデックスを返す関数です。

ここで、返される値は、$0$ から始まるため、$+1$ する必要があります。

最後に、$B$ 配列を表示して終了となります。

このコードは、時間計算量 $O(N \log N)$ で、与えられた条件を満たす圧縮された配列 $B$ を求めています。

[実行結果（入力例１）]

解： ['3', '4', '1', '2', '3']