はじめに
そもそものきっかけは、ベイズ推定とは何？という程度の知識レベルで、AtcoderのAH030を解こうとすると、適当なロジックで試行錯誤して、時間を浪費したところで大してスコアも伸びずギブアップするだけなので、ゼロから手を動かして知識を得たい。
一方で、従来型の独学での自習は限度があるので、NotebookLMを使うとどのようなメリットがあるのか試してみようかと思いました。
- NotebookLMを初めて使っての気づき 【NotebookLM編】
- AHC030に関する気づき
- 1.機械的にjavaへ移植
- 2.ランダムな占い
- 3.相互情報量を最大化する占い
- 4.事後確率とgiveup改良
- 5.数を絞ったランダムなプール
- 6.なんちゃってテキスト変換ツールでcppソースをjavaソースに変換【この記事】
- 7.java完成版
とっても参考になる題材はこちら→AHC典型解法シリーズ第3弾「ベイズ推定」
いきさつ
最初はNotebookLMがjavaに変換したソースを元に中を読んで理解していたが、本当にしれっと省略したりの部分が多すぎて、忠実にcppソースをjavaソースに変換してみた。
なんちゃってテキスト変換ツール（非公開）
なんちゃってテキスト変換ツール（非公開）は、cpp言語構文なんかまるで知らない、ただのテキスト置換ツールです。
単にテキストエディタで置換をするといろいろ共通なキーワードがあるので、まとめて置換するだけ。
例えば、boolをbooleanにしたら、gen_boolという関数がgen_booleanに変わってた。まあ、呼べるからいいけど、手で戻した。
cpp仕様を少し吸収するjavaクラス
例えば、pair<double, double>をArrayList<Double, Double>に置き換えれば、同じデータ構造のはずだが、swapsとかネストが深いのでPairIntクラスを用意した。
OilLayoutのvector<uint8_t> volumeがよく見たら8ビット（AIがbyteにしたのはこのためか）なので、List<Byte>にするところ、ByteListクラスを用意した。
このメリットは、volumes[ij + top_lefts[oil_id]] -= 1;みたいな元ある値に加減するみたいなやつが、どうしてもx.set(i, x.get(i) + v)みたいに書かざるを得ないため、x.add(i, v)を作ってやった。
変数
いわゆるグローバル変数。
- Scanner sc : java独自、わざわざ引数に追加しないため。
- long start :
get_time()関数の中でstatic変数を書いているが、javaはメソッド内にstatic変数が書けないため。
関数
いわゆるグローバル関数。
- erf0() : javaに誤差関数がないため近似関数。
以下はcppの関数をそのまま使うため。
必要に応じて、呼び出し回数、呼び出し累計時間を収集するため。
- erf(double a)
- exp(double a)
- isinf(double a)
- log(double a)
- max(int a, int b)
- min(double a, double b)
- min(int a, int b)
- round(double a)
- sqrt(double a)
クラス
いわゆるテンプレートクラスの型を固定したクラス。
- PairDouble : double first,secondを持たせる。
- PairDoubleInt : double first,int secondを持たせる。
- PairInt : int first,secondを持たせる。
compare(PairInt a, PairInt b)を定義。 - BoolList : ArrayList<Boolean> listをラップ。
- BoolListList : ArrayList<ArrayList<Boolean>> listをラップ。
- ByteList : ArrayList<Byte> listをラップ。
- ByteListList : ArrayList<ArrayList<Byte>> listをラップ。
- DoubleList : ArrayList<Double> listをラップ。
- DoubleListList : ArrayList<DoubleList> listをラップ。
- IntList : ArrayList<Integer> listをラップ。
- IntListList : ArrayList<IntList> listをラップ。1
- LongList : ArrayList<Long> listをラップ。
- PairDoubleList : ArrayList<PairDouble> listをラップ。
- PairDoubleListListList : ArrayList<ArrayList<PairDoubleList>> listをラップ。
- PairDoubleIntList : ArrayList<PairDoubleInt> listをラップ。
- PairIntList : ArrayList<PairInt> listをラップ。
- PairIntListListList : ArrayList<ArrayList<PairIntList>> listをラップ。
- LongDoubleMap : HashMap<Long, Double> mapをラップ。
主なcppとjavaの違い
あとはコンパイルエラーとなる部分を修正すると何となく動くが、コンパイルが通っても、同じように動かない部分は以下の通り。
3番目は、javaで例外となるのは分かるけど、なんでcppで問題ないのか、AIチャットに聞くまで、size_t(unsigned int)の存在を忘れていた。
- Xorshiftの中の>>は、符号なしで右シフトするため>>>に変更する。
- Xorshiftの中のuint64_tをlongにしても符号ありなので、符号ビットをクリアする。
- simulated_annealing()でsize_tは負の数にならないが、intにすると負の数となり追加の範囲チェックが必要なので、Integer.MAX_VALUEを足して大きい値にする。
メリット
まわりくどいBoolListを用意したメリット。
getDivinationQueryで普通にboolean[]に置き換えていたら、vector<bool> same(input.n2, true);のtrueで初期化を見逃して、デフォルトのfalseで初期化したら、same[ij] = same[ij] && layout.volume[ij] == pool[0].volume[ij];のsame[ij]が最初からfalseなので、trueに変わることはなかった。
ソース置き場
- 99 cppと同等となる移植
-
当初はArrayList<ArrayList<Integer>> listをラップしたが、iteratorがIntListを返さないと都合が悪い。 ↩