ﾕﾕﾕﾕﾕ

webエンジニアです

任意の区間で任意の整数の倍数を数える

TIL Ruby

　Codility の問題をいくつか解いてみていて、どうにも解けずに諦めてしまった問題があった。匙を投げて解法を検索してみて、あまりにスマートに解けるものだから、なおさら悔しい思いをしている。そこで供養の意味も込めて振り返りをまとめておく。

　当該の問題は Lesson 5 の count_div である。リンクは以下に貼る。

app.codility.com

　 A, B, K の3つの整数が与えられ、 [A, B] の区間に含まれる K の倍数の個数を数え上げる。

　制約として定式化すると次の通りである。

  • \{ i:A\leq B,i\ mod\ K= 0\}
  • 0\leq A\leq B\leq 2,000,000,000
  • 1\leq K\leq 2,000,000,000

　A から B までを愚直にイテレートする解がまず思い浮かぶが、これでは計算量が O(B - A) であるから制約に照らすと許容できない。で、自前のテストケースを用意した上で効率化する方法を考えてみるのだが、どうにもうまく仕様を満たせない。 A = 0 の場合、 A = B = 0 の場合、 A\ mod\ K = 0 の場合、 B\ mod\ K = 0 の場合 ... などのケースを同時に満たすことができず、いっけん簡単に見えるにもかかわらず解ききることができずうろたえてしまった。なお利用したテストケースは gist として公開してある。

count_div_test.rb · GitHub

　バグがあるというよりは単に計算の帳尻が合わないということが自分でも痛いほどわかっていて、コーディングスキルというよりも数学的思考の弱さを突きつけられているようで、解いていて本当に辛かった。結局は検索エンジンに頼って正答例を得てしまったわけだが、5行で実装されているその解法をみるにつけても、自分で解答にたどり着けなかった悔しさが募るばかりである。

　そこで、ここでは正当例のコードを基に証明も考えてみた。もちろん証明してから解ければ申し分ないし、本来はそうありたいわけだが、あいにくその力がなかったということで、振り返りも兼ねてまとめる。

証明

定義

  • r = A\ mod\ K \left( r\geq 0\right)
  • m = A\ -\ r\ \left( 0\leqq m \lt r\right)

とおく。m は A 以下の最大の K の倍数ということになる。

手続き

　 [A, B] の区間における K の倍数の個数を考える。

  1. a = 0 のとき
    • m = A より [m,B] の区間について考えればよい
  2. a > 0 のとき
    • 便利のためにこの場合も [m, B] の区間を数え上げる。
    • m は [A, B] に含まれない倍数であるが、 [m, B] について解を求めて、最後に -1 を加えれば結局 [A, B] についての解が得られる

　というように、 [m, B] の範囲における K の倍数を数え上げるという方針で考えればよい。さらにこれを変形して [0, B-m] としても、範囲内に含まれる倍数の個数は変わらないのは明らかである。

　以上より、問題の条件を求める計算式は (B - m) / K + 1 となる。 [0, B-m] の区間には 0 が含まれ、これも K の倍数であるから、最後に 1 を加えている。

　コードとしてはこうなる。

def solution(a, b, k)
  r = a % k
  m = a - r
  answer = (b - m) / k + 1
  answer -= 1 if r > 0
  answer
end

おわりに

　こういった整数論的な問題は、僕にとっては明らかな苦手分野だ。問題文をみたときにはすでにこのような思考を組み立てられる頭脳を持つ人もいるのだと思うとまったく恐ろしい。

　同じ土俵で勝負することは到底敵わないわけであるから、こうしてきちんと復習はしつつも、自分の勝てる土俵を見つけないといけない、そしてそこで戦う根性を身につけなければならない、と改めて考えさせられる契機となった。もっとうまくなりたいと思うが、それは当然、もっと修行しなければいけないという意味にほかならない。とはいえこのほかにも学びたいものはたくさんあるわけで、どの優先順位で何をやるかをよく考えて取り組まないと、二兎を追うだけの結果となりかねない。