paiza プログラミング

[Ruby]paiza リアルイベント問題セット 本の整理 (paizaランク A 相当)

今回はpaiza リアルイベント問題セット 「本の整理」 (paizaランク A 相当)を解説します。

順番がバラバラになっている本を指示されたルールに従って並び替えた時の入れ替え回数を答える問題です。

本の整理 (paizaランク A 相当)

※ paiza リアルイベント問題セット より

問題

あなたはパイザ図書館で働く図書館員です。

パイザ図書館には N 冊の蔵書があります。この蔵書はすべて 1 段からなる本棚で管理されています。そして、それぞれの本には 1 から N までの相異なる整数の ID がついています。本棚の本は ID 順に並んでいます。

しかし、ある日、あなたが蔵書の点検をしていると、本棚の本がバラバラに並べられていることに気づきました。

そこで、あなたは、次のルールに従って本を並び替えることにしました。

次の手順を N 回繰り返す。

1. i (1 ≦ i ≦ N) 回目の手順では、まず本棚の左から i 番目の位置に立つ。
2. 左から i 番目の位置にある本から、本棚の右端にある本までのうち、最も ID が小さい本の位置を歩きながら見つける。この位置を j とする。
3. i = j なら、何もしない。 i ≠ j なら、i 番目の本と j 番目の本を入れ替える。

本を取り出して入れ替えるのには時間がかかります。そこで、このルールに従って本を整理するときに、何回本を入れ替える必要があるのかを計算してください。

例)

5 冊の本が、本棚に次の順番で並んでいたとします。ただし、数字はそれぞれの本の ID を表します。

5 4 3 2 1

このとき、ルールに従うと、次のように本が整理されます。

i = 1 のとき (1 番目の本と 5 番目の本の位置が入れ替わる)

1 4 3 2 5

i = 2 のとき (2 番目の本と 4 番目の本の位置が入れ替わる)

1 2 3 4 5

i = 3 のとき

1 2 3 4 5

i = 4 のとき

1 2 3 4 5

i = 5 のとき

1 2 3 4 5

本の交換は i = 1 のときと i = 2 のときのみ起こっているので、このときの出力は 2 となります。

入力される値

入力は以下のフォーマットで与えられます。

N
a_1 a_2 ... a_N

  • 1 行目に本の冊数を表す整数 N が与えられます。
  • 2 行目に、 1 番目の本の ID を表す整数 a_1、 2 番目の本の ID を表す整数 a_2、 ...、 N 番目の本の ID を表す整数 a_N がこの順に半角スペース区切りで与えられます。
  • 入力は合計で 2 行となり、末尾に改行が 1 つ入ります。

入力値最終行の末尾に改行が１つ入ります。

期待する出力

本の交換をする回数を整数で出力してください。

条件

すべてのテストケースにおいて、以下の条件をみたします。

  • 1 ≦ N ≦ 100,000
  • 1 ≦ a_i ≦ N (1 ≦ i ≦ N)
  • 各 j, k (1 ≦ j, k ≦ N) について j ≠ k のとき a_j ≠ a_k
入力例1
5
5 4 3 2 1
出力例1
2
入力例2
10
8 7 9 1 5 6 2 10 4 3
出力例2
6
攻略ポイント

ポイント

  • 問題文の条件から、効率よく該当IDの本を検索する方法を考える
    • 本の数 = 棚の数 = N （空になる棚はない）
    • 本のIDは 1 ～ N の連番
    • 1 ≦ N ≦ 100,000
問題を解く流れ

入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。

INPUT1 = <<~"EOS"
  5
  5 4 3 2 1
EOS
OUTPUT1 = <<~"EOS"
  2
EOS

INPUT2 = <<~"EOS"
  10
  8 7 9 1 5 6 2 10 4 3
EOS
OUTPUT2 = <<~"EOS"
  6
EOS

# 確認用コード
p INPUT1
# > "5\n5 4 3 2 1\n"
p OUTPUT1
# > "2\n"
p INPUT2
# > "10\n8 7 9 1 5 6 2 10 4 3\n"
p OUTPUT2
# > "6\n"
よくある失敗実装

せっかく罠がある問題なので、やりがちな失敗をしてみたいと思います。
失敗実装をsolve1メソッドとし、変数の下に定義します。

solve1 処理の流れ

  • 入力データ受け取り
    • 棚の数=本の数 : 整数n
    • 棚に入っている本のID: 整数の配列a
  • 交換回数count = 0 で初期化する
  • 配列a[i] (0 ≦ i ≦ n-2)の順番で整数a[i](本のID)を取り出す
    • s_id = i + 1
      ※ s_id: i番目の棚に収めるべき本のID
    • a[i] == s_id なら i のループをスキップ(next)する
    • a[j] (i+1 ≦ j ≦ n-1)の順番で整数a[j](本のID)を取り出す
      • a[j] == s_id なら
        • 棚a[i]にある本のIDと 棚a[j] にある本のIDを入れ替える
        • 交換回数count を +1 する
        • j のループを抜ける(break)
  • 交換回数count を出力する

以上を実装すると、例えばINPUT2 の処理は下図のようになります。

INPUT2の処理の流れ

では、以上の処理をsolve1メソッドに書いていきます。（今回は動作確認用コードも入れます）

def solve1(input_lines)
  n, *a = input_lines.split.map(&:to_i)

  # 【確認用コード ここから】
  search = 0
  # 【確認用コード ここまで】

  count = 0
  # 棚の左端から右に向かって調査していく
  0.upto(n - 2) do |i|

    # 【確認用コード ここから】
    search += 1
    p a
    # 【確認用コード ここまで】

    # index: i の棚には 本ID: i + 1 の本を置く
    s_id = i + 1
    # 調査中の棚にある本のIDが正しければ次の棚を調べる
    next if a[i] == s_id

    # 調査中の棚より右側から index: i の棚に置く本を探す
    (i + 1).upto(n - 1) do |j|

      #【確認用コード ここから】
      search += 1
      #【確認用コード ここまで】

      # index: i に置く本 a[j] を発見したとき
      if a[j] == s_id
        # a[i] にある本と a[j] にある本を入れ替え
        a[i], a[j] = a[j], a[i]
        # カウントアップして j のループを抜ける
        count += 1
        break
      end
    end
  end

  # 【確認用コード ここから】
  p a
  puts "search: #{search}"
  # 【確認用コード ここまで】

  count
end

# 確認用コード
p solve1(INPUT1)
# > [5, 4, 3, 2, 1]
# > [1, 4, 3, 2, 5]
# > [1, 2, 3, 4, 5]
# > [1, 2, 3, 4, 5]
# > [1, 2, 3, 4, 5]
# > search: 10
# > 2

p solve1(INPUT2)
# > [8, 7, 9, 1, 5, 6, 2, 10, 4, 3]
# > [1, 7, 9, 8, 5, 6, 2, 10, 4, 3]
# > [1, 2, 9, 8, 5, 6, 7, 10, 4, 3]
# > [1, 2, 3, 8, 5, 6, 7, 10, 4, 9]
# > [1, 2, 3, 4, 5, 6, 7, 10, 8, 9]
# > [1, 2, 3, 4, 5, 6, 7, 10, 8, 9]
# > [1, 2, 3, 4, 5, 6, 7, 10, 8, 9]
# > [1, 2, 3, 4, 5, 6, 7, 10, 8, 9]
# > [1, 2, 3, 4, 5, 6, 7, 8, 10, 9]
# > [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# > search: 31
# > 6

正しく計算出来ているようなので、確認用コードを削除し、標準入力からのデータ入力、交換回数countを出力するようにコードを変更して提出してみます。

solve1 提出コード

def solve1(input_lines)
  n, *a = input_lines.split.map(&:to_i)

  count = 0
  # 棚の左端から右に向かって調査していく
  0.upto(n - 2) do |i|

    # index: i の棚には 本ID: i + 1 の本を置く
    s_id = i + 1
    # 調査中の棚にある本が正しければ次の棚を調べる
    next if a[i] == s_id

    # 調査中の棚より右側から index: i に置く本を探す
    (i + 1).upto(n - 1) do |j|

      # index: i に置く本 a[j] を発見したとき
      if a[j] == s_id
        # a[i] にある本と a[j] にある本を入れ替え
        a[i], a[j] = a[j], a[i]
        # カウントアップして j のループを抜ける
        count += 1
        break
      end
    end
  end
  count
end

puts solve1(STDIN.read)

提出結果

最後のテスト10が通らず・・・残念！

ということで、solve1メソッドでテスト10が通らなかった原因を確認してみましょう。
INPUT1(n = 5, a = [5, 4, 3, 2, 1])のようなカウントダウンの数列の桁を増やしながら入力データとして与えて、処理時間を測ってみます。

def solve1(input_lines)
  n, *a = input_lines.split.map(&:to_i)

  count = 0
  # 棚の左端から右に向かって調査していく
  0.upto(n - 2) do |i|
    # index: i の棚には 本ID: i + 1 の本を置く
    s_id = i + 1

    # 調査中の棚にある本が正しければ次の棚を調べる
    next if a[i] == s_id

    # 調査中の棚より右側から index: i に置く本を探す
    (i + 1).upto(n - 1) do |j|
      # index: i に置く本 a[j] を発見したとき
      if a[j] == s_id
        # a[i] にある本と a[j] にある本を入れ替え
        a[i], a[j] = a[j], a[i]
        # カウントアップして j のループを抜ける
        count += 1
        break
      end
    end
  end
  count
end

# 配列サイズが大きいときの処理時間
[5, 10, 100, 1_000, 10_000, 100_000].each do |n|
  input = ([n] + n.downto(1).to_a).join(" ")

  start = Time.now
  puts "n = #{n.to_s.rjust(6)}"
  puts "交換回数 #{solve1(input).to_s.rjust(5)} 処理時間: #{Time.now - start}"
  puts "---"
end

# > n =      5
# > 交換回数     2 処理時間: 7.91e-05
# > ---
# > n =     10
# > 交換回数     5 処理時間: 2.67e-05
# > ---
# > n =    100
# > 交換回数    50 処理時間: 0.0002558
# > ---
# > n =   1000
# > 交換回数   500 処理時間: 0.0195869
# > ---
# > n =  10000
# > 交換回数  5000 処理時間: 1.892705
# > ---
# > n = 100000
# > 交換回数 50000 処理時間: 190.5272883
# > ---

データ数nと処理時間の関係を見てみると、 nの桁が1個増えるごとに処理時間の桁が2個増えていることが分かります。
最後の n = 100,000 の時は処理時間に190秒かかっていますが、判定は16秒で打ち切られるのでタイムオーバーが発生してしまうというわけですね。

本の場所を1発で検索する

失敗した実装では、調査対象の棚を調べてそこから右に順番に探索していましたが、本のIDは 1〜n までの重複なしであることから、本の位置を保持する配列を用意することで、ループなしで任意の本の位置を取得することが出来ます。

solve2 処理の流れ

  • 入力データ受け取り
    • 棚の数=本の数 : 整数n
    • 棚に入っている本のID: 整数の配列a
  • 要素数n の 配列b を用意する。
  • b[a[i] - 1] に インデックスi を格納する。
    ※ 本ID: i の場所を取得するには b[i - 1] を参照する
  • 交換回数count = 0 で初期化する
  • 配列a[i] (0 ≦ i ≦ n-2)の順番で整数a[i](本のID)を取り出す
    • s_id = i + 1
      ※ s_id: i番目の棚に収めるべき本のID
    • a[i] == s_id なら i のループをスキップ(next) する
    • tmp_p = b[i]
      ※ 現在の棚に置くべき本がある場所を格納
    • tmp_i = a[i] - 1
      ※ 現在の棚に置かれている本の位置情報を格納する配列bのindexを格納
    • a[i] と a[tmp_p] を入れ替える（本のID情報）
    • b[i] と b[tmp_i] を入れ替える（本の位置情報）
    • 交換回数count を +1 する
  • 交換回数count を出力する

文字で説明しても分かりづらいですね。
今回もINPUT2 の処理を図にしてみました。

では、以上の処理をsolve2メソッドに書いていきます。
今回はINPUT1, INPUT2, n = [5, 100, 1000, 10000, 100000] まで一気に確認します。

def solve2(input_lines)
  n, *a = input_lines.split.map(&:to_i)

  # b[index(本ID - 1)] に 現在位置を格納
  b = Array.new(n)
  a.each_with_index { |ai, i| b[ai - 1] = i }

  count = 0
  # 棚の左端から右に向かって調査していく
  a.each_with_index do |ai, i|
    # ai: 現在の本ID, i+1: 入るべき本ID
    # 調査中の棚にある本が正しければ次の棚を調べる
    next if ai == i + 1

    # tmp_p: 正しい本がある場所
    tmp_p = b[i]
    # tmp_i: 調査中の棚に置かれている本のindex
    tmp_i = a[i] - 1

    # 本の情報を入れ替える
    a[i], a[tmp_p] = a[tmp_p], a[i]
    b[i], b[tmp_i] = b[tmp_i], b[i]

    count += 1
  end
  count
end

# 確認用コード
p solve2(INPUT1)
# > 2
p solve2(INPUT2)
# > 6

# 配列サイズが大きいときの処理時間
[5, 10, 100, 1_000, 10_000, 100_000].each do |n|
  input = ([n] + n.downto(1).to_a).join(" ")

  start = Time.now
  puts "n = #{n.to_s.rjust(6)}"
  puts "交換回数 #{solve2(input).to_s.rjust(5)} 処理時間: #{Time.now - start}"
  puts "---"
end
# > n =      5
# > 交換回数     2 処理時間: 1.4e-05
# > ---
# > n =     10
# > 交換回数     5 処理時間: 2.2e-05
# > ---
# > n =    100
# > 交換回数    50 処理時間: 6.7e-05
# > ---
# > n =   1000
# > 交換回数   500 処理時間: 0.001765
# > ---
# > n =  10000
# > 交換回数  5000 処理時間: 0.007277
# > ---
# > n = 100000
# > 交換回数 50000 処理時間: 0.062295
# > ---

n = 100,000 でも 0.06秒で解けているので問題なさそうです！

確認用コードを標準入力からのデータ受け取りに変更、標準出力をpメソッドからputsメソッドに変更して、動作確認をしたら提出します。（STDIN.readの入力終了は Ctrl+D 又は Ctrl+Z)

解答コード
def solve2(input_lines)
  n, *a = input_lines.split.map(&:to_i)

  # b[index(本ID - 1)] に 現在位置を格納
  b = Array.new(n)
  a.each_with_index { |ai, i| b[ai - 1] = i }

  count = 0
  # 棚の左端から右に向かって調査していく
  a.each_with_index do |ai, i|
    # ai: 現在の本ID, i+1: 入るべき本ID
    # 調査中の棚にある本が正しければ次の棚を調べる
    next if ai == i + 1

    # tmp_p: 正しい本がある場所
    tmp_p = b[i]
    # tmp_i: 調査中の棚に置かれている本のindex
    tmp_i = a[i] - 1

    # 本の情報を入れ替える
    a[i], a[tmp_p] = a[tmp_p], a[i]
    b[i], b[tmp_i] = b[tmp_i], b[i]

    count += 1
  end

  # 交換回数 count を文字列に変換し末尾に改行を追加
  count.to_s << "\n"
end

puts solve2(STDIN.read)
他の解答例

ハッシュを使って解くこともできます。

def solve3(input_lines)
  n, *a = input_lines.split.map(&:to_i)

  # key: 本のID-1, value: 今ある場所
  b = a.each_with_index.to_h

  count = 0
  # 棚の左端から s_id: 1 ~ s_id: n として
  # s_id と 本ID が揃うように並べ替える
  0.upto(n - 1) do |i|
    # s_id: 棚ID
    s_id = i + 1

    # 調査中の棚にある本が正しければ次の棚を調べる
    next if a[i] == s_id

    # tmp_p: 正しい本がある場所
    tmp_p = b[s_id]
    # tmp_i: 調査中の棚に置かれている本のID
    tmp_i = a[i]

    # 本の情報を入れ替える
    a[i], a[tmp_p] = a[tmp_p], a[i]
    b[s_id], b[tmp_i] = b[tmp_i], b[s_id]
    count += 1
  end
  count.to_s << "\n"
end

puts solve3(STDIN.read)

今回のまとめ

多重ループで考えると分かりやすい問題もありますが、要素数が増えると計算量が一気に増加しますので注意しましょう！

paiza Aランク問題あたりからは答えが合っていても（工夫なしの）多重ループで実装すると時間切れになるケースも出てきます。
問題の条件を確認して、超ざっくりで良いので計算量をつかんでおきましょう。


【PR】アルゴリズム学習でお世話になった本


アルゴリズム関連の技術書は大抵C/C++で書かれていますが、ある程度プログラムが出来れば、処理の流れは理解することが出来ます。





通称: 螺旋本。C++で解説されています。AOJ(Aizu Online Judge)を運営している会津大学の渡辺准教授が書いた本です。データ構造や計算量の内容から丁寧に書いてありますのでアルゴリズム学習の最初の参考書としてオススメです。


プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 [ 渡部有隆 ]
posted with カエレバ
楽天市場
Amazon
Yahooショッピング




通称: 蟻本。C++で解説されています。競技プログラミング中級者の定番書と言われていて、競技プログラミングで利用できる色々なアルゴリズムを学ぶことが出来ます。かなり高度な内容も含まれているので1冊分を完全に理解するのにはかなりの時間がかかりそうですが、手元に置いて何度も読み返しています。


プログラミングコンテストチャレンジブック第2版 問題解決のアルゴリズム活用力とコーディングテクニッ [ 秋葉拓哉 ]
posted with カエレバ
楽天市場
Amazon
Yahooショッピング




通称: チーター本。C#, C++, JAVAでTopcoderの問題を解説しています。初心者～中級者向けに書かれているので解説が非常に丁寧です。


最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド【電子書籍】[ 高橋 直大 ]
posted with カエレバ
楽天市場
Amazon
Yahooショッピング




Python3でアルゴリズムを解説している本です。講義スタイルの本で、図やフローチャートを使ってアルゴリズムとデータ構造についてしっかりと説明されています。代わりにコードは少なめです。Pythonコードが読めなくても十分理解できると思います。


Pythonで体験してわかるアルゴリズムとデータ構造 [ 西澤 弘毅 ]
posted with カエレバ
楽天市場
Amazon
Yahooショッピング

-paiza, プログラミング
-,

© 2024 じゃいごテック