ABC072 D - Derangement
備忘録
問題
回答
import sys import os import math import bisect import itertools import collections import heapq import queue import array import time import numpy as np from numpy import linalg as LA # 時々使う # import numpy as np # from decimal import Decimal, ROUND_HALF_UP # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # from collections import defaultdict, deque # 再帰の制限設定 sys.setrecursionlimit(10000000) def ii(): return int(sys.stdin.buffer.readline().rstrip()) def il(): return list(map(int, sys.stdin.buffer.readline().split())) def fl(): return list(map(float, sys.stdin.buffer.readline().split())) def iln(n): return [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] def iss(): return sys.stdin.buffer.readline().decode().rstrip() def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split())) def isn(n): return [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] def lcm(x, y): return (x * y) // math.gcd(x, y) # MOD = 10 ** 9 + 7 MOD = 998244353 INF = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N = ii() P = il() ret = 0 nxt = False for i in range(N): if nxt: nxt = False continue if P[i] == i + 1: nxt = True ret += 1 print(ret) if __name__ == '__main__': main()
考え方
ある数字がi = Pi
となっているとき、隣り合う数字と入れ替えを行う。
このとき、i
番目の数字はi != Pi
となる。
さらに、隣のi + 1
番目に存在していた数字はi
番目になる。
つまり、入れ替えが必要なi
番目の数字に隣り合うi + 1
番目の数字は、
入れ替えが行われると、必ずi != Pi
となるため、
入れ替えが必要になった次の数字については考慮をする必要がない。