ABC041 C - 背の順

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import string

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    ret = {}
    for i, v in enumerate(A):
        ret[v] = i + 1

    ret = sorted(ret.items(), key=lambda x: -x[0])
    for r in ret:
        print(r[1])


if __name__ == '__main__':
    main()

考え方

背の順Aから背の高さをkey、出席番号をindexとしたdictを作る。
その後、作ったdictに対して、keyで降順ソートを行い、
順にvalue(出席番号)を出力することで回答。

ちなみに、array.indexを使用するとTLEとなる。
Submission #12231284 - AtCoder Beginner Contest 041
これは、array.indexが内部的にforを行っているため、
計算量がO(N^2)となるため？