雑記：AtCoderでF#を試そうとして色々躓いた

ねおさん / T.A.

概要

関数型言語に興味を持ち
Copilotに色々聞きながらF#で↓を解こうとしたら色々躓き学びを得た話

試したこと

#[allow(unused_imports)]
use proconio::{fastout, input, marker::Chars};

pub fn bin_sch<F>(edge_l: usize, edge_r: usize, mut judge: F) -> isize
where
    F: FnMut(usize) -> bool,
{
    let mut ok: isize = edge_l as isize - 1isize;
    let mut ng: isize = (edge_r + 1) as isize;
    while ng - ok > 1 {
        let mid: isize = ((ok + ng) / 2) as isize;
        if judge(mid as usize) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    ok
}

#[fastout]
fn main() {
    input! {
        n: usize,
        mut l: [usize; n],
    }
    l.sort();
    let mut ans = 0;
    for i in 0..n {
        for j in i + 1..n {
            let a = l[i];
            let b = l[j];
            // c > a - b この時点で a <= b なので無視していい
            // c > b - a この時点で c >= b なので無視していい
            // c < a + b
            let k = bin_sch(0, n - 1, |mid| l[mid] < a + b);
            if k > j as isize {
                ans += k as usize - j;
            }
        }
    }
    println!("{ans}");
}

Rustで上記のように解けるので、F#に変換しようとした

let n = stdin.ReadLine() |> int
let l = stdin.ReadLine().Split() |> Array.toList |> List.map int |> List.sort

let binarySearch leftEdge rightEdge judge =
    let rec binarySearchHelper leftOuterEdge rightOuterEdge judge =
        if rightOuterEdge - leftOuterEdge > 1 then 
            let mid = (leftOuterEdge + rightOuterEdge) / 2
            if judge mid then
                binarySearchHelper mid rightOuterEdge judge
            else
                binarySearchHelper leftOuterEdge mid judge
        else
            leftOuterEdge
    binarySearchHelper (leftEdge-1) (rightEdge+1) judge


let rec solveFirst l cnt =
    let rec solveSecond l a cnt =
        match l with
        | [] -> cnt
        | b :: tail ->
            let judge mid = tail.[mid] < a + b
            let searchRes = binarySearch 0 ((List.length tail) - 1) judge
            let cnt = cnt + if searchRes >= 0 then (searchRes + 1) else 0
            solveSecond tail a cnt

    match l with
    | [] -> cnt
    | a :: tail ->
        let cnt = solveSecond tail a cnt
        solveFirst tail cnt

let ans = solveFirst l 0
printfn "%d" ans

上記のようになったが、TLE

学んだこと

関数の内部で関数を定義

例えば↓の二分探索関数では、関数の内部で関数を定義している。

let binarySearch leftEdge rightEdge judge =
    let rec binarySearchHelper leftOuterEdge rightOuterEdge judge =
        if rightOuterEdge - leftOuterEdge > 1 then 
            let mid = (leftOuterEdge + rightOuterEdge) / 2
            if judge mid then
                binarySearchHelper mid rightOuterEdge judge
            else
                binarySearchHelper leftOuterEdge mid judge
        else
            leftOuterEdge
    binarySearchHelper (leftEdge-1) (rightEdge+1) judge

高階関数（Higher-Order Functions）と呼ばれる概念の一部らしい。
関数型言語において関数は値と同様に扱える？
要調査。

普段AtCoderではRustを使用しており、
そこでは下記のような自作二分探索関数を使用している。
先ほどのF#の二分探索はこれを元にしている。

fn bin_sch<F>(edge_l: usize, edge_r: usize, mut judge: F) -> isize
where
    F: FnMut(usize) -> bool,
{
    let mut ok: isize = edge_l as isize - 1isize;
    let mut ng: isize = (edge_r + 1) as isize;
    while ng - ok > 1 {
        let mid: isize = ((ok + ng) / 2) as isize;
        if judge(mid as usize) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    ok
}

リストのパターンマッチ

F#以外の関数型言語も同様かはわからないが、
リストに対して下記のようなパターンマッチができる

// l はリスト
match l with
| [] -> ()
| head :: tail -> // headはlの先頭、tailはlからheadを除いた残り

これを使ってリスト全体に対して繰り返し操作を行う場合、
例えば下記のような再帰関数でできる

let sum list =
    let rec sumHelper list sum =
        match list with
        | [] -> sum
        | head :: tail ->
            head + sumHelper tail sum
    sumHelper list 0

※度々使用している〇〇Helperという関数名は私が勝手にそうしているだけで、実際にそのように書かれているとは限らない。

List.lengthの計算量について

そもそも大前提としてListは値と次の値へのポインタを持つデータ構造である。
Listはその構造上、特定の位置のデータを取得するためには先頭からポインタを辿る必要がある。
対して、配列やベクタの場合はメモリ上の連続したアドレスにデータを格納する。
メモリ上のデータの開始位置さえわかればそこからの差分を指定することで配列上の特定の位置のデータを取得できる。
つまりlist[i]の計算量はO(i)、array[i]の計算量はO(1)である。

配列やベクタの場合は連続したデータの長さを保持しているため、array.length()の計算量はO(1)。
対してListはそうではないため先頭から末尾までの長さを捜査する必要がある。
list.length()の計算量はO(list.length())

TLEの原因は、↓の処理を何度も呼び出していたから

let searchRes = binarySearch 0 ((List.length tail) - 1) judge

半分くらいRustのベクタみたいなノリで使っていたからListの構造を忘れていた。
基本的にArrayを使うようにすべきかなと思った。

おまけ

最終的にこうなった

let n = stdin.ReadLine() |> int
let l = stdin.ReadLine().Split() |> Array.map int |> Array.sort

let binarySearch leftEdge rightEdge judge =
    let rec binarySearchHelper leftOuterEdge rightOuterEdge judge =
        if rightOuterEdge - leftOuterEdge > 1 then 
            let mid = (leftOuterEdge + rightOuterEdge) / 2
            if judge mid then
                binarySearchHelper mid rightOuterEdge judge
            else
                binarySearchHelper leftOuterEdge mid judge
        else
            leftOuterEdge
    binarySearchHelper (leftEdge-1) (rightEdge+1) judge


let solve (array: int array) =
    let rec solveHelper (array: int array) aIdx cnt =
        if aIdx >= Array.length array then
            cnt
        else
            let rec solveHelperSecond (array: int array) a bIdx cnt =
                if bIdx >= Array.length array then
                    cnt
                else
                    let b = array.[bIdx]
                    let judge mid = array.[mid] < a + b
                    let cIdxMax = binarySearch 0 (Array.length array - 1) judge
                    let cnt = cnt + if cIdxMax > bIdx then cIdxMax - bIdx else 0
                    solveHelperSecond array a (bIdx + 1) cnt
            let a = array.[aIdx]
            let cnt = solveHelperSecond array a (aIdx + 1) cnt
            solveHelper array (aIdx + 1) cnt
    solveHelper array 0 0


let ans = solve l
printfn "%d" ans

いいなと思ったら応援しよう！