【プログラミング】複数キー、異順ソート(AtCoder ABC128-B)

はじめに

目から鱗だったのでメモします。異順ソートという言葉はないと思いますが便宜上名付けました。

問題

市名 点数 が複数個渡されるので、市名は昇順、かつ同じ市名なら点数は降順にして、番号(渡された順に1から採番)を出力する。

atcoder.jp

ポイント

各キーで昇順/降順が異なるソートをどのようにおこなうか？

私の実装

以下の記事を参考に、優先度が低いものから2回ソートした。

qiita.com

atcoder.jp

n = int(input())
rs = [ [i+1, input().split()] for i in range(n) ]

rs = sorted(rs, key=lambda a:int(a[1][1]), reverse=True)
rs = sorted(rs, key=lambda a:a[1][0])

for r in rs:
    print(r[0])

解説によると

https://img.atcoder.jp/abc128/editorial.pdf

問題文に合うようにレストランを並べるには、C++ でいう pair 型を利用すると簡単に実装できます。具 体的には、pair<pair<string,int>,int> の配列を用意し、レストランの情報を格納します。

ここまでは自力で辿り着いた。

first.second (2 番目のソート基準) に int 型で点数の −1 倍を入れ (点数が高い順に並べたいので)、

本来なら点数は降順でソートしなければならないが、-1倍することで市名と同じ昇順に揃えられるようにしてソートを1回で済ませてしまう、ということ。この発想はなかった。

試してみた

かなりシンプルな実装になった。sorted()のkeyを使ってキーを指定することをしないので、pair内の値の順番も重要になる。

atcoder.jp

n = int(input())
rs = []
 
for i in range(n):
    s,p = input().split()
    p = int(p)
    rs.append([[s, -p], i+1])
 
for r in sorted(rs):
    print(r[1])

柔軟な発想。。