NEPLg2 Standard Library

kpsearch: 競技プログラミング向け探索ユーティリティ

目的もくてき:

ソート済み配列に対する lower_bound / upper_bound を提供します。
「条件を満たす最初の位置」を求める二分探索の雛形を固定化します。

実装じっそう:

配列は i32 の連続領域 (ptr, len) として扱います。
不変条件 lo..hi を保つ標準的な二分探索で実装します。

注意ちゅうい:

入力配列は昇順である必要があります。

TESTstdionormalize_newlines

#entry main
#target std
#import "kp/kpsearch" as *
#import "core/mem" as *
#import "std/stdio" as *
fn main <()*> ()> ():
    let len <i32> 5;
    let data <i32> alloc_raw mul len 4;
    store_i32 add data 0 1;
    store_i32 add data 4 3;
    store_i32 add data 8 3;
    store_i32 add data 12 7;
    store_i32 add data 16 9;
    print_i32 lower_bound_i32 data len 2;
    print " ";
    print_i32 upper_bound_i32 data len 3;
    print " ";
    println_i32 if contains_i32 data len 3 then 1 else 0;
    dealloc_raw data mul len 4

lower_bound_i32: x 以上が最初に現れる位置を返す
upper_bound_i32: x より大きい値が最初に現れる位置を返す
contains_i32: 値 x が存在するか判定する
count_equal_range_i32: 値 x の出現回数を返す

目的もくてき:

ソート済み配列における x の個数を O(log n) で求めます。

実装じっそう:

lower_bound_i32 と upper_bound_i32 の差で個数を計算します。

注意ちゅうい:

配列は昇順である必要があります。

計算量けいさんりょう:

O(log n)

TESTstdionormalize_newlines

#entry main
#target std
#import "kp/kpsearch" as *
#import "core/mem" as *
#import "std/stdio" as *
fn main <()*> ()> ():
    let len <i32> 6;
    let data <i32> alloc_raw mul len 4;
    store_i32 add data 0 1;
    store_i32 add data 4 2;
    store_i32 add data 8 2;
    store_i32 add data 12 2;
    store_i32 add data 16 5;
    store_i32 add data 20 9;
    println_i32 count_equal_range_i32 data len 2;
    dealloc_raw data mul len 4

unique_sorted_i32: ソート済み配列を in-place で重複除去し、新しい長さを返す

目的もくてき:

ソート済み配列を先頭側へ圧縮し、重複を 1 つにまとめます。

実装じっそう:

読み取り位置 read と書き込み位置 write の 2 ポインタで走査します。
data[read] が直前の一意値と異なるときだけ data[write] に書き込みます。

注意ちゅうい:

配列は昇順である必要があります。
返り値 new_len 以降の要素内容は未規定です。

計算量けいさんりょう:

O(n)

TESTstdionormalize_newlines

#entry main
#target std
#import "kp/kpsearch" as *
#import "core/mem" as *
#import "core/math" as *
#import "std/stdio" as *
fn main <()*> ()> ():
    let len <i32> 7;
    let data <i32> alloc_raw mul len 4;
    store_i32 add data 0 1;
    store_i32 add data 4 1;
    store_i32 add data 8 2;
    store_i32 add data 12 2;
    store_i32 add data 16 3;
    store_i32 add data 20 7;
    store_i32 add data 24 7;
    let new_len <i32> unique_sorted_i32 data len;
    println_i32 new_len;
    let mut i <i32> 0;
    while lt i new_len:
        do:
            if gt i 0:
                then print " "
                else ()
            print_i32 load_i32 add data mul i 4;
            set i add i 1;
    println "";
    dealloc_raw data mul len 4

lower_bound_vec_i32: Vec<i32> を対象に lower_bound を返す
upper_bound_vec_i32: Vec<i32> を対象に upper_bound を返す
contains_vec_i32: Vec<i32> に値 x が存在するか判定する
count_equal_range_vec_i32: Vec<i32> における x の個数を返す