「今週のお題：140問目！素数列から抜き出してつぶやこう？」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 空白区切りで入力されるm,nに対して、m以上n以下の素数の全ての桁を連結した数字列の中で、次の条件を満たす部分列の和の最大値を求める。
- 部分列の長さは140桁以下
- 部分列の最初と最後の数字が等しい
例えば、m,n=5,30に対しては数字列の全体 57111317192329 の部分列 3171923の合計26が最大となります。
解説
両端の数字を1種類に固定して考えた場合、部分列の和の最大は、尺取法によって求めることができます。その際、部分列の情報を保持するキューを設けておき、おしりが伸びるに連れ、140文字に収まらない分を先頭から間引いていくことになります。
今回、これを両端0～9の10種類分同時に考えることになりますから、それぞれ Fiber を用意して分散管理することを考えました。 部分列の和の値は、先頭からの累積和の差分を元に計算できるため、Fiberを起床する時に、文字の位置と累積和の2種類を渡すことで対処できます。
ということで提出版です。
とまあ、Fiberを使うのが初めてだったのではしゃいでEnumeratorを多用した感も無きにしもあらず、なんですが、実は別に使わなくても組めたな、というのが後から分かりました。
やっていることは基本同じですが、こちらの方がより簡潔で速いです。
終わりに
CodeIQの今週のお題シリーズ、ほぼ毎週の出題でもう140問ということだそうで、よく問題のネタが尽きないものだと感心することしきりです。今後とも楽しみに、挑戦していきたいと思います。
さて。ソース管理にgithubを使うようになりました。ideoneの埋め込みも便利なのですが、gist-itでの埋め込みも楽で良いですね。
