最近のgccは気を利かせすぎるようだ

UVAに送信してて思った．

手元ではコンパイル通る（-Wall付きで）のに，向こうではコンパイルエラー．よく見ると必要なライブラリをincludeしてない，ということが最近よく起こりました．

なんで #include<cstdio> が無いのに，何の問題もなくsprintf使えてるんだ…みたいな．

gcc (GCC) 4.1.2 (Ubuntu 4.1.2-0ubuntu4)

使ってるコンパイラはこれですが，こういうのをチェックするオプションって無いんでしょうか．バージョンが違うと，こうも動作が違うものか…．

関係ないけど，UVA369がちょっと面白かった．

組合せ数_NC_Mを出せという話なんですが，5 ≦ N, M ≦ 100．定義通り書くとすると N!/( (N-M)! * M!) を計算するけど， 100の階乗って10の150乗より大きい値（問題文に書いてある）なわけで．

これに対応するには? 任意精度の整数を使えば出来ます．階乗にする数は高々100なので， 1!から100!まで配列に入れといて必要になったら呼び出せば毎回計算せずに済む．あとは定義通りに計算でおkと．

で，多倍長整数を使いたくない場合，というか多分期待されてる回答はこれだと思うのですが．

私も多倍長整数使いたくないので何かいい性質がないかと組合せ (数学) – Wikipedia を読んでたら，ありました．つかこの程度の知識は持っとけと言われるかも．

${}_N \mathrm{C} _M = {}_{N-1} \mathrm{C} _M + {}_{N-1} \mathrm{C} _{M-1}$

ある二つの組合せ数が分かってれば次の一つが計算できると．というわけで次のようなN×Mの表を作ります．

_NC_N=1，_NC₁=nが分かればこれだけ埋められます．問題文にM ≦ Nだと書いてある（組合せ数だからこれは当然）ので，表の左下三角部分だけ埋めれば良い．

ここでさっきの式が使えるわけですね．この表ではNは下方向に，Mは右方向に向かってそれぞれ増えていくので，式を当てはめると，あるセルAの上と左上のセルの値が分かればその和がセルAの値! という話になります．

こんな感じ．上の解法とは違って和しかとらないので簡単．しかも問題文にあるように全ての計算がlongで収まるので多倍長の計算が不要．そしてN×Mは高々10,000でしかなく，和もその半分の回数程度しか計算しないので速い．

長々と書いたけど，おそらくこの問題やるような人であればほぼ確実に知ってそうな気がする．

Equation images by TexClip.

About this entry

You’re currently reading “最近のgccは気を利かせすぎるようだ,” an entry on 数奇な因子