すべてのチャレンジ
中級 0件解決済み 正答率0%

完全順列(攪乱順列)

n 個のものを並べ替えて、どれも元の位置に残らない並べ方の数を数えます。

このチャレンジで学べること

  • 数え上げの考え方を漸化式に落とし込める
  • 初期値から漸化式を繰り返し計算できる
  • n = 0 と n = 1 の場合を正しく扱える

問題

原文(英語)を表示

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用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。