本の整理 (paizaランク A 相当)：Python3解答例

Posted at 2024-08-24

背景

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

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

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

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

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

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

例)

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 となります。

このコードは、パイザ図書館でバラバラに並べられた本棚の本をID順に並べ替える際に、何回本を交換する必要があるかを計算するプログラムです。

入力の受け取りと前処理:
```
N = int(input())
shelf = [int(x) - 1 for x in input().split()]
```
- N は本の冊数を表します。
- shelf は本棚に並んでいる本のIDのリストを0ベースに変換して格納します。例えば、入力が 1 3 2 の場合、shelf は [0, 2, 1] になります。
位置情報の初期化:
```
pos = [-1] * N
for i in range(N):
    pos[shelf[i]] = i
```
- pos リストは各本のIDの現在の位置を記録するために使用します。
- pos[shelf[i]] = i により、本のID shelf[i] の現在の位置 i を記録します。
本の交換の計算:
```
ans = 0
for i in range(N):
    if shelf[i] == i:
        continue

    ans += 1
    shelf[pos[i]] = shelf[i]
    pos[shelf[i]] = pos[i]
```
- ans は本の交換回数をカウントする変数です。
- for i in range(N) ループを使って、各本のIDがそのインデックス i と一致するかを確認します。
- 本のIDが正しい位置にない場合、交換を行います。
- ans を1増やし、shelf と pos の情報を更新します。
結果の出力:
```
print(ans)
```
- 最後に、交換回数 ans を出力します。

例えば、入力が次のような場合：

5
5 4 3 2 1

この場合の処理は以下のようになります：

初期状態:
- shelf = [4, 3, 2, 1, 0]（本のIDを0ベースに変換）
- pos = [4, 3, 2, 1, 0]（各IDの位置）
交換のステップ:
- i = 0 のとき、shelf[0] != 0 なので、交換を行います。shelf と pos を更新します。交換回数 ans を1増やします。
- i = 1 のとき、shelf[1] != 1 なので、交換を行います。再び shelf と pos を更新し、交換回数 ans を1増やします。
- i = 2, 3, 4 のときは、すでに正しい位置にあるので、交換は行いません。

結果として、交換回数は 2 となり、これが出力されます。