6
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

posted at

updated at

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

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
6
Help us understand the problem. What are the problem?