増井技術士事務所さんがCodeIQで出題されていた「今週のお題:番号の対応表で作るグループ」をRubyで解いてみました。
問題の内容および解法は@angel_p_57さんの素敵な記事を参照していただくとして、参加人数が$m$人のときのグループ数の期待値は第$m$調和数(調和級数の第$m$部分和)になることが分かれば、あとは指定された期待値を超える$m$を見つかればよいのでした。
よって、解答のコードは以下のようになります。
codeiq.2928.rb
i=s=0;n=gets.to_i;until s>n;i+=1;s+=1.0/i;end;p i
また、第$m$調和数は$\log m+\gamma \ (\gamma:Euler-Mascheroni \ constant)$で近似できることが知られているので、期待値$n$をこれが超えるような最小の$m$は、
m= \lfloor\exp(n-\gamma)\rfloor+1
とすることで、$O(1)$で答えを見つけることができます。
今回は用意されていた期待値のテストケースがせいぜい6までだったので、以下のようにちょっとずるをして書くことができました。
codeiq.2928.approximation.rb
p Math.exp(gets.oct-0.577).round
その他の言語での解答
$n=8$までは正常に動きます。
いろんな言語でgolfしてみようかと思ったけど、HardCodeしたほうが短く書けるという、、、
C
codeiq.2928.c
float s;main(i,n){scanf("%d",&n);while(s<=n)s+=1./i++;printf("%d",i-1);}
codeiq.2928.approximation.c
main(n){scanf("%d",&n);printf("%d",lround(exp(n-.577)));}
D
codeiq.2928.approximation.d
import std.stdio;import std.math;int n;void main(){readf("%d",&n);write(round(exp(n-.577)));}
Go
codeiq.2928.approximation.go
package main;import(."fmt";."math");func main(){n:=.0;Scan(&n);Print(int(Exp(n-.577)+.5))}
Haskell
codeiq.2928.approximation.hs
main=do
n<-readLn
putStr.show.round.exp$n-0.577
PHP
codeiq.2928.approximation.php
<?=round(exp(fgets(STDIN)-.577));
Perl
codeiq.2928.approximation.pl
print int exp(<>-.577)+.5
Python
codeiq.2928.approximation.py
print int(2.718**(input()-.576)+.5)
R
codeiq.2928.approximation.r
cat(round(exp(scan("stdin")-.577)))
Scala
codeiq.2928.approximation.scala
import scala.math._;object Main extends App{println(round(exp(readInt-.577)))}
Bash
codeiq.2928.approximation.sh
awk '{print int(exp($1-.577)+.5)}'</dev/stdin
JavaScript(spidermonkey)
codeiq.2928.approximation.spidermonkey.js
print(Math.round(Math.exp(readline()-.577)))