6.1

この問題は「座標圧縮」と呼ばれる典型的な処理です。
各要素が全体で何番目に小さいか（0始まりの順位）を求める問題で、ソートを使うと (O(N \log N)) で実現できます。

アイデア

  1. 値と元の位置をペアにする
    配列 a の各要素に、「値」と「もともとあったインデックス」をセットにしたタプルを作ります。
    例：a = [12, 43, 7, 15, 9] → [(12,0), (43,1), (7,2), (15,3), (9,4)]

  2. 値でソートする
    タプルのリストを「値」の昇順に並べ替えます。
    ソート後：[(7,2), (9,4), (12,0), (15,3), (43,1)]
    こうすると、先頭から順に「0番目に小さい値、1番目に小さい値…」と順位が決まります。

  3. 順位を格納する配列を作る
    答えを入れる配列 rank を用意し、ソート後のリストを先頭から見ていきます。
    ソート後の i 番目の要素が持つ「元のインデックス」の位置に、順位 i を入れます。
    上の例なら：

    • i=0 → 元のインデックス 2 → rank[2] = 0
    • i=1 → 元のインデックス 4 → rank[4] = 1
    • i=2 → 元のインデックス 0 → rank[0] = 2
    • i=3 → 元のインデックス 3 → rank[3] = 3
    • i=4 → 元のインデックス 1 → rank[1] = 4

    結果 rank = [2, 4, 0, 3, 1] となり、問題例と一致します。

ソートが (O(N \log N))、その後の走査が (O(N)) なので、全体で (O(N \log N)) です。
※値がすべて相異なるという条件があるので、同点を気にする必要はありません。

6.2

アイデア

条件は「a のある要素 < b のある要素 < c のある要素」なので、真ん中の配列 b に着目して考えます。
ある b[j] を固定したとき、次の2つが分かれば、その b[j] を使う組の数が計算できます。

  • a の中で b[j] より小さい要素の個数
  • c の中で b[j] より大きい要素の個数

この2つの積が、その b[j] に対する有効な (i, k) の組み合わせ数です。
あとはすべての j についてこれを合計すれば答えになります。

効率的な求め方

  1. 配列 a と c をソートする

    • a は昇順にソート → O(N log N)
    • c も昇順にソート → O(N log N)
      ※ b はそのまま使うためソート不要です。

  2. 各 b[j] について個数を二分探索で求める

    • a の中で b[j] より小さい要素の個数 → bisect_left(a, b[j]) のインデックスがその個数。
    • c の中で b[j] より大きい要素の個数 → N - bisect_right(c, b[j]) で求められる。
      （bisect_right は b[j] より大きい最初の位置を返すため、そこから末尾までが条件を満たす要素数）
      これは1つの b[j] あたり O(log N) なので、全体で O(N log N) です。

  3. 積を合計していく
    各 j について (aの小さい個数) * (cの大きい個数) を足し上げます。

  • 個数を求めるだけなので二分探索を実装しなくてもbisectを使うことができる
  • 数列の要素に重複があっても、bisect_left / bisect_right を使うことで「より小さい」「より大きい」を正しく数えられます。
  • 答えが大きくなる可能性があるため、言語によっては64ビット整数が必要ですが、Pythonの整数は自動拡張されるので問題ありません。
  • この解法の計算量は、ソートに O(N log N)、二分探索のループに O(N log N) で、全体 O(N log N) です。

6.3

アイデア

4つの数の組み合わせを直接調べると \(O(N^4)\) かかります。そこで、「2つの数の和」をあらかじめ全列挙し、問題を2段階に分けることで高速化します。

  1. 2数の和を全生成する
    配列 \(a\) から2つの要素（重複可）を選んだ和の一覧 \(S\) を作ります。
    組み合わせは \(N \times N = N^2\) 通り → \(O(N^2)\)。

  2. ソートする
    \(S\) を昇順にソートします → \(O(N^2 \log N)\)。

  3. 探索する
    いま、選ぶ4つの数は「2つの数の和」2つに分解できます。
    一方の和を \(x \in S\)、もう一方を \(y \in S\) とすると、条件は \(x + y \le M\) です。
    ソート済みの \(S\) に対し、各 \(x\) について \(M - x\) 以下で最大の \(y\) を二分探索で見つけ、\(x + y\) の最大値を記録します。
    各 \(x\) の探索は \(O(\log |S|) = O(\log N)\)、全体で \(O(N^2 \log N)\) です。

ポイント

  • 重複を許すため、\(S\) は \(a_i + a_j\) （\(i,j\) は独立に全範囲）とすれば同じ要素の複数回使用もカバーできます。(こんなの思いつけるかい)
  • 二分探索には bisect_right を使い、M - x 以下の最後の位置を求めます。
  • 正の整数のみなので \(S\) の要素も2以上ですが \(x > M\) のときはスキップして構いません。

補足

  • 実際の競技では \(N \le 1000\) 程度でも \(N^2=10^6\) は十分扱えます。
  • ソート後の探索にしゃくとり法（二つのポインタ） を用いると \(O(N^2)\) に改善できますが、問題の要求は \(O(N^2 \log N)\) のため二分探索で十分です。
  • Pythonでは答えが32bitに収まらない場合もあるので、そのまま整数で扱える点も安心です。