1日9時間寝たい

本当は10時間寝たいです

LCA (Lowest Common Ancestor; 最近共通祖先) がバグっていた

はじめに

ダブリングで LCA を求めるスニペットがバグっていました。Library Checker で AC したので大丈夫かと思っていたのです。

バグに気づけなかった理由は木の入力形式だとわかりました。

親の親の親の……

復習です。

ダブリングにより根付き木の LCA を求めるアルゴリズムでは、前計算として、木の各頂点 $v$ と $i = 0, 1, 2, \dots$ について

$f(i, v)$: 頂点 $v$ から根方向に $2^i$ 回辺を辿った頂点

を求めます。たとえば $f(0, v)$ は $v$ の親です。*1

さて、$v$ から 根へ $2^i$ 回辺を辿ることは「$v$ から $2^{i - 1}$ 回辺を辿った頂点 = $f(i - 1, v)$ から $2^{i - 1}$ 回辺を辿ること」と同じです。したがって漸化式は次のようになります。

$$ f(i, v) := f(i - 1, f(i - 1, v)) $$

$f(i, v)$ を求めるには、たとえばボトムアップ的に $(i, v)$ の昇順に計算すればよいです。

for (int i = 1; i < lg; i++) {
    for (int j = 0; j < n; j++) {
        anc[i][j] = (anc[i - 1][j] == -1) ? -1 : anc[i - 1][anc[i - 1][j]];
    }
}

https://github.com/yosupo06/library-checker-problems/blob/master/graph/lca/sol/correct.cpp

このように実装すれば、$f(i, v)$ を求める際に $f(i - 1, \ast)$ が確定しているため、$f(i - 1, f(i - 1, v))$ が正しく計算されます。

木の入力形式によってはバグに気づけない

Library Checker の LCA https://judge.yosupo.jp/problem/lca では木が次の形式で与えられます。

N
p[1] p[2] ... p[N-1]

p[i] は頂点 $i$ の親を表し 0 <= p[i] < i を満たします。

このとき、$(v, i)$ の昇順に $f(i, v)$ が計算できてしまいます。実際、頂点 $v$ の祖先はすべて $v$ 未満なので $f(i - 1, v) < v$ より $f(i - 1, f(i - 1, v))$ が正しく計算されます。

したがって外側のループと内側のループを入れ替えても正しく動きます。(提出)

for (int j = 0; j < n; j++) {
    for (int i = 1; i < lg; i++) {
        anc[i][j] = (anc[i - 1][j] == -1) ? -1 : anc[i - 1][anc[i - 1][j]];
    }
}

もちろん、木が次の形式で与えられる場合はうまくいきません。たとえばこの問題です。

N
a[1] b[1]
a[2] b[2]
︙
a[N-1] b[N-1]

*1:$i$ が大きい場合は根を飛び越してしまうので、そのような場合は実装上 $f(i, v) = -1$ や $f(i, v) = \infty$ とすればよいです。

FParsec の使い方メモ

はじめに

この問題 を FParsec で解いたので使い方をメモ。

問題概要としては

1 plus 2 plus 3 plus 4

のような入力から 10 を得たい、というもの。

FParsec

F# のパーサコンビネータライブラリです。「string を parse する」「integer を parse する」などの部品が組み合わせやすい形で用意されていて、いちから自分で再帰下降するより (慣れれば) 速くパーサを作れます。

日本語の資料では

が詳しい。

英語でもよいなら、最初に チュートリアル を読んで詳しいところは リファレンス を漁るのがいいと思います。

結果

最終的なソースコードです: https://gist.github.com/ia7ck/ade36d8f909c429a9034b04c9cec8ca8

詳しい実行手順は下のほうに書きます。(書きました: 実行手順)

数値の parse

数値を parse するところから始めましょう。pfloat が使えます。

この関数はパーサを返して、その型は Parser<float,'u> です。1 つ目の型引数 float がパースして得られる値の型です。パースを実行するには run に parser と入力文字列を渡します。何度も使うので実行結果を確認しやすいように以下に示す test を用意しておきましょう (チュートリアルに出てくるものとまったく同じです) 。

let test p str =
    match run p str with
    | Success(result, _, _)   -> printfn "Success: %A" result
    | Failure(errorMsg, _, _) -> printfn "Failure: %s" errorMsg

詳しい説明は省きますが、パースに成功すると Success: ... の形で結果が出力されて、失敗すると Failure: ... と出力されます。

test pfloat "1.23" // Success: 1.23
test pfloat "a1b2c3" // Failure
空白の parse

数値をパースできるようになりましたが、このままでは少し使い勝手が悪いです。先頭に空白があるとパースに失敗してしまいます。

test pfloat "  1.23   " // Failure

前後の空白を消費するように変更しましょう。中置演算子 (二項演算子) (>>.), (.>>) が使えます。p1 >>. p2 も p1 .>> p2 も p1 → p2 の順でパーサを適用しますが、run を実行して得られる結果は . がある側です。ドットが無い側のパース結果は無視です。

連続する空白をパースするには spaces が使えます。

// Parser<float,unit>
let number = spaces >>. pfloat .>> spaces
test number "1.23" // Success: 1.23
test number "  1.23   " // Success: 1.23

number の型は pfloat と同じで Parser<float, 'u> であることに注意してください。

文字列の parse

次は plus をパースすることを考えます。Parser<string,'u> を返す pstring が使えそうです。いいえ、plus をパースして文字列の "plus" が得られても何もうれしくありません。私たちは足し算をしたいのでパース結果は足し算を表す関数: 引数が float, float で返り値が float になるべきです。

// float -> float -> float
let plus (a: float) (b: float) = a + b

stringReturn は stringReturn str result の形で使えます。文字列 str をパースし Parser<resultの型, 'u> を返します。

// Parser<(float -> float -> float), unit>
let opPlus = spaces >>. stringReturn "plus" plus .>> spaces
足し算の parse

数値・plus・数値 の順にパースすればよいです。ただし >>. や .>> は適しません。p1 >>. p2 は p1 のパース結果を捨ててしまうからです。それぞれのパース結果を利用して新しいパーサを返すには pipe3 を使います。

// Parser<float,unit>
let xPlusY = pipe3 number opPlus number (fun x op y -> op x y)
test xPlusY "1 plus 2" // Success: 3.0
test xPlusY "1 plaz 2" // Failure

pipe3 p1 p2 p3 f は p1, p2, p3 をパースしてその結果を f に渡します。f では 1 plus 2 を plus(1, 2) のように並び替えればよいです。

足し算の parse (複数回)

ここまでで 1 回の足し算をパースして計算結果を得ることはできました。最後のステップです。私たちは (ちょうど 1 回ではなく) 好きな回数だけ足し算を実行したいです。そのためには次の形の入力をパースする必要があります。

  • 1
  • 1 plus 2
  • 1 plus 2 plus 3
  • 1 plus 2 plus 3 plus 4
  • ...

このような p (op p)* のパターンには chainl1 が使えます。これは p によるパース結果の列を op で左から fold した値を持つパーサを作ります。たとえば 1 plus 2 plus 3 plus 4 から plus(plus(plus(1, 2), 3), 4) を計算します。

let manyPlus = chainl1 number opPlus
test manyPlus "1 plus 2 plus 3 plus 4" // Success: 10.0

できました！

実行手順

手元で実行してみたい人向けです。

【競技プログラミング】Rust でグリッドグラフの走査

まえがき

競技プログラミングで、グリッドグラフが与えられて、隣接 4 マスに移動できる設定はよくあります。 そのときは以下のようなプログラムを書くことになると思います。くわしくはこの問題 https://atcoder.jp/contests/abc007/tasks/abc007_3 を見てください。

q = queue()
q.push((si, sj))
while len(q) > 0:
    i, j = q.pop()
    for di, dj in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        ni, nj = i + di, j + dj
        if (ni, nj) が範囲内 && (ni, nj) が空きマス:
            # 何かする
            q.push((ni, nj))

上の問題の Python3 での回答例です: Submission #17943325 - AtCoder Beginner Contest 007

一方、Rust での回答例がこちらです: Submission #17943842 - AtCoder Beginner Contest 007
以下は隣接マスの走査パートを抜き出したコード片です。

  • isize と usize との演算・比較はできない
  • スライス a に対して a[x] としたいとき x は usize 型でないといけない (isize だとダメ)

という理由で型キャスト as isize, as usize を無限回書く必要があり、つらいです。

let dydx = [(-1, 0), (0, -1), (1, 0), (0, 1)];
let mut q = std::collections::VecDeque::new();
// ...
while let Some((y, x)) = q.pop_front() {
    for (dy, dx) in &dydx {
        let ny = y as isize + dy;
        let nx = x as isize + dx;
        if 0 <= ny && ny < R as isize && 0 <= nx && nx < C as isize {
            let ny = ny as usize;
            let nx = nx as usize;
            if a[ny][nx] == '.' && d[ny][nx] == -1 {
                // ...
            }
        }
    }
}

隣接マスを走査するライブラリ

「移動先のうち、グリッドの範囲内に収まるマス」を列挙するパートはライブラリ化しておきましょう。

Adjacent::new に

  • 現在位置の座標
  • グリッドの高さ (縦方向のマスの個数)
  • グリッドの幅 (横方向のマスの個数)
  • 移動先の座標との差分 (移りたいマスへのベクトル) 列

を渡します。

let dydx = [(-1, 0), (0, -1), (1, 0), (0, 1)];
let mut q = std::collections::VecDeque::new();
// ...
while let Some((y, x)) = q.pop_front() {
    for (ny, nx) in Adjacent::new((y, x), R, C, dydx.iter().copied()) {
        if a[ny][nx] == '.' && d[ny][nx] == -1 {
            // ...
        }
    }
}

ソースコードの全体は Submission #17944643 - AtCoder Beginner Contest 007 を見てください。