Dividing(2)

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

• おもくそインチキですな。

前回掲載したコードを見て、「インチキコードじゃーん」と思った方はエライ。その通りまったくイケてないコードです。アルゴリズムは、単に価値の値を合計し奇数なら当然アウト、偶数なら価値合計のちょうど半分になる可能性を、すべての組み合わせについて再帰的に探索しているだけです。この方法では、20000なんて入力値に耐えられるはずがないのですが、Discussionで「入力値のmod 30で計算しても通ったYO!」という記述を見つけたので、それをパクったわけです。Discussionでも指摘されている通り、mod 30では、

31 0 1 2 0 0

のような入力では間違いになってしまいます。まあ、その場合はmod 30ではなくmod 50とかもうちょっと大きな数にすれば良いのですが、インチキコードには変わりありません。何度かSubmitしてみたところ、テストケースがかなりいい加減のようでいくらでもインチキできることがわかりました。ということは、短いコードを通す事自体はあまり意味の無い事のように思えます。論理的に穴の無い、かつ高速なアルゴリズムを考える事が重要でしょう。