読者です 読者をやめる 読者になる 読者になる

「今週のお題:140問目!素数列から抜き出してつぶやこう?」問題解答 ( CodeIQ )

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 空白区切りで入力される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での埋め込みも楽で良いですね。