短縮王「割り算と足し算」解説（C言語部門）

CODE FESTIVAL 2015の短縮王で出題した「割り算と足し算」のC言語部門の解説です。

この問題のC言語部門で1位を獲得した ehaさんのコードを元に解説します。

n;f(x,i){n=++i>x?:fmax(f(x%i?0:x/i,1)+x/10+x%10,f(x,i));}
main(){n=scanf("%d",&n)/printf("%d\n",99/n?f(n,1):19);}

(112byte)
(表示の都合上、改行を入れています。以下同様。)

ehaさんのコードの特徴は i についてのループを回す代わりに再帰で処理している、という点です。
この発想がないと、なかなかコードが縮みません。
ジャッジ側が用意していた解答もループを回すものだったので、ehaさんの解答はなかなか衝撃的でした。

さて、この解は x/10+x%10 の部分が余分なので1byte削ることが出来ます。
また、入力が100の場合のために処理を分ける必要もありません。

n;f(x,i){n=++i>x?:fmax(f(x%i?0:x/i,1)+x-x/10*9-x/100*9,f(x,i));}
main(){n=scanf("%d",&n)/printf("%d\n",f(n,1));}

(111byte)

CODE FESTIVAL中にはここまでしか縮みませんでした。
後日、さらに頑張るとまだまだ無駄があることがわかりました。
まずは、この問題の全言語部門で2位を獲得した hirokazuさんのコードを参考にすると3byte縮みます。

n;f(x,i){n=++i>=x?:fmax(f(i,x%i*x)+x-x/10*9-x/100*9,f(x,i));}
main(){n=scanf("%d",&n)/printf("%d\n",f(n,0));}

(108byte)

ずいぶんスッキリしましたが、x-x/10*9-x/100*9 はいかにも縮みそうな気配がします。
この式は x/10*9+x/100*9 → (x/10+x/100)*9 → x/10*11/10*9 という変形をすると2byte縮めることが出来ます。

n;f(x,i){n=++i>=x?:fmax(f(i,x%i*x)+x-x/10*11/10*9,f(x,i));}
main(){n=scanf("%d",&n)/printf("%d\n",f(n,0));}

(106byte)

これが現在見つかっている最短コードです。
まだまだ縮みそうな気がしてきますね。
そう思った人は頑張って考えてみましょう。

さて、明日は

動作を停止しました。'8日目の担当' は決まっていません。