Namaran

Code daily. Without assist.

2026-10-21

prefix_count.rs

fn main() {
    let a = [12, 10, 13, 10, 12];
    let mut count = [0; 4];
    for x in a {
        count[x - 10] += 1;
    }
    for i in 1..count.len() {
        count[i] += count[i - 1];
    }
    println!("{count:?}");
}

これは何を出力するでしょうか?

Answer

[2, 2, 4, 5] です。

値は10から13の範囲にあるので、x - 10 で0から3の添字に移し、長さ4の配列で数えます。最初のループのあと、count は10が2個、11が0個、12が2個、13が1個で [2, 0, 2, 1] です。ここで止めると出現回数がそのまま出ますが、2つ目のループが続きます。

2つ目のループは、添字1から順に、1つ前の要素を自分に足します。前の要素はすでに足し込み済みなので、count[i] は「添字 i 以下の値の個数の合計」になります。count[1] は 0 + 2 = 2、count[2] は 2 + 2 = 4、count[3] は 1 + 4 = 5 です。

この累積の個数は、計数ソートで各値を出力のどこに置くかを表します。たとえば12は、12以下の値が4個あるので、並べ替えた結果の4番目までに収まり、11以下の2個のあと、3番目と4番目に置かれます。