More than 5 years have passed since last update.

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

Last updated at 2016-09-21Posted at 2015-12-17

Competitive Programming Advent Calendar (2) 12/18
(本記事は12/17午前まで非公開設定でした)

前説

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

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

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

幸い、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()も潰されているようです。)
この方法を用いた答案
動的リンクなのでgmpxxが使えないのは残念ですが、C版でも十分戦えると思います。

P/Invokeで呼ぶことが可能です。
しかし、mpz_tを定義することができません。今回は32bytesのバッファを割り当てる方法を取りました。Cで言うmalloc()なので面倒です。
また、まともな出力関数がありません。とりあえず、/dev/stdoutをfopen()して、その返値に__gmpz_out_str()して、 fputs()やらfflush()やらでうまくやる 方法で通りそうです。
- ABC030D へんてこ辞書の答案
- AOJ 0015 National Budgetの答案
  - Cと(C#では、)gmpのsonameが違うようなので注意
- CodeIQ マヨイドーロ問題の答案
ご覧のとおり、こってりとしたCです。改良はやりたい方がいましたらお任せいたします。既存のGMP bindingをソースに埋め込める形にするのもありだと思います。

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