CodinGameでバイナリデータを扱いたい時ありますよね。ニューラルネットワークとか。
ソースコードで提出しないといけないので、バイナリデータを何らかの方法でテキスト形式に変換して埋め込んでおき、実行時にバイナリデータに戻すといった手順が必要になります。
バイナリデータをテキスト形式に変換する方法で有名なものにBase64がありますが、CodinGameにおいてはもっと良い方法があります。
Base64
まずBase64とは、バイナリデータを64種類の文字で表現する方法です。
手順
- バイナリデータを先頭から6bit読み取る
- この6bitを整数とみなすと0～63の値になる
- 値に対応する1文字を出力（変換テーブルを用意しておく）
- 1～3をバイナリデータなくなるまで繰り返す
※最後の6bitに満たないとこだけ特殊処理必要
という感じ（64進数に変換してるようなもの）
Base32768
CodinGameのコード長制限は恐らくUTF16で10万文字（2022/7/5 bowwowforeach調べ）
つまり'a'も1文字だし、'あ'も1文字だし、'犬'も1文字としてカウントされます。
使える文字を調べた結果55000文字ほどありました（サロゲートペアは良く分からんので除外）
このことからBase32768というのがデータ量効率、実装の手軽さで良さそうです。
手順
- バイナリデータを先頭から15bit読み取る
- この15bitを整数とみなすと0～32767の値になる
- 値に対応する1文字を出力（変換テーブルを用意しておく）
- 1～3をバイナリデータなくなるまで繰り返す
※最後の15bitに満たないとこだけ特殊処理必要
☆使える文字が55000あるので、55000進数変換すればもう少しデータ量効率は良くなるはず。処理時間や実装の手間と相談。
使える文字が連続している場所（文字コード）はこちら。（間違ってたらごめんなさい）
- 0x3220 ～ 0x4DB4
- 0x4DC0 ～ 0x9FEE
- 0xAC00 ～ 0xD7A2
これで39274文字あるので十分足ります。
UltimateTicTacToeでニューラルネットワークを埋め込んだらこんな感じ。
以上です。
