NotebookLMを使って、真剣にベイズ推定の問題を解いてみた【1.機械的にjavaへ移植】

はじめに

そもそものきっかけは、ベイズ推定とは何？という程度の知識レベルで、AtcoderのAH030を解こうとすると、適当なロジックで試行錯誤して、時間を浪費したところで大してスコアも伸びずギブアップするだけなので、ゼロから手を動かして知識を得たい。

一方で、従来型の独学での自習は限度があるので、NotebookLMを使うとどのようなメリットがあるのか試してみようかと思いました。

• NotebookLMを初めて使っての気づき【NotebookLM編】
• AHC030に関する気づき
  • 1.機械的にjavaへ移植【この記事】
  • 2.ランダムな占い
  • 3.相互情報量を最大化する占い
  • 4.事後確率とgiveup改良
  • 5.数を絞ったランダムなプール
  • 6.なんちゃってテキスト変換ツールでcppソースをjavaソースに変換
  • 7.java完成版

とっても参考になる題材はこちら→AHC典型解法シリーズ第3弾「ベイズ推定」

AHC030に関する気づき

まず、A - Polyomino Miningを自力で解いて、前提知識が不足している限界を感じてから、AHC典型解法シリーズ第3弾「ベイズ推定」を追っていきました。

ソースファイル名とQiita記事見出しの対応表

#	ソースファイル名	Qiita記事見出し
①	04_all_pool_random_divination.cpp	ランダムな占いを元にベイズ推定で配置を推定
②	03_all_pool_hill_climb.cpp	相互情報量を最大化する占い
③	02_random_pool.cpp	数を絞ったランダムなプールを用いることでM=3以上に対応
④	01_simple_neighbor.cpp	焼きなましで尤度の高いプールを生成
⑤	00_complete.cpp	近傍を工夫した焼きなまし
⑥	10_after_publication.cpp	記事公開後に作った延長戦2位コード

① 04_all_pool_random_divination.cpp

cppのソースは読めるけど、とりあえずNotebookLMでjavaに翻訳してみた。

配列の添字がなくてコンパイルエラーとなる。

• 400ビットに足りるのは64ビット×7個のため、new long[7];なのだけど、BitSetクラスを使えよ。そもそもmaskは使っていないので、とりあえずコメントアウト。

long[] mask = new long; // bitset<400>の代用（必要に応じて）

• input.oilsとstate.topLeftsは配列です。適切に[0]と[1]をつけましょう。

        if (input.m == 2) {
            for (int i0 = 0; i0 <= input.n - input.oils.maxI - 1; i0++) {
                for (int j0 = 0; j0 <= input.n - input.oils.maxJ - 1; j0++) {
                    state.topLefts = i0 * input.n + j0;
                    for (int i1 = 0; i1 <= input.n - input.oils.maxI - 1; i1++) {
                        for (int j1 = 0; j1 <= input.n - input.oils.maxJ - 1; j1++) {
                            state.topLefts = i1 * input.n + j1;
                            OilLayout layout = new OilLayout(input.m, input.n2);
                            System.arraycopy(state.topLefts, 0, layout.topLefts, 0, input.m);
                            layout.volume = input.getVolume(layout.topLefts);
                            pool.add(layout);
                        }
                    }
                }
            }
        }

まるで演習問題ですが、さっと直して、
seed0のテストデータで実行したら、回答できました！　Score = 1327125
なお、M=2以外のデータはpoolに登録しないので、M>2では例外となりますが、もともとそういうものです。

assert(input.m == 2);

M>2でも回答するには、giveupのロジックでも実行すればよいかと。

giveupがギブアップしてる

コンパイルできるけど、そんな処理は書いていません。あはは。

        void giveup() {
            // BFS等で全掘りする処理（省略可）
            System.exit(0);
        }

c++のdeque<pair<size_t, size_t>> queの部分は、Deque<Integer> queかDeque<Point> queにすればよいかと。とりあえず放っておきます。（これが後で困る）

PointクラスがPairクラスに変わってた

ここで気が付いたのですが、最初javaに翻訳したときは、

    static class Point {
        int r, c;
        Point(int r, int c) { this.r = r; this.c = c; }
    }
    static class OilShape {
        int maxI, maxJ;
        List<Integer> coordinateIds = new ArrayList<>();
        List<Point> coordinates = new ArrayList<>();
    }

だったのですが、配列の添字がどうの、List<Integer>とint[]のパフォーマンスがどうの、と、チャットでいろいろ会話した後に、javaに翻訳したところ、こうなってました。

    static class Pair<T, U> {
        T first;
        U second;
        Pair(T first, U second) { this.first = first; this.second = second; }
    }
    static class OilShape {
        int maxI, maxJ;
        int[] coordinateIds;
        List<Pair<Integer, Integer>> coordinates;
    }

うーん。ラッパークラスを避ける点では、Pointクラスにint型2つの方が良かったのだが。

Xorshiftも変わってた

最初04_all_pool_random_divination.cppの時は、

        public boolean genBool(double p) {
            return (Math.abs(next()) / (double) Long.MAX_VALUE) < p;
        }

次に03_all_pool_hill_climb.cpp以降は、

        public boolean genBool(double p) { 
            return (double)(next() & 0x7FFFFFFFFFFFFFFFL) / Long.MAX_VALUE < p; 
        }

に変わっていることに気が付いたのですが。¹
この後、チャットでこの部分について雑談したら、javaのRandomは53ビットですよ。なぜならdoubleの仮数部は53ビットだから、c++の64ビットも、javaの63ビットも、doubleにキャストした時点で有効桁は53ビットと聞いて、へぇーと納得した後に、javaに翻訳したら反映してた。
このとき、pってここで使えるのかと納得。もう一生使うことはないだろう。

        public double random() {
            // 53ビットの精度で[0.0, 1.0]を生成
            return (next() >>> 11) * 0x1.0p-53;
        }
        public boolean genBool(double p) {
            return random() < p;
        }

出来栄えは

seed0からseed99のM=2に限定すれば、すべてスコアが出てました。
なかなか優秀ですな。

② 03_all_pool_hill_climb.cpp

とりあえずNotebookLMでjavaに翻訳してみた。

配列の添字がなくてコンパイルエラーとなる。

まあ当然なのですが、あれれ。
List<Point>がList<Pair<Integer, Integer>>に変わったのが、今度はList<int[]>になって、このブレはいろいろな面でキツイな。

    static class OilShape {
        int maxI, maxJ;
        int[] coordinateIds;
        List<int[]> coordinates = new ArrayList<>();
    }

当然int[2]={r, c}を入れるとかやると、配列の添字が抜ける問題が増えるわけですよ。
os.coordinates.get(j)は配列です。適切に[0]と[1]をつけましょう。

            for (int j = 0; j < size; j++) {
                os.maxI = Math.max(os.maxI, os.coordinates.get(j));
                os.maxJ = Math.max(os.maxJ, os.coordinates.get(j));
                os.coordinateIds[j] = os.coordinates.get(j) * input.n + os.coordinates.get(j);
                os.mask.set(os.coordinateIds[j]);
            }

seed0でYour program has terminated unexpectedly

すんなり動くかと思いきや、seed0で実行すると、1件だけqueryを出して、しばらくして、Your program has terminated unexpectedlyです。
giveupが何も出さずにSystem.exit(0);しているためですが、正直な感想は、これからプログラミングを覚えようという人にとっては、かなり難易度が高いですな。
最低でも、何か出さないと、こりゃ意味不明で何時間も浪費しそう。
giveupをそのまま放っておいたツケで、ここで回収されます。
なお、いきなりSystem.exit(0);しているところは、何ヵ所かありますので、標準エラー出力(System.err)にメソッド名くらい出しておいた方が良いかも。

        void giveup() {
        	System.err.println("giveup");
        	System.exit(0);
        }

seed0の条件はN=15,M=2です。プールサイズをデバッグ出力すると、pool.size=7623でした。もっと数十万とかと思ったら、ショボかった。

seed20に変更

もっと軽いN=10,M=2を探す²と、seed20があり、プールサイズはpool.size=360です。
seed20のテストデータで実行したら、回答できました！クエリ数6回。　Score = 1327125
参考までに、04_all_pool_random_divinationのソースをseed20で実行したらクエリ数21回。Score = 2991399

相互情報量の効果を知るため、pool.get(0).pxIfRの推移を比べてみます。

03_all_pool_hill_climb
pool.get(0).pxIfR=0.002777777777777778
pool.get(0).pxIfR=0.01980946762423068
pool.get(0).pxIfR=0.0747073575523522
pool.get(0).pxIfR=0.20875376533253384
pool.get(0).pxIfR=0.2850241150288851
pool.get(0).pxIfR=0.7048406672370957
pool.get(0).pxIfR=0.9948737108880664

04_all_pool_random_divination
pool.get(0).pxIfR=0.002777777777777778
pool.get(0).pxIfR=0.003995784828418464
pool.get(0).pxIfR=0.0064403348536729
pool.get(0).pxIfR=0.029849378688458453
pool.get(0).pxIfR=0.04953080944424384
pool.get(0).pxIfR=0.06459492430606295
pool.get(0).pxIfR=0.07999701431585149
pool.get(0).pxIfR=0.12907017197399692
pool.get(0).pxIfR=0.15566467351281227
pool.get(0).pxIfR=0.1353384688439395
pool.get(0).pxIfR=0.13100907080631483
pool.get(0).pxIfR=0.1449858156283346
pool.get(0).pxIfR=0.1325359922571048
pool.get(0).pxIfR=0.21266579819882317
pool.get(0).pxIfR=0.3368608345389535
pool.get(0).pxIfR=0.5157665291305915
pool.get(0).pxIfR=0.5191958885753034
pool.get(0).pxIfR=0.744795566118024
pool.get(0).pxIfR=0.7787533316109061
pool.get(0).pxIfR=0.7792201371668382
pool.get(0).pxIfR=0.7450993229154376
pool.get(0).pxIfR=0.8500142637334906

さて、N=15やN=20はどうするんだ、については、予想以上に大変だったので、後回しにします。
理由はロジック本体はjavaでもcppでも同じだが、事前計算とその持たせ方が、java側を最小限の修正でN=20の全列挙が動くようにパッチを当てていったら、最後はcppと全く同じになってしまって、それが結構大変だったのでした。

③ 02_random_pool.cpp

とりあえずNotebookLMでjavaに翻訳してみた。

配列の添字がなくてコンパイルエラーとなる。

もうコピペです。
今回新しくhashが導入されました。
これだけ見ると意味不明ですが、hashesは配列です。
cppを見ると[0]なんですが、この0はtopLeftsの初期値がすべて0のため、hashもすれば0の位置のものを入れてます。

for (OilState os : oilStates) this.hash ^= os.hashes;

実行できたが、なんか違う

さっき相互情報量なるものをマスターしたはずですが、何気にランダム占いに戻ってます。

                // ランダムな占い
                List<Integer> q = new ArrayList<>();
                for (int i = 0; i < input.n2; i++) if (rng.genBool(0.5)) q.add(i);
                if (q.isEmpty()) q.add(0);
                sim.query(q);
                state.addQuery(q);

まあ、重くて間に合わないのでこれは好都合ですが、M>2に対応できたと思いつつ、ランダムで正解できるのは、M=3の一部だけでした。
これはこれで興味深いので、後でスコアの比較をまとめます。

④ 01_simple_neighbor.cpp

とりあえずNotebookLMでjavaに翻訳してみた。

配列の添字がなくてコンパイルエラーとなる。

もうコピペです。
今回は新しいものはありません。

実行できたが、なんか違う

これもコピペです。
こちらもランダム占いですが、まあ焼きなましの作り方を知るにはちょうど良いでしょう。

⑤ 00_complete.cpp

とりあえずNotebookLMでjavaに翻訳してみた。

配列の添字がなくてコンパイルエラーとなる。

ついに大ボス。これは難しいやつ。

まずラムダ式。
ソート対象がList<int[]> listなんですが、中身がint[]{vol, di, dj}です。ソートしたいのはvolなので、[0]が抜けているのですが、個人的には分かりやすいようにクラスを作ってよと思います。

list.sort((x, y) -> y - x);

次になんか同じことを2回代入してますな。
実はswapsの型がint[][][] swapsなんですが、以前はList<int[]>[][]だったので、なんか4次元が3次元に落ちている。
3次元目はvolでソートした最大4つの候補で、さらに4次元目がint[2]={r, c}の座標だったはずなので、int v=r*n+cと扱うことにする。
さらにlist.get(i)はint[3]={vol, r, c}です。
つまり、swaps[a][b][i] = list.get(i)[1] * input.n + list.get(i)[2];です。

for (int i = 0; i < sz; i++) { swaps[a][b][i] = list.get(i); swaps[a][b][i] = list.get(i); }

ちなみに、List<int[]>[][]のときは、List<int[]>相当を持つクラスCellを作り、Cell[][]にしました。

こんどは受ける方が、配列でなくなって、ij/nとij%nでi,jに分かれる。

                int[] d1 = swaps[m2][m1][(int)rng.randRange(swaps[m1][m2].length)];
                int[] d2 = swaps[m1][m2][(int)rng.randRange(swaps[m2][m1].length)];
                int ni1 = (bk2 / input.n) + d1, nj1 = (bk2 % input.n) + d1;
                int ni2 = (bk1 / input.n) + d2, nj2 = (bk1 % input.n) + d2;

実行できたが、なんか違う

今度は山登りによる相互情報量最大の占い生成に戻っているけど、座標が左上からの順番になっている。

⑥ 10_after_publication.cpp

本質的なものは00_complete.cppと変わらないので、省略します。

javaに機械的に移植した後の状態

#	ソースファイル名	説明
①	04_all_pool_random_divination.java	ランダムな占いを元にベイズ推定で配置を推定。M=2のみ対応。
②	03_all_pool_hill_climb.java	相互情報量を最大化する占い。M=2のみ対応、重いのでN=10程度のみ。
③	02_random_pool.java	数を絞ったランダムなプールを用いることでM=3以上に対応。cpp版と異なりランダムな占い。
④	01_simple_neighbor.java	焼きなましで尤度の高いプールを生成。cpp版と異なりランダムな占い。
⑤	00_complete.java	近傍を工夫した焼きなまし。相互情報量を最大化する占いだが、cpp版と異なり固定の順番によるクエリ作成。
⑥	10_after_publication.java	扱いません

javaに機械的に移植した後のスコア一覧

②相互情報量を最大化する占いは、いざ実効すると終わる気配がないので、4秒を超えたらループの深いところで打ち切るようにしました。

                    for (int ij : indices) {
                        if (System.currentTimeMillis() - start > 4000) throw new RuntimeException();
                        q.flip(ij);

⑤近傍を工夫した焼きなましは、相互情報量を最大化しても今は無理なので、ランダムな占いに変えています。

seed	N	M	eps	total	①	②	③	④	⑤
0	15	2	0.01	38	1,327,125	0	1,120,183	1,217,006	1,211,375
1	13	6	0.04	27	0	0	0	0	0
2	13	2	0.07	68	2,417,617	0	1,525,009	3,947,690	1,614,523
3	19	2	0.08	114	2,541,408	0	2,743,853	2,607,167	1,848,280
4	16	8	0.14	94	0	0	0	0	0
5	15	10	0.11	87	0	0	0	0	0
6	10	4	0.15	33	0	0	0	0	0
7	10	5	0.15	45	0	0	0	0	0
8	11	2	0.13	46	4,553,827	0	9,857,608	12,024,170	4,743,748
9	14	2	0.17	41	13,396,970	0	8,773,298	10,126,514	13,059,956
10	10	3	0.13	27	0	0	0	0	0
11	13	8	0.2	55	0	0	0	0	0
12	15	4	0.08	40	0	0	0	0	0
13	16	4	0.11	66	0	0	0	0	0
14	17	7	0.2	111	0	0	0	0	0
15	16	11	0.12	44	0	0	0	0	0
16	16	4	0.06	55	0	0	0	0	0
17	13	3	0.05	73	0	0	3,038,827	3,388,747	3,702,376
18	10	5	0.05	38	0	0	0	0	0
19	20	19	0.11	99	0	0	0	0	0
20	10	2	0.08	41	2,991,399	743,523	4,153,071	3,758,651	2,897,510
21	13	2	0.15	50	7,980,229	0	0	7,336,943	5,145,834
22	12	4	0.17	36	0	0	0	0	0
23	11	4	0.12	44	0	0	0	0	0
24	14	6	0.04	63	0	0	0	0	0
25	13	2	0.2	27	13,247,220	0	0	0	0
26	17	3	0.04	114	0	0	4,596,605	1,922,983	1,494,124
27	12	2	0.2	56	15,117,518	0	10,898,739	0	11,717,488
28	14	3	0.11	78	0	0	0	0	10,209,317
29	16	10	0.1	120	0	0	0	0	0
30	15	9	0.18	54	0	0	0	0	0
31	13	3	0.12	36	0	0	0	0	0
32	16	12	0.04	61	0	0	0	0	0
33	11	5	0.04	45	0	0	0	0	0
34	16	8	0.14	83	0	0	0	0	0
35	10	3	0.17	17	0	0	0	0	0
36	13	8	0.02	70	0	0	0	0	0
37	10	3	0.03	24	0	0	3,277,343	4,336,572	2,832,218
38	13	2	0.06	95	541,775	452,144	3,345,885	2,092,697	2,993,074
39	16	11	0.01	91	0	0	0	0	0
40	16	12	0.11	98	0	0	0	0	0
41	11	3	0.12	29	0	0	0	0	0
42	19	2	0.04	148	1,653,203	0	1,109,013	1,787,503	1,256,680
43	16	9	0.1	88	0	0	0	0	0
44	14	8	0.04	64	0	0	0	0	0
45	15	2	0.07	83	2,185,951	0	2,642,096	2,335,024	2,938,936
46	10	5	0.17	46	0	0	0	0	0
47	16	5	0.1	109	0	0	0	0	0
48	13	8	0.2	66	0	0	0	0	0
49	12	3	0.08	52	0	0	0	6,332,414	7,039,968
50	12	6	0.11	47	0	0	0	0	0
51	13	4	0.06	70	0	0	0	0	0
52	13	4	0.08	39	0	0	0	0	0
53	12	6	0.09	32	0	0	0	0	0
54	11	4	0.02	45	0	0	0	2,852,454	1,000,000,000
55	16	4	0.02	59	0	0	0	3,636,118	3,221,491
56	15	7	0.17	82	0	0	0	0	0
57	17	5	0.02	96	0	0	0	2,910,970	0
58	17	13	0.2	132	0	0	0	0	0
59	13	3	0.13	33	0	0	0	0	0
60	19	5	0.08	130	0	0	0	0	0
61	15	2	0.12	52	9,569,245	0	0	7,995,630	9,167,934
62	14	9	0.1	86	0	0	0	0	0
63	18	10	0.2	101	0	0	0	0	0
64	14	8	0.15	64	0	0	0	0	0
65	14	2	0.03	62	1,325,300	0	1,726,166	1,022,103	1,594,484
66	13	6	0.03	87	0	0	0	0	0
67	15	5	0.19	91	0	0	0	0	0
68	20	2	0.19	190	12,978,748	0	9,281,220	6,741,920	9,584,555
69	12	6	0.02	56	0	0	0	0	0
70	19	10	0.02	105	0	0	0	0	0
71	20	10	0.12	120	0	0	0	0	0
72	14	3	0.12	82	0	0	5,372,519	5,884,358	0
73	14	6	0.19	84	0	0	0	0	0
74	10	4	0.17	43	0	0	0	0	0
75	19	12	0.11	147	0	0	0	0	0
76	13	7	0.01	67	0	0	0	0	0
77	10	3	0.16	52	0	0	8,465,816	0	11,988,096
78	16	4	0.06	71	0	0	0	0	0
79	12	5	0.09	35	0	0	0	0	0
80	13	7	0.13	44	0	0	0	0	0
81	17	4	0.19	118	0	0	0	0	0
82	17	10	0.14	80	0	0	0	0	0
83	13	8	0.18	64	0	0	0	0	0
84	15	7	0.12	64	0	0	0	0	0
85	10	2	0.09	50	3,281,698	712,398	6,306,904	1,553,800	2,124,518
86	10	5	0.14	20	0	0	0	0	0
87	19	5	0.16	94	0	0	0	0	0
88	15	2	0.04	68	2,185,951	0	1,697,288	1,049,056	0
89	17	11	0.04	65	0	0	0	0	0
90	12	2	0.15	49	6,560,898	0	0	0	9,639,037
91	12	7	0.1	42	0	0	0	0	0
92	11	5	0.18	23	0	0	0	0	0
93	10	2	0.05	23	6,292,704	0	7,581,211	4,861,886	3,318,801
94	16	2	0.03	105	892,833	0	1,324,879	946,945	2,412,305
95	14	3	0.2	66	0	0	0	0	0
96	14	3	0.02	54	0	0	2,227,670	2,099,510	2,333,988
97	20	10	0.12	138	0	0	0	0	0
98	13	4	0.07	61	0	0	0	0	0
99	16	7	0.07	55	0	0	0	0	0

これからの方針

①と②を比較すると、②が優秀なのは明らかだが、3件しか実行できない。
まずM=2で②が動くようになることが最優先。

③と④と⑤を比較すると、③と④は微妙だが、⑤はさすがによさげ。
②を改良してまともになった状態で、③、④、⑤に適用して、再度比較する。

ツール群

自分でTesterを動かしたくなったので、同じようにjavaに翻訳する。

入力ジェネレータ(gen.rsとlib.rs)をjavaに翻訳して

もう配列DIJのループと来たら、[0]と[1]。
後はargsですか。先頭は[0]です。
想像はついていたけど、仮に乱数はシードを合わせても違いますな。
マニアックなn*n=totalのようなデータが欲しいとかのときに、改造するかも。

Rustのrand_chacha::ChaCha20Rng::seed_from_u64(seed)とjavaのjava.util.Random(seed)の違いは

Rustの rand_chacha::ChaCha20Rng::seed_from_u64(seed) と Java の java.util.Random(seed) は、どちらもシード値に基づいて乱数系列を生成するものですが、そのアルゴリズムの性質、精度、および生成される数値の互換性において決定的な違いがあります。

ソースコードおよび一般的なプログラミング知識に基づくと、主な違いは以下の通りです。

1. アルゴリズムの種類

• ChaCha20Rng (Rust): 暗号学的疑似乱数生成器 (CPRNG) です。非常に高い品質の乱数を生成し、統計的な偏りが極めて少ないのが特徴です。
• java.util.Random (Java): 線形合同法 (LCG) という古典的なアルゴリズムを使用しています。計算は高速ですが、乱数の質（多次元的な分布など）には弱点があることが知られています。

2. 生成される数値の互換性（再現性）

• 全く異なる系列: 同じ seed 値（例えば 1）を与えたとしても、Rust と Java で生成される乱数の順番や値は全く異なります。
• 入力ジェネレータの影響: AHC030 の公式ツール（Rust製）は ChaCha20Rng を使用して島のサイズ $N$ や油田の形状、ノイズ $e_k$ を生成しています。したがって、Java で java.util.Random を使ってジェネレータを移植しても、公式と同じシード値から同じテストケースを再現することはできません。

3. 内部状態と周期

• ChaCha20Rng: 内部状態が大きく（512ビット）、周期も事実上無限（$2^{256}$ 以上）と言えるほど長大です。
• java.util.Random: 内部状態は 48ビットしかなく、周期も $2^{48}$（約281兆）程度です。競技プログラミングの範囲では十分ですが、暗号学的な安全性を備えた ChaCha20 とは設計思想が異なります。

ローカルテスタ(tester.rsとlib.rs)をjavaに翻訳して

やっぱりargs。でもパラメータ指定が違う気もするが、好きなように直すか。

ビジュアライザ(vis.rsとlib.rs)をjavaに翻訳して

StringBuilderでSVGを出力しているので、使うことはないけど、一番面倒。
int x1 = cx + (d - d) * r, y1 = cy + (d + d) * r;ってなんだよ。
Rustのソースを見た。

ソース置き場

• 01 コンパイルできない状態
• 02 コンパイルを通した状態
  • 00_complete.java 相互情報量を最大化する占い
  • 00_complete_v2.java ランダムな占い

1. なにか気になってMath.abs(Long.MIN_VALUE)を出力したらMIN_VALUE(-9223372036854775808)が表示されます。つまり、(double)Long.MIN_VALUE/Long.MAX_VALUEは-1です。 ↩

2. ダウンロードしたツールのREADME.mdには記載はありませんが、genコマンドに--verboseをつけると、カラムfile,seed,N,M,eps,totalのCSVが出力されます。Rustソースを見て気が付きましたが、--helpでもオプション一覧が出てきます。 ↩