第103回 Yokohama.rbにてみんなで問題を解いてみた

月次で開催しているYokohama.rbにて@Nabetaniさんに用意して頂いた問題をみんなで解いてみるということをやってみました。

用意して頂いた問題は以下のもの。

問題としては単純なものです。ですが素朴に問題を解くと計算量が多くなるので、問題を速く解くためにはなんらかの工夫が必要という良問と思いました。

以下、回答編。問題を解きたい方はスクロールはしないでください。

...

さて、回答編です。

私が解いたのは以下のもの。愚直な実装です。

会場では愚直な実装で解かれた方が多かったのですが、早々に@hamaknさんが高速な実装を行い参加者が皆驚いてました。

@Nabetaniさんの実装例は以下の通り。

正直、一度読んだだけではよく理解できなかったので、手元で動かしながら理解していこうと思います。

こういう問題を解いたりすることをこれからもやりたいと思っています。ご興味ありましたらYokohama.rbにご参加いただけますと嬉しいです。