問題
5人の友人が帽子を1か所に集め、それぞれ無作為に1つずつ取ります。誰も自分の帽子を取らないような取り方は何通りあるでしょうか。n 個のものの並べ替えのうち、どれも元の位置に残らないものを完全順列(攪乱順列)といいます。その個数は 1, 0, 1, 2, 9, 44 と続き、D(n) = (n − 1) × (D(n − 1) + D(n − 2)) を満たします。
derangements(n) を実装してください。
入力
n:ものの個数。
出力
n 個のものの完全順列の個数を返してください。D(0) は 1(空の並べ方には、元の位置に残るものがありません)、D(1) は 0 です。
制約
0 ≤ n ≤ 20
例
例 1
入力:
n = 3
期待される出力:
expected = 2
入力:
long long n = 3;
期待される出力:
long long expected = 2;
入力:
long n = 3;
期待される出力:
long expected = 2;
解説
A, B, C の場合、すべてが移動するのは BCA と CAB だけなので、答えは 2 です。
例 2
入力:
n = 4
期待される出力:
expected = 9
入力:
long long n = 4;
期待される出力:
long long expected = 9;
入力:
long n = 4;
期待される出力:
long expected = 9;
解説
D(4) = 3 × (D(3) + D(2)) = 3 × (2 + 1) = 9 です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
D(0) = 1、D(1) = 0 から始めます。
ヒント 2
次の値は、直前の2つの値と現在の n を使って求めます。
ヒント 3
常に必要なのは直近の2つの値だけです。
目安の計算量
時間 O(n)、追加メモリ O(1)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。