Factorization 終了
Factorization 終了。この問題は、2次式の因数分解のつもりで作った問題。自分で作った問題に参戦するのは、なんだかちょっとうしろめたい気がするな。もちろん、いんちきしているつもりは無いけど。
解法には大きく 2 通りのアプローチがある。2 次方程式の根の公式を用いるものと、ブルートフォース攻撃によるもの。私の扱っている言語では、C と awk では前者が、JavaScript、Groovy、GolfScript、C++、vi では後者が有利だったようだ。
C
nai さんが、79Bを決めてトップ。79B〜82Bまで、数人がばらけたが、nai さんの解は、全てのいいとこ取りをしたような最良解だった。
nai さん含め何人かの方が、2 項の和の半分を求めるところを、片方の項を +1 して、それぞれを 2 で割ってから和を取るようにして 1B 稼いでいる。これは、思いもしなかった。sqrt()の中に 2 で割る部分を突っ込むとバイト数が稼げるのは分かっていたが、整数の切捨てを避けるために、浮動少数点数化するとやはり 80B になり縮まない。
//80B
main(a,b){for(;~scanf("%d %d\n",&a,&b);)printf(""-6,a-b,b=a*.5+sqrt(a*a/4.-b));}
これが、
b=sqrt(a*a/4-b)-~a/2
と書けるとは。
整数 n, m の和 (n+m) を 2 で割った結果が整数になるには、n, m ともに偶数か、ともに奇数でなければならない。ともに偶数ならば、各項を 2 で割ってから和をとっても良い。ともに奇数の時は、各項を 2 で割ってから(整数除算)和をとると、各項における切り捨てのため 1 足りなくなる。そこをうまく調整している。こんなのなかなか思いつけないなぁ。
それから、C のブルートフォース版は、
i;main(a,b){for(;i=scanf("%d %d\n",&a,&b)/2;printf(""-6,-i,a))for(;--i*a+b;)a--;}
i;main(a,b){for(;i=~scanf("%d %d\n",&a,&b)/3;printf(""-6,i,a))for(;++i*a-b;)a--;}
a,b;main(i){for(;~scanf("%d %d\n",&a,&b);printf(""-6,i,a))for(i=0;i*a-b;a--)i++;}
こんなのができたが、どれも、81B で頭打ち。おしいんだけどな。因みに、C++版は、sqrt() の宣言が必要になるので、ブルートフォースの方が短くなる。
