概要

与えられた順序で本を棚に戻すとき、各時点以降に残っている本のうち現在の本より小さい棚番号を持つ本の数を合計する問題。

考察

この問題では、各 \(i\) 番目の本を戻した後の残りの本に対して「棚の番号が \(G_i\) 未満である本の数」を数える必要があります。これを素直に前からシミュレートすると、毎回最大 \(M\) 冊の本を走査する必要があり、全体で \(O(M^2)\) の計算量となり、制約が大きいためTLEになります。

重要な観察は、各 \(L_i\) は「今後戻す予定の本の中で、現在の本の棚番号よりも小さい番号の本が何冊あるか」ということです。つまり、後ろから処理すれば、すでに見た本が「今後戻す予定の本」に該当し、効率的に管理できます。

さらに、この「今後戻す予定の本のリスト」において、棚番号が小さい順にソートしておけば、二分探索によって「\(G_i\) 未満の本の数」を高速に求めることができます。

アルゴリズム

1. 本を戻す順番を後ろから処理します。
2. books_after というリストを用意し、これは「現在までに処理した本（＝今後戻す予定の本）」を棚番号の昇順で保持します。
3. 各本について：
   • 現在の本の棚番号 \(G_i\) に対して、books_after 中で \(G_i\) 未満の本の数を二分探索で求め、total に加算します。
   • 次に、現在の本を books_after に挿入します（ソート順を保ちながら挿入するために insort を使います）。
4. 最終的な total を出力します。

例

入力が以下の場合を考えます：

N = 5
M = 4
G = [3, 1, 4, 2]

• 後ろから処理：
  • \(i=3\): \(G_3=2\) → books_after=[] → \(L_3=0\)、books_after=[2]
  • \(i=2\): \(G_2=4\) → books_after=[2] → \(L_2=1\)、books_after=[2,4]
  • \(i=1\): \(G_1=1\) → books_after=[2,4] → \(L_1=0\)、books_after=[1,2,4]
  • \(i=0\): \(G_0=3\) → books_after=[1,2,4] → \(L_0=2\)、books_after=[1,2,3,4]

合計は \(0+1+0+2=3\)

計算量

• 時間計算量: \(O(M \log M)\)
  （各要素に対して二分探索と挿入操作を行うため）
• 空間計算量: \(O(M)\)
  （books_after リストのサイズ）

実装のポイント

• 後ろから処理することで、「今後戻す予定の本」を効率的に管理できる。

• ソートされたリストに対して、二分探索（bisect_left）で高速に条件を満たす要素数を求めること。

• insort を使うことで、リストを常にソートされた状態に保ちながら要素を挿入できる。

  ソースコード

import sys
from bisect import bisect_left, insort

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    G = list(map(int, data[2:]))

    # 本の番号を後ろから処理するためのリスト（棚の番号）
    # 後ろから処理して、現在処理中の本以降の本のリストを管理
    books_after = []
    total = 0
    
    # 後ろから処理することで、すでに追加された本がbooks_afterに含まれる
    for i in range(M-1, -1, -1):
        g = G[i]
        # g未満の本の数をカウント (bisect_leftでg未満の要素数を得る)
        idx = bisect_left(books_after, g)
        total += idx
        # 現在の本をリストに追加（次以降の比較対象になる）
        insort(books_after, g)
        
    print(total)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。