C++
VB.Net
C#
C言語
競技プログラミング

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

More than 1 year has passed since last update.

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