この記事は新歓ブログリレー 8 日目の記事です。

こんにちは、23B の @hayatroid です。普段は競プロなどしています。

突然ですが

以下のソースコードは木 DP の例題として知られる EDPC の P 問題 に対する私の提出ですが、どうやらおかしな部分があるようです。main 関数の中身を追っていくと、隣接リストを構築し、行きがけ順で探索し、そのまま ( 帰りがけ順で値を fold せずに ! ) 途中で終わっているように見えます。しかし AC は得られています。いったいどういうことでしょうか ( ソースコードの下に種明かしがあるので考えてみてください ) 。

種明かし

正解は……

• 根付き木の各頂点について、子に Rc<RefCell<親>> を持たせることで、葉から順に drop することが保証される
• その上で、drop 時に子から親に向かって値を fold する処理をねじ込むと、木 DP を実現できる

でした !

( よくわからないという声が聞こえてきたので、以下に詳しい解説をです。)

drop とは

Rust には次のような所有権という概念があります ( the book を参照 ) 。

• Rustの各値は、所有者と呼ばれる変数と対応している。
• いかなる時も所有者は一つである。
• 所有者がスコープから外れたら、値は破棄される。

これにより、main 関数を抜けると、main 関数内の値が drop し、破棄処理が走ります。この破棄処理はオーバーライドでき、今回の例では子が破棄される際に、子から親に向かって値を fold する処理をねじ込んでいます ( 51 ～ 60 行目 ) 。

葉から順に drop させたい

上記の処理をしたとしても、それが葉から順に起こらないようでは、正しい結果が求まりません。

そもそも drop の順番をいじれるの ? というところではありますが、Rust の参照を使うとうまいことできそうです。参照は次のルールを満たします ( the book を参照、参照だけに ) 。

• 任意のタイミングで、一つの可変参照か不変な参照いくつでものどちらかを行える。
• 参照は常に有効でなければならない。

2 番目のルールはいわゆるダングリングポインタを防ぐためで、例えば A が B を参照しているとき、A が drop するより先に B が drop することはない、ということが保証されています。

これより、子が親を参照する形にすれば、親は 1 つでも子がいれば drop しないので、葉から順に drop することが保証されます。

ちなみに、複数の子が 1 つの親の可変参照を持つことは 1 番目のルールによりできませんが、Rc<RefCell<親>> を持つことで似たようなことが実現可能です ( 27 行目 ) 。この辺りの解説は the book などに委ねます。

まとめると

全体としては以下のような処理を行っています。

• main 関数内で、子に Rc<RefCell<親>> を持たせる。
• main 関数を抜けると、根付き木の各頂点のうち葉から drop していき、以下の破棄処理を呼び出す。
  • 子から親に向かって値を fold していく。
  • 最終的に根が drop するときには答えを出力する。

処理のほとんどが main 関数外なのと、帰りがけ順で値を fold していく部分 ( drop する順番の決定 ) を Rust の所有権システムに委ねているのがこのプログラムの面白いポイントだと思います。

おわりに

実用性はなさそうです ( 泣 )

新歓ブログリレー、明日の担当は @beferia さんです ! お楽しみに !