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

  • 6
    いいね
  • 3
    コメント

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

C#

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

  • また、まともな出力関数がありません。とりあえず、/dev/stdoutをfopen()して、その返値に__gmpz_out_str()して、 fputs()やらfflush()やらでうまくやる 方法で通りそうです。

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

VB

F#

Nemerle

  • マヨイドーロ答案 (企業版可)
    • ただし、DLL名を定数で取れないようなので実用には厳しいか。

ヘッダ生成

  • スクリプト
    • いろいろ手抜きなので、特にC/C#以外で基本型以外のポインタを宣言するとまずいかも。

備考

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

追伸

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

追伸2