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

これは Competitive Programming （その2） Advent Calendar 2015 の7日目の記事です。

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日目の担当' は決まっていません。

CODE FESTIVAL 2015 参加記

N日目(N<0)

本戦・短縮王・リレーの問題準備をする。 短縮王をテストプレイしたら徹夜だった。

短縮王の順位表を宇宙ツイッタラーさんに依頼する。

0日目

スタッフで前夜祭をする。

1日目

朝

5時起床に失敗して若干TLEする。

リハをする。 徐々に目が覚めてくる。

選手が到着したので雑用をする。

ネットワークトラブルが発生する。 できることがないので早く解消してくれ〜と祈る。

本戦

解説スライドのチェックをしたり短縮王ランキングのチェックをしたり書道コーディングしたり雑談したりする。

個別指導塾

あんまり人が来ないので、雑談しに来た人に強引に解説したりする。

エキシビション

ボドゲしてた。

夜

僕「リレーの説明の打ち合わせしたいんでそっちの部屋に行っていいですか」

y3「ok」

〜2分後〜

部屋を尋ねる。

y3「(˘ω˘)ｽﾔｧ」

僕「!?」

しょうがないので打ち合わせは明日することにして短縮王の提出を眺めたりする。

2日目

朝

4時起床。 短縮王のC言語部門のジャッジ解を整理する。 C問題のehaさんの解を1バイト縮める。D問題のジャッジ解を2バイト縮める。

短縮王の順位表の修正を依頼する。

あさプロ

リレーの説明の原稿を作ってた。

昼

shinhさんがいらしたので最短コードとか表彰とかの打ち合わせをする。

リレー準備

今回の最大の佳境。

問題文が印刷されていないことが発覚する。 JAG夏合宿2日目のCSSを流用してその場で印刷用問題文を作る。

設営の人手が足りないと言われたのでディスプレイの設置とかをする。

コンテストの設定あってるかな〜とぼんやり眺めてたら、待機スペースのPCが管理者権限でコンテストにログインしてたのであわててけんしょーさんを呼ぶ。 正しいIDでログインしなおす。

選手が入場してからチーム番号の1〜20とA〜Tが対応していないことに気づき大移動をしてもらう。 そういえば打ち合わせで断片的に聞いた気がする…。

リレーの説明をする。それなりに笑いをとれたのでまぁ良し。

印刷された問題文が届かない。自分がやるべきだなぁと思ったのでスタッフ間の連絡役をやる。インタビューで時間が持たなくなったら何しようかなぁと考える。

リレー

問題文が届いたので15分遅れで開始。

システムがちゃんと動いてそうで安心する。

みんながわいわい問題を解いてるのを眺める。

あまりに解かれる速度が速いので、頼む〜詰まってくれ〜と祈る。

祈りが通じず40分すぎに全完がでる。マジかよ。

MVTを決めるとかいう無茶ぶりな仕事をこなす。

バタバタしたけど無事終了。表彰式をやる。

表彰式

大量のクリーナーを押し付ける。

きゅうりは天才。

打ち上げ

頼んでもないのに突然運ばれてきてびっくりする。

感想

めっちゃ楽しかったです。

リレーでめっちゃトラブったのは申し訳なかったけど、トラブルを収束させるの好きなので楽しかった。

短縮王はshinhさんがガッツリ解説してくれるなら、もっとマニアックな問題にすればよかったかなぁと思った。ショートコーディング初めての人でも、がんがん縮むから楽しいかなぁと思って問題作ったけど、どうなんだろう。

おまけ