A問題 お茶
1 2 3 4 5 |
a,b = map(int,input().split()) if b%a==0: print(b//a) else: print(b//a+1) |
C問題 座圧
方針
座標圧縮を用います。
座標圧縮とは、大小関係はそのままに不要なデータを取り除くことでデータの数を減らす操作です。
手順は次の通りです。
- ソートする
- 重複を排除する(setを用いる)
- 新しく順番をつける(辞書(dict型)を用いる)
■1例目:[3,1,6,7,2,4,2,1,5]
座標圧縮すると以下の通りになります。
1.ソート:[1,1,2,2,3,4,5,6,7]
2.重複を排除:[1,2,3,4,5,6,7]
3.新しく順番をつける:[1:0, 2:1, 3:2, 4:3, 5:4, 6:5, 7:6]
■2例目:[5,9,10,4,4,9,2]
座標圧縮すると以下の通りになります。
1.ソート:[2,4,4,5,9,9,10]
2.重複を排除:[2,4,5,9,10]
3.新しく順番をつける:[2:0, 4:1, 5:2, 9:3, 10:4]
解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
n = int(input()) A = [] for i in range(n): A.append(int(input())) B = sorted(list(set(A))) #[1]setで重複排除、sortedでソート #dict = {v:i for i,v in enumerate(A)} #次の3行の代わりに上記1行でも良い dict = {} for i in range(len(B)): dict[B[i]]=i #[2]ソート・重複排除を行った後のリストに対して、新たに順番をつける for i in A: print(dict[i]) #[3]入力値のリストAの各要素に新しく加えた順番を出力 |
[1]ここで、手順の1と2を行っています。
set(A)で重複を排除しています。set型という別の型になります。
list(set(A))で再度リスト型に戻しています。
sorted(list(set(A)))でリスト型に戻したAをソートしています。
[2]重複排除・ソートを行った後のリストに新しく順番をつけています。
辞書(dict型)は、キーと値がセットになっています。
※dict = {キー1:値1,キー2:値2,キー3:値3}
手順1,2を行った後のリストB=[1,3,6]だとすると、
dict={1:0, 3:1, 6:2}という具合で辞書を作成しています。
つまり、リストBの各要素をキーに、0,1,2を新しい順番として値に設定しました。
作成したdictでは下から何番目に大きいかを示すために、番号が0から振りなおされています。
このdictを元の入力値(リストA)と比較した時に、その大小関係がわかります。
元の入力値:[3,3,1,6,1]、dict:{1:0, 3:1, 6:2}
元の入力値の大小関係(下から何番目に大きいか)
→[3:1, 3:1, 1:0, 6:2, 1:0]
ちなみに、キーと値は逆に付けることもできます。
キーを指定して値を出力するのは簡単ですが、値を元にキーを出力するのは少し面倒なので、今回はこのような形にしました。
[3]キーを指定して値を出力するには、”dict[キー]”とすれば良いです。
問題は入力された各値の大小関係(下から何番目に大きいか)を出力する指示を出しているので、リストAの各要素を辞書(dict)のキーとして指定し、その値を出力しています。
類題
座標圧縮の類題はこちら。カテゴリからも確認できます。
コメント