int型の除算の結合法則に注意

結合法則に思わぬ落とし穴があることを発見した。（多分、基本ですが・・・）

まずは、この問題を見て下さい。PKUの問題です。

http://acm.pku.edu.cn/JudgeOnline/problem?id=3619

この問題に対して、最初にsubmitした回答がこれ。

撃沈。

int main() {
int N, K;
scanf("%d %d", &N, &K);

int s, t, r;
while(K) {
scanf("%d %d %d", &s, &t, &r);
int ret = 0;
while (ret * s < N)
++ret;
printf("%d\n", ret + r*(ret - 1)/t);
--K;
}

return 0;
}

結構悩んだ後で、気付いたのはここ。

11行目のところ。

計算したかったのは、

しかし、私が求めたかった値を厳密に数学的に記すならば、

である。ここで注意すべきは、

の結合法則は成立するが、int型で小数点以下を切り捨てしている場合は、ソース上では単なる乗算と除算だが数学的にはfloorという演算が入っているため、同様の結合法則が成り立たないということだ。

ここを見落としてしまうと、上の例でr = 3, ret = 11, t =3のとき

を期待して、r * (ret - 1) / tなんてやってしまうと、

と計算されてしまうことになる。。

つまり、思惑通りの演算をするためには、11行をr * (ret-1) /t ではなく、(ret - 1) / t * r にしなければいけなかったのだ。。。

まあかなり基本だけど、ハマってしまうと意外と抜けられない感じなので気をつけましょう。。