ABC161 D - Lunlun Number

AtCoder Python3

備忘録

問題

atcoder.jp

回答

import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, 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()
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]


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

    K = ii()
    q = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    for k in range(0, K):
        x = q[k]
        mod = x % 10
        if mod != 0:
            q.append(10 * x + mod - 1)
        q.append(10 * x + mod)
        if mod != 9:
            q.append(10 * x + mod + 1)

    print(q[K-1])


if __name__ == '__main__':
    main()

考え方

1桁のルンルン数(1, 2, 3, 4, 5, 6, 7, 8, 9)については自明なので、2桁以降のルンルン数について考える。
2桁のルンルン数は10, 11, 12, 21, 22, 23, ... 98, 99となっており、
3桁のルンルン数について考えると、
100, 101, 110, 111, 112, 121, 122, 123, 210, 211, 212, 221, 222, 223, 232, 233, 234 ... 876, 877, 878, 887, 888, 889, 898, 899, 987, 988, 989, 998, 999
となる。

上記の各ルンルン数に注目すると、
ルンルン数の1桁目が1のとき、

  • ルンルン数を10倍し（1 * 10)、ルンルン数の一桁目(1 % 10)を加算し、一つ減算(-1)した値
    (1 * 10 + 1 % 10 - 1 = 10)

  • ルンルン数を10倍し（1 * 10)、ルンルン数の一桁目(1 % 10)を加算した値
    (1 * 10 + 1 % 10 = 11)

  • ルンルン数を10倍し（1 * 10)、ルンルン数の一桁目(1 % 10)を加算し、一つ加算(+1)した値
    (1 * 10 + 1 % 10 + 1 = 12)

が次の桁数のルンルン数になっている。

ルンルン数が11の場合

  • ルンルン数を10倍し（11 * 10)、ルンルン数の一桁目(11 % 10)を加算し、一つ減算(-1)した値
    (11 * 10 + 11 % 10 - 1 = 110)

  • ルンルン数を10倍し（1 * 10)、ルンルン数の一桁目(1 % 10)を加算した値
    (11 * 10 + 11 % 10 = 111)

  • ルンルン数を10倍し（1 * 10)、ルンルン数の一桁目(1 % 10)を加算し、一つ加算(+1)した値
    (11 * 10 + 11 % 10 + 1 = 112)

となるので、次の桁（3桁）のルンルン数は110, 111, 112とわかる。

注意が必要なのは、一桁目が9または0の場合。
一桁目が9のときは、一つ加算(+1)すると、桁数が変わってしまうので、行わない。
一桁目が0のときは、一つ減算(-1)すると、桁数が変わってしまうので、行わない。

ルンルン数が9の場合（一桁目が9のとき）

  • ルンルン数を10倍し（9 * 10)、ルンルン数の一桁目(9 % 10)を加算し、一つ減算(-1)した値
    (9 * 10 + 9 % 10 - 1 = 98)

  • ルンルン数を10倍し（9 * 10)、ルンルン数の一桁目(9 % 10)を加算した値
    (9 * 10 + 9 % 10 = 99)

  • ルンルン数を10倍し（9 * 10)、ルンルン数の一桁目(9 % 10)を加算し、一つ加算(+1)した値
    (9 * 10 + 9 % 10 + 1 = 100)
    // ルンルン数だが、ルンルン数が10の時と被るので不要

ルンルン数が10の場合（一桁目が0のとき）

  • ルンルン数を10倍し（10 * 10)、ルンルン数の一桁目(10 % 10)を加算し、一つ減算(-1)した値
    (10 * 10 + 10 % 10 - 1 = 99)
    // ルンルン数だが、ルンルン数が9の時と被るので不要

  • ルンルン数を10倍し（10 * 10)、ルンルン数の一桁目(10 % 10)を加算した値
    (10 * 10 + 10 % 10 = 100)

  • ルンルン数を10倍し（10 * 10)、ルンルン数の一桁目(10 % 10)を加算し、一つ加算(+1)した値
    (10 * 10 + 10 % 10 + 1 = 101)

あとは一桁目に気を付けて、上記のルールでK回処理を行い、ルンルン数の配列を作ったら
配列のK-1番目が回答のルンルン数となる。