gccを使ってコンテストに出る

雑記 小ネタ

大抵のプログラミングコンテストやオンラインジャッジではC/C++が選択できる。しかも大体gccである(もしくは、選べる)ことが多い。なので、gccで書くときに覚えておくと便利、かもしれないことを書いておく。そもそもgccのバージョンやコンパイルオプションによってはコンパイルできなかったりする可能性もあるので積極的に使うものでもないと思うけど。

関数

algorithmをincludeしたときに__gcdが使えるのはかなり役立つ。ただし、long longでは動いたり動かなかったりする様だ(個人的な経験では動くことが多いような)。
stdio.hやstring.hやmath.hに入ってる大部分(自分が把握できてる分については全部)の関数が、__builtin_を先頭に付けるとincludeせずに使える(__builtin_printfとか)。
上に挙げたのは単にincludeすればいいだけなので気にしなくても良いけど、次のビルトイン関数はビット演算に役に立つ。書く手間が省けるだけでなく、実行速度の面でも有利。

  • __builtin_popcount(): 引数のビットがいくつ立っているか返す。多分JavaのInteger.bitCount()と同じ。64bitでは__builtin_popcountll()。
  • __builtin_parity(): __builtin_popcount() のmod 2での値を返す。64bitでは__builtin_parityll()。
  • __builtin_ctz(): 引数をxとする。(x>>i)&1が1となる最小のiを返す。0に対する動作は未定義(ローカルでは32を返した)。JavaのInteger.numberOfTrailingZeros()に似ている。64bitでは__builtin_ctzll()。
  • __builtin_clz(): 引数をxとする。31-((x>>i)&1が1となる最大のi)を返す。0に対する動作は未定義(ローカルでは32を返した)。JavaのInteger.numberOfLeadingZeros()に似ている。64bitでは__builtin_clzll()。
  • __builtin_ffs(): __builtin_ctz()に1を加えた値を返す。0に対しては0を返す。64bitでは__builtin_ffsll()。

文法

  • max(a,b)と同じ用途でa>?bと書ける。普通にmax(a,b)と書くのとと比べて何がありがたいかというと、型が違っていても大丈夫。intとlong longでも意図した通りに動くようだ。当然minに対応するのは<?。演算子の優先順位は知らない( =よりは高いらしい。まあ( )で囲んでおくのが無難 )。TopCoderでは動作確認したけど、ローカルで使えないので多分これは書かない。
  • typeof(x)でxの型になる。
  • a = max(a,b)の代わりにa >?= bと書ける。これも型を気にせず書ける。minに対応するのは <?=。TopCoderでは動作確認。ローカルでは使えないので多分書かない。
  • switchに対してcase文でcase 0 ... 10:みたいに書ける。値が0<=x<=10のとき該当するという意味。ただし範囲は定数でないといけない。そもそもswitch使わない人間なので多分書かない。
  • 0bを付けることによって2進数を表現できる。例えば0b010110=22とか。