Dividing(3)

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

• 高速・低消費メモリのアルゴリズムを考える

入力値の剰余を使う方法は、テストケースによっては間違いになることがわかりましたが、それではこんな方法はどうでしょう。
結局、2人で均等に分けられない可能性があるのは、おはじきの個数に奇数が現れたときです。たとえば価値が6のおはじきが奇数個あると、2人で分けたときの価値の差は6になります。この、6の差を埋めるためには他の価値のおはじきがいくつか必要で、たとえば1と5とか、2が3個とか、組み合わせはたくさんあります。しかしおはじきの個数にだけ注目すれば、おはじきの必要個数が多い場合でも、せいぜい1が6個です。価値の差を埋めるために必要なおはじきの個数は、1ばかりの場合を考慮しても6個は超えないということになります。
もし、奇数個が6だけじゃなくて5もだったら必要なおはじきが6個を超えるんじゃないか？と一瞬思ったりもしますが、その場合は(6)と(5,1)のように価値が1のおはじきが1個だけあれば等分可能ですから、やはり6個は超えないだろう*1ということになります。
というわけで、入力値が大きい場合は剰余を求めるのではなく、

6を超えた場合、偶数はすべて6・奇数はすべて5

とすれば、必要な計算量が少なくて済みそうです。

*1:とはいえ、数学的に証明しているわけではないのでちょっとアヤシイかも^^;