deq notes

Hanafuda Shuffle 解説

• 問題名：Hanafuda Shuffle (PKU)
• 出典：Problem A, ACM/ICPC Japan Domestic, 2004-07-02
• 難易度：☆
• 問題の種類：シミュレーション
• 解法：配列を書き換え
• 解答ソースコード：
  • 1978-deq.cpp
  • HanafudaShuffle.java
• プログラムプロムナードの解説：2004年12月号『国内予選を突破せよ』（湯浅太一）

アルゴリズムの概略

問題文で与えられている通りにプログラムを書けばOKです。 現在の花札の状態データを格納する配列以外に，シャッフル時の一時データを格納する配列も使うと楽でしょう。 この問題は花札のシャッフルを行うのをシミュレートするのでシミュレーション問題に分類できます。

アルゴリズムの計算量

まず，基本的にはシャッフル回数が r なので，r回繰り返すのでその部分の計算量は O(r) となります。 そして，一回のシャッフルに必要な計算量は最大でトランプの枚数 n に対してたかだか係数倍，具体的には1～2回の配列走査で済みます。 従って，最終的に O(r×n) 程度で，1 <= n <= 50, 1 <= r <= 50 の入力に対して計算量は問題となりません。

アルゴリズムの実装

配列の添え字に気を付けてください。 一度，紙にn=5くらいのケースの場合の図を描いて，添え字が合っているかどうかちゃんと確かめた方がいいと思います。

$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $