bouzuya.hatenablog.com

ぼうずやのにっき

React Native から WASM を使ってみた / ABC190 F を解いた

bouzuya/kireta で WasmContextProvider を抜き出した。 React Native で WASM を使うための仕組みの一部。 WebView (onMessage と postMessage) 経由で WASM の関数を呼び出す。呼び出し元 (React Native 側) には Promise を返しておいて、 onMessage で解決するようにしているのですべて Promise を返すようになってしまうけど、今回のユースケースだとこれくらいで妥協して良さそう。

https://github.com/bouzuya/kireta/commit/a0913763e6f3bc1fab998ec566ad7fe2a898220d

以下は使用イメージ。

import { useCallback, useState } from "react";
import { Button, Text, View } from "react-native";
import { WasmContextProvider, useWasm } from "./components/WasmContextProvider";

function MyApp(): JSX.Element {
  const { call } = useWasm();
  const [count, setCount] = useState<number>(0);
  const handleOnPress = useCallback((): void => {
    (async () => {
      const result = await call("add", [count, 1]);
      setCount(result as number);
    })();
  }, [count]);
  return (
    <View>
      <Text>{count}</Text>
      <Button onPress={handleOnPress} title="Increment" />
    </View>
  );
}

export default function App(): JSX.Element {
  return (
    <WasmContextProvider uri="http://example.com/">
      <MyApp />
    </WasmContextProvider>
  );
}

http://example.com/ にしている箇所ではメッセージを処理するための HTML を指定する。 WASM を埋め込んでしまえば外部通信は不要なのだけど、逆に外部から更新可能なほうが都合が良いのでは……などと想像している。

  • Shift and Inversions (AtCoder Beginner Contest 190:F問題) https://atcoder.jp/contests/abc190/tasks/abc190_f
    • https://atcoder.jp/contests/abc190/submissions/45085361
    • 転倒数を N 回求めると間に合わない
    • 0..N の並び替えであることを考えると転倒数を求めるのは初回のみで良いことが分かる
    • 左にローテートするごとに左端の数字よりも大きい数字分だけ転倒数が増え小さい数字分だけ転倒数が減る
    • あとは転倒数を Segtree や FenwickTree などで求めれば良い
    • 書籍に合わせて Segtree で解いた
    • なぜか解けるなと思ったら 2023-08-13 とつい 2 週間ほど前に解いていた
use proconio::input;
use segtree::*;

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    }
    let mut count = 0_usize;
    let mut segtree = Segtree::<Additive<usize>>::new(n);
    for (i, a_i) in a.iter().copied().enumerate() {
        segtree.set(a_i, 1);
        count += i - segtree.prod(0..a_i);
    }
    println!("{}", count);
    for i in 0..n - 1 {
        count += n - 1 - a[i];
        count -= a[i];
        println!("{}", count);
    }
}

// segtree

今日のコミット。