第８回日本情報オリンピック　予選５

2008年12月23日
情報オリンピック日本委員会

解説

カードをシャッフルしていく様子をシミュレートする問題である． 基本的な配列と繰り返しのプログラムが書ければ部分点を取ることは難しくない． しかし，満点を取るためには，アルゴリズムやデータ構造を工夫してプログラムを書く必要がある．

解法１

配列を用いて n 枚のカードの状態を記憶する． 例えば，長さ n の配列 t[1],...,t[n] を用意して， 一番上のカードに書かれた番号を t[1]， 上から2枚目のカードに書かれた番号を t[2]，...， 一番下のカードに書かれた番号を t[n] に格納する． 最初の山の状態では，t[1] = 1, t[2] = 2, ..., t[n] = n である．
このようにしてカードの状態を記憶しておけば， 配列を3段階に分けてコピーすることで，シャッフルを実現することができる． 「シャッフル(x,y)」を行う場合は次のようにすればよい． 作業用の配列 s[1],...,s[n] を用意して，

と代入する．これはループを3つ書くだけで実現できる． 最後に配列 s の内容を配列 t にコピーすればよい．
この解法では，1回のシャッフルに O(n) 時間かかるから， 全体で O(mn) 時間かかってしまう． この問題では n の値がとても大きいので， この解法では満点を取ることは難しい．

解法２

この問題では，カードの枚数 n がシャッフルの回数 m に比べてとても大きいことに注目しよう． カードの山のうち，ほとんどの部分は連続して並んでいるはずである． したがって，カードの1枚1枚を別々のデータとして配列に記憶するのは無駄である． 連続して並んでいるカードをまとめて， 1 つの「束」として処理することで， 効率の良い解法が得られる．
例えば，次のようにすればよい． 最初の山の状態では n 枚のカードが順番に並んでいるから， それを 1 つの「束」と考えて，[1,n] で表すことにする （[1,n] は『 1 から n まで』という意味である）． 同様に，カードの山の中に，番号 a から番号 b までの b - a + 1 枚のカードが順番に並んでいたら， それは [a,b] というカードの「束」としてまとめて処理する．
（次のようにイメージすれば分かりやすいかもしれない． 解法１では n 枚のカードを 1 枚ずつ別々に処理するので，膨大な時間がかかってしまう． 解法２では，連続したカードをクリップでまとめて処理する． もちろんシャッフルする際には，必要に応じてクリップをつけ直す手間がかかるが， カードの枚数が膨大な場合は，こうした方が効率が良い．）
この方法を問題文の入力例1に適用すると次のようになる． まず，最初の山の状態は，一つの「束」

で表される． 「シャッフル(3,5)」を行うためには，まず，[1,9] という「束」を

という3つの「束」に分割する．そして，「束」を並び替えて，

とすればよい． 後は，シャッフルを行う毎に，「束」を適切に分割して並び替えていけばよい．
シャッフルを行う毎に「束」の個数が増えていくから， 1回のシャッフルは O(m) 時間かかる． したがって，この解法では，全体で O(m²) 時間かかる．

入力データについて

参考までに，以下に，採点用の５つの入力データにおける n, m の値を挙げる．

解法1の場合， 最初の2つのテストデータに対して正解を出力することができるが， n の値が大きい残りの３つのデータに対しては， どんなに高速なＰＣを使ったとしても， 現実的な時間内に正解を求めることはできないだろう． また，メモリが足りず，長さ n の配列を確保することができないかもしれない．
もちろん，解法2であれば，制限時間内に正解を出力することが可能である．

この問題のように，情報オリンピックでは， 単純な解法で部分点を取ることは難しくないが， さらに高得点を得るためには問題を分析して， アルゴリズムやデータ構造を工夫する必要がある問題が多く出題される． ある程度プログラミングが上達してきたら， 単に動けばいいや，という気持ちでプログラムを書くのではなく， 『どこに無駄があるか．どうすれば効率の良いプログラムが書けるか』 と考えながら書くとよい． そうすることで，プログラミングの面白さ・深さがますます実感できるようになるだろう．