ABC004 C - 入れ替え

AtCoder Python3

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import collections
import itertools
import heapq

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 = ii()
    C = [str(i) for i in range(1, 7)]
    for n in range(N % 30):
        n %= 5
        C[n], C[n + 1] = C[n + 1], C[n]
    print(''.join(C))


if __name__ == '__main__':
    main()

考え方

カードの配列[1, 2, 3, 4, 5, 6]について考える。
まず、1枚目のカード1が初期位置の最も右から最も左に移動するまでに5回の移動が必要になる。
[1, 2, 3, 4, 5, 6] → [2, 3, 4, 5, 6, 1]
このことから、カードを25回動かした場合、カードの配列は以下のようになることがわかる。
[6, 1, 2, 3, 4, 5]
ここからさらに5回カードを動かすと、カードの配列は初期状態に戻る。
[6, 1, 2, 3, 4, 5] → [1, 2, 3, 4, 5, 6]

仮に31回カードの移動を行う場合、
初めの30回でカードの配列は初期状態に戻るため、
愚直に31回行う必要はなく、1回行うだけで、
31回移動した結果 ＝ 1回移動した結果となる。
つまり、与えられる整数N回カードの移動を行った場合と、
N % 30回カードの移動を行った場合は同じ結果となるため、試行する回数はN % 30。
最大でも29回でよい。

実装はforでN % 30回ループ、
与えられた条件通りに配列の操作を行うだけ。