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とか。

Maximum Winter-Contest 2011 A: Shopping

keyword

尺取り法　C++

問題概要

長さM(<5*10^4)の文字列MとN(<=8)個の文字が与えられる。Nの文字が全て出現するような区間の最小幅を求める問題。

解法

蟻本に載ってる尺取り法の例題とほとんど同じ。なので詳細は蟻本参照のこと。

続きを読む

Maximum Winter-Contest 2011 B: Who Fired

keyword

平面幾何　C++

問題概要

2次元平面上に、M(<1000)個の点とN(<1000)個の円が与えられる。M個の点が全て周上にあるような円の中心を含む円がいくつあるか求める問題。

解法

M=1, M=2の場合はコーナーケースなので分けて解く(簡単なので略)。M>=3のときは、3点あれば円が決定できる(or円が無いことがわかる)ので後はやるだけ。もしかしたら入力には同じ点が与えられているのかもしれない。

続きを読む

Maximum Winter-Contest 2011 C: Planning a Date

keyword

動的計画法　BruteForce　C++

問題概要

M(<10)人の議員がいて過半数以上の議員を買収しなければならない。各議員には時間の上限(<1000=S)と満足度の下限(<100=P)が与えられる。接待の方法はN(<10)とおりある。それぞれかかる時間、与える満足度、必要なコストが与えられる。総コストを最小化する問題。

解法

M人全ての議員について買収するのに必要な最小コストを前処理で計算しておけば後はBruteForceで解ける。各議員について買収する最小コストを求めるにはdp[使った時間][与えた満足度]としてDPで解ける。
計算量O(2^M + M*S*P*N)。

続きを読む

Maximum Winter-Contest 2011 G: Stacked Rotatable Mazes

keyword

幅優先探索　C++

問題概要

3次元の迷路の最短距離を求める問題。ただし下方向への移動はできず、上方向には特定のマスからしかいけない。また、上に登る前に上の層を任意に回転させることができる。

解法

定石通り幅優先するだけ。サンプルが珍しく親切。

続きを読む

Maximum Winter-Contest 2011

参加していました。
自分が解いた問題の中には、前回の店長の様なトラップは無かったように思う。
AとFは蟻本で勉強したのがほぼそのまま出ていたっぽい。蟻本さまさまである。
GとFはデバッグに大分時間をとられてしまった。しかし多次元のBITを書いたのは初めてだったのでこれ以降はもっとスムーズに書けるようになると思う。
(追記：終了時間勘違いして公開の時期間違えてしまいました。関係者の方申し訳ありませんでした)