【Python】AtCoder Beginner Contest 036 A,C問題 解答・解説

この記事は約3分で読めます。

A問題 お茶

 

C問題 座圧

方針

座標圧縮を用います。

座標圧縮とは、大小関係はそのままに不要なデータを取り除くことでデータの数を減らす操作です。

手順は次の通りです。

  1. ソートする
  2. 重複を排除する(setを用いる)
  3. 新しく順番をつける(辞書(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]ここで、手順の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)のキーとして指定し、その値を出力しています。

 

類題

座標圧縮の類題はこちら。カテゴリからも確認できます。

AtCoder Beginner Contest213 A,B,C問題 解答・解説

コメント