はじめに
少し前の話しになりますが、 sendai.rbで、AtCoderの問題をRubyで解く機会がありました。
このときの経験を元に、AtCoderの問題を（Rubyで）解くことについて、感じたことを書いてみます。
Atcoderの問題を解くことで、検索力を身につけたり、Rubyのクラスやメソッドを知ることができる
たとえば、C - Unlucky7 を解く場合を考えてみましょう。
この問題を解くためには、数字を8進数表記に変換する方法や文字列の中に '7' が含まれるかどうかを判定する必要があります。
Ruby 8進数 でネットで検索すれば、8進数への変換に Integer#to_s が使えそうなことが分かります。
また、Ruby 文字列 含む で、ネットで検索すれば、 String#include? が使えそうなことが分かります。
調べたことを組み合わせて使ってコードを書けば、問題を解くことができます。
問題を解くために使えそうなクラスやメソッドを調べ、それらを使うことを通じて、Rubyのクラスやメソッドのことをより深く理解できるようになります。
Rubyには、便利なメソッドが数多く用意されていることもわかるでしょう。必要なことをネットで調べる基本的な検索力も身に付くと思います。
AtCoderの問題を解くことで、アプリケーションロジックを深く考える訓練ができる
次に、D - Hachi を解く場合を考えてみましょう。
この問題を解くためには、並べ変えた数字をすべて列挙し、8で割り切れるかどうか判定する必要があります。
Ruby 並べ替え 列挙 でネットを検索すれば、Array#permutation が使えそうなことがわかります。
8で割り切れるかどうかは、8で割った余りが0かどうかを判定すれば良く、 Ruby 余り で検索すれば、 % を使えそうなことがわかるでしょう。
これを使えば、正しい答えを出すコードを書くことができます。
と、これだけで終われば、話は簡単ですが、そう上手くいかないところが AtCoder の世界なのです。
AtCoderには、単純に問題の正しい答えを出力するという機能要件の他に守るべき非機能要件があります。
プログラムの実行時間と使用できるメモリの制約です。実行時間が2秒以内、メモリ1024MB以内の制約の中で答えを出す必要があるのです。
時間とメモリという2つの非機能要件も満たす必要があるのです。
結果的に、私は、Array#permutation を使って非機能要件を満たすコードを書くことができませんでした。
実行時間の制限にひっかかって、全てのテストにパスできないのです。
Array#permutation を使わない方法でコードを書いてみて、2秒ギリギリ通るようになりました。
その後、書いていたコードの一部をバイナリサーチを使うように書き変えると速くなるのでは、とひらめきました。
実際、バイナリサーチを使うことで、200ミリ秒で全てのテストが通るようになりました。
レベルの高い問題だと、単純にライブラリを使っても問題をクリアできず、その問題領域を深く理解する必要があります。
要求されていることは何か？ その答えを導く出すのに必要な処理は何か？ 限られた時間とメモリの範囲内で答えを出すもっと別の方法は無いのか？ などを考える必要があります。
実際、 Array#permutation を使わないコードは、「並べ変えた数字をすべて列挙」していませんし、 「8で割った余りが0かどうかを判定」していません。
(この問題を解くために、なぜ「バイナリサーチ」を使うことができるのか、おわかりでしょうか？)
Ruby でAtCoder の問題を解くということ
AtCoder の問題を解くことによって得られるメリットには次のようなことがありそうです。
- Rubyにどんなライブラリやメソッドがあるか調べることを通じて、Rubyのクラスやメソッドを深く知ることができるようになる。特に
ArrayやStringなど良く使われる基本的なライブラリについて深く知れるのではないかと思います。 - ネットでうまく必要な情報を見つける練習にもなる。
上位のレベルの問題を解くには、ライブラリの知識だけでは、不十分です。
機能要件、非機能要件を満足するように、アプリケーションロジックを深く考え、考えたロジックをコードに落とし込む技術が必要になってきます。
こちらは、ネットで検索して、すぐ解決できるようなものではないと思います。
解決したい問題とネットで検索して解決できることの間に隔りがあるので、この隔りを埋める作業が必要になってきます。
D-Hachiの問題で言えば、バイナリサーチを使う方法を思いつくことが、隔りを埋める作業です。
バイナリサーチの実装例は、ネットで検索すれば見つかるでしょう。
つまり、こちらで得られることは、次のようなところでは無いかと思います。
- その問題領域を深く考える練習ができる。
- ネットで検索して解決できるレベルまで問題を落とし込む練習ができる。
- 考えた方法をコードとして実現する練習ができる。
実業務では
実際の開発業務でも、似たようなことがあると思います。
すぐにネットで検索して解決できることもあれば、ネットで検索するレベルと課題との隔りを埋める作業が必要なこともあります。
AtCoder はRubyの知識を深めたり、検索力を高めたり、検索して解決できるレベルまで問題を落とし込む練習をする題材として使えそうと思いました。