nekoTheShadow’s diary

IT業界の片隅でひっそり生きるシステムエンジニアです(´・ω・`)

CodeIQの「フィズ・バズ・エクストリーム」に参加しました。

 冷静に見返してみると、反省点が山盛りですね……。ふだんいかに何も考えていないかがわかります。

「フィズ・バズ・エクストリーム」とは

 「フィズバズ・エクストリーム」とはリクルートキャリア社が運営する――って、この手のことは以前に何度も書いたので、省略。以下のリンクをもって説明に変えておきます。

提出コード

 言語はRuby。実行時間は計測するまでもないほどにわずか。一発目の提出で合格でした。

 もう数週間ぶりに提出コードを見直しているのですが――我ながらひでーコードだな。大体にしてmultipleって何だよ……。かけ算ならmultiplyだろうに。というか、そもそもこのメソッド用意する必要あったかしら。

 あと最後のほうにある、mapしてからinjectするという謎の処理。ふつうはinjectだけで何とかする処理をなぜ分けてしまったのか――と思って、履歴を見ていたところ、過去のバージョンでは謎の処理はしていないことが判明。なぜ提出段階で書き換えてしまったのか。当時のわたしに聞きたいです……。

 答えが出たテンションで、見直しをしないからこうなるのだ。反省。

考え方

 さて本問を見て、まず思いつくのはFizzBuzz式の解き方。

sum = 0
(1..100).each do |i|
    sum += i if i % 3 == 0 || i % 5 == 0
end
puts sum

 こちらのほうがプログラミングっぽいといえばその通りですが、範囲が大きくなったり、条件分岐が多くなったりすると、まず破たんします。少なくともRubyでは無理です。したがって別のやり方を考える必要が出てきます。

 ここで問題を矮小化(?)してみます。

1から100に含まれる3の倍数の合計を求めなさい

 これは等比数列の和、ないし等差数列の和なので、簡単にもとめることができます。センター試験に出てきそうですね。

 ただし簡単にもとめられるからといって、「3の倍数の合計」と「5の倍数の合計」を足し合わせれば出来上がり――とはいきません。これだと「3かつ5の倍数」(=「15の倍数」)を余計に数えてしまってしまっているからです。

 つまり「何らかの倍数の合計」を足したり引いたりすると、答えが出てきそうだということがわかります。そしてここに思い当って思い出したいのが「包括と排除の原理」です

 包括と排除の原理。正直なところ理屈はさっぱりわかりませんが(ひどい話だ)、わからないなりに次のように理解しています。

A or B or C のような和集合を求めたい。まず和集合をつくる要素(A,B,C)の集合からべき集合を作る。ただし空集合は無視。べき集合の要素をそれぞれ共通部分とみなして、これを足したり引いたりすると、和集合が完成する。なお共通部分をなす要素の数が奇数のときは足し算、偶数のときは引き算である。

 ……(´・ω・`)??? 自分で書いておいてあれですが、説明がさっぱりわかりませんね。理屈を理解せず、結果だけを知っているがゆえの惨状。反省。とりあえずWikipedia「包除原理」が一番わかりやすいと思います

 「等差数列(等比数列)の和の公式」と「包括と排除の原理」。このふたつに思い当れば、本問を解く方針は立つはず。あとはプログラムに落とし込んでいくだけ。ネックがあるとすれば、組み合わせを求めるあたりでしょうか。Rubyには組み合わせを求めるメソッドが標準にあるので、問題ありませんが、ない場合は工夫する必要がありそうです。

おまけ

 最近諸事情あってC言語の復習中なので、こちらでも挑戦してみました。正直Cに触れるのは数年ぶり。まったく自信がありません……。

 書いてみてつらかったのは2点。

 まずは組み合わせ関係。Rubyにはメソッドがあるので、それを利用すればよいだけですが、Cだと自分で実装する必要があります。今回は2進数を利用して、総当たりの組み合わせを作りました。再帰を使う方がすっきりするような気もしますが、気にしない。正直なところRubyになれていると、Cで配列を扱いたくない。

 次に困ったのは整数関係。どうやら所々でint型だと桁あふれを起こす可能性があり、この対策にかなり時間が取られました。最後のほうは投げやりになって、特に考えもせずlongを使っているのは内緒。このあたりもRubyだとまったく気にする必要がないということで、Rubyのありがたさが骨身にしみます。