競技プログラミングにおいて、C/C++/C#/VB/F#/NemerleでGMPを使う


[Competitive Programming Advent Calendar (2)](http://www.adventar.org/calendars/1165) 12/18
(本記事は12/17午前まで非公開設定でした)

## 前説

- 競技プログラミングでは、まれに言語機能に強く依存する問題が出ることがあります。
- 私の中ではその2大勢力に多倍長整数と正規表現があると思います。
  - Javaを勉強したのはICPCで認められている言語の中で正規表現が使えるのがJavaだけだったからだったりします。

### C/C++

- さて、C++11で正規表現が入りましたが、多倍長整数は入りませんでした。
  - C++1zでも厳しそうです。
- そうすると、多倍長整数を扱うには、自前実装かGMPを使うしかありませんが、できればGMPを使いたいものです。
- しかし、GMPを使うには、ソースでgmp.hをインクルードすることに加え、リンカオプションに-lgmpを加える必要があります。
  - リンカオプションはソースからは操作できないため、難しそうです。
- 動的リンクを使えば良さそうですが、-ldlを付ける方法もありません。

### C# ###

- C#が使えるオンラインコンテストも最近は増えてきました。多倍長実装はSystem.Numerics.BitIntegerがありますが、System.Numeric.dllを参照する必要があります。
- オンラインジャッジ側でこれを参照しない設定になっている場合、コンパイルオプションを変更して参照するのは不可能です。

## 方法

### C/C++

- 幸い、Linuxで標準的なlibcであるglibcにおいては、\_\_libc_dlopen_mode()/\_\_libc_dlsym()/\_\_libc_dlclose()が定義されています。dlopen()/dlsym()/dlclose()の代わりにこれらを呼べば動的リンクが可能です。ただし、ヘッダファイルはなさそうなので、プロトタイプ宣言は必要です。
- libgmpのパスですが、
  - wandbox/yukicoderはCentOS系(64bit)なので、`/usr/lib64/libgmp.so.10`です。
  - AOJはCentOS系(64bit)ですが、少し古いため、`/usr/lib64/libgmp.so.3`です。
      - AOJのgccが5系になったけど、ソースからコンパイルして入れたのかな。
  - paiza.io/atcoder/HackerRankはDebian系(64bit)なので、`/usr/lib/x86_64-linux-gnu/libgmp.so.10`です。
  - ideoneはDebian系(32bit)なので、`/usr/lib/i386-linux-gnu/libgmp.so.10`です。ただしObjCは`/usr/lib/libgmp.so.3`です。統一されてないですね…
      - (ちなみにCodeforcesをcustom invocationで調査しようとしたところランタイムエラーに。system()もdiropen()も潰されているようです。)
- この方法を用いた答案
  - [ABC030D へんてこ辞書](http://abc030.contest.atcoder.jp/tasks/abc030_d)の[答案](http://abc030.contest.atcoder.jp/submissions/585015)
  - [AOJ 0015 National Budget](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0015)の[答案](http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1600527)
  - [CodeIQ マヨイドーロ問題](https://codeiq.jp/q/2549)の[答案](http://ideone.com/38xX75)
- 動的リンクなのでgmpxxが使えないのは残念ですが、C版でも十分戦えると思います。

### C# ###

- P/Invokeで呼ぶことが可能です。
- しかし、mpz_tを定義することができません。今回は32bytesのバッファを割り当てる方法を取りました。Cで言うmalloc()なので面倒です。

- また、まともな出力関数がありません。とりあえず、`/dev/stdout`をfopen()して、その返値に__gmpz_out_str()して、 **fputs()やらfflush()やらでうまくやる** 方法で通りそうです。
  - [ABC030D へんてこ辞書](http://abc030.contest.atcoder.jp/tasks/abc030_d)の[答案](http://abc030.contest.atcoder.jp/submissions/588359)
  - [AOJ 0015 National Budget](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0015)の[答案](http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1605290)
    - Cと(C#では、)gmpのsonameが違うようなので注意
  - [CodeIQ マヨイドーロ問題](https://codeiq.jp/q/2549)の[答案](http://ideone.com/ZZzOKp)

- ご覧のとおり、こってりとしたCです。改良はやりたい方がいましたらお任せいたします。既存のGMP bindingをソースに埋め込める形にするのもありだと思います。

### VB

- [マヨイドーロ答案](http://ideone.com/fOCT3j) (企業版ideoneでは/usr/lib/libgmp.so.3を使う)

### F# ###

- [マヨイドーロ答案](http://ideone.com/lUxuCr) (企業版ideoneは不可)

### Nemerle

- [マヨイドーロ答案](http://ideone.com/E07yxh) (企業版可)
  - ただし、DLL名を定数で取れないようなので実用には厳しいか。

### ヘッダ生成

- [スクリプト](http://ideone.com/iyZLt8)
  - いろいろ手抜きなので、特にC/C#以外で基本型以外のポインタを宣言するとまずいかも。

## 備考
- C/C++において。\_\_libc_dlsym()は、dlsym()と違って、第一引数にNULLを指定できないようなので注意して下さい。
- MinGW系のジャッジ(POJやCodeForces等)ではこの方法は使えないと思います。

## 追伸

- ICPCは非標準ライブラリ不可ですので、くれぐれもやらないようにしてください(そして(日本地区予選はまだ良いとして)海外の地区予選に行く場合は本番で泣かないようJavaも基礎だけは押さえておきましょう)。
- (ライブラリに制限がないコンテストではばんばん使いましょう。)

## 追伸2
- 公開日から分かる通り、記事作成動機は[マヨイドーロ](https://codeiq.jp/q/2549) [(解答集)](https://github.com/cielavenir/codeiq_solutions/tree/master/yuki_hiroshi/q2549/)です。
- <del>ところで、見出しに「\#」を使うと正しくレンダリングされないの、なんとかなりませんか。</del>[norioc氏に方法教えて頂きました](https://twitter.com/norioc/status/677363644028444673)。感謝します。