ABC113 C - ID

備忘録

問題

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
MAX = float('inf')


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

    N, M = il()
    PY = [il() for _ in range(M)]
    k = {}
    sortPY = sorted(PY, key=lambda x: (x[0], x[1]))

    tmp = 0
    cnt = 1
    for p, y in sortPY:
        if p != tmp:
            cnt = 1
            tmp = p
        else:
            cnt += 1

        k[y] = cnt

    for p, y in PY:
        print(str(p).zfill(6) + str(k[y]).zfill(6))


if __name__ == '__main__':
    main()

考え方

各市の誕生した年(Y)が各市(P)の中で何番目かを求める。

PとYでソートした配列に対して、
YがPの中で何番目であるかを判定する。
また判定した情報をYをkeyにした辞書型で保持しておく。
（条件からYは常に一意）

あとはソートする前のPとYを順に、
PとYをkeyにしたvalueのゼロ埋めを出力することで回答。