Hangoverふたたび

POJの1003番の問題、Hangover。
http://acm.pku.edu.cn/JudgeOnline/problem?id=1003

テーブルの上に、カードを少しずつずらして重ねていく。カードが崩れないようにするには、枚数が増えるごとにずらす長さを短くしなければならない。

最短コード88B(Cozy Ozy)
http://d.hatena.ne.jp/Ozy/20060104#p1

すっかりプレミア価格になって入手困難になっている「Short Coding ~職人達の技法~」でも解説されている問題だ。

この本の監修のために原稿を査読させてもらったとき、この問題は私のなかでどうも引っかかるものがあった。調和級数の和なのだから、Integral 1/x dx = log x とか近似して、与えられた長さLに対してexp(L + α) - βとか、exp(L)×αとかで表現できたりしないのかな、と。

しかし、ひとつひとつの問題をそれほど時間をかけて検討してられないので、自分を欺き、気がつかなかったことにした。 まあ、この手の本を一冊仕上げるというのは、そういう妥協の上にしか成り立たないのである。

それでも、まあ、3年以上経ったいま、冷静に振り返ると縮むものは縮むのである。

main(float x){for(;scanf("%f",&x),x;)printf("%.f card(s)\n",exp(.422+x)-1);}
としてみると通りました。これで76B。

3年越しの最短コード7XB(Cozy Ozy)
http://d.hatena.ne.jp/Ozy/20090523

折角なので、私も記念パピコsubmit。

http://acm.pku.edu.cn/JudgeOnline/problemstatus?problem_id=1003&orderby=clen&language=-1

私は3年を経て、あの査読の時のもやもや感を払拭できた。

え？72Bのコードを見せろ？いや、それは、もちろんごにょごにょ…。

追記1) そのあとOzyさんが71Bに到達。私が負けじと69B。
追記2) そして、Ozyさんの協力により禁断のテクを発明して64Bに！！
追記3) その直後、Ozyさんが63Bに。さすが！たぶんこれで最短。