はむ吉（のんびり）の練習ノート

プログラミングとことばに関する話題を中心に，思いついたこと，試してみたこと，学んだことを，覚え書きを兼ねてまとめます．その際に役立った，技術書，参考書，辞書，機器などの紹介も行います．

Google Code Jam Qualification Round 2016 C. Coin Jam：SymPyによる解答例

プログラミング 競技プログラミング 数論

Googleが開く競技プログラミングのコンテストGoogle Code JamのQualification Round 2016が、4月9日8時から翌10日11時まで（日本時間）の27時間にわたり開かれました。私はこれに参加し、その結果としてRound 1への進出が決まりました。この記事では、このQualification Roundで私が正解した問題の一つである、C. Coin Jamという問題の、Python用記号計算ライブラリSymPyを用いた解き方について述べます。

問題の趣旨

各文字が'0'または'1'であり、両端が'1'である長さN (≧2)の文字列であって、これをb (= 2, 3, ..., 10)進法表記として解釈して得られる整数m_{i, b}がすべて合成数である*1ような相異なるJ個の文字列S_i (1≦i≦J)を求めよ。また、整数m_{i, b}のそれぞれについて、その自明ではない約数（すなわち、1とm_{i, b}以外の約数）d_{i, b}の例を一つ答えよ。

方針

区間(2^{N - 1}, 2 ^ N)にある各整数を2進記数法で表した文字列について、上記の条件を満たすかを実際に判定すればよいでしょう。Jは高々500個なので、合成数m_{i, b}とその非自明な約数d_{i, b}を高速に見つければ、現実的な時間で答えを得られるでしょう。

合成数であるm_{i, b}とd_{i, b}を高速に見つけるために、乱択アルゴリズムであるPollardのp - 1法（wikipedia:en:Pollard's p − 1 algorithm）を使います。SymPyにはその実装としてsympy.ntheory.factor_.pollard_pm1（ドキュメント）があるので、これを使えばよいでしょう。ここで、合成数が与えられた場合でも、このアルゴリズムは失敗することがあります*2。そこで、何度か再試行することで、なるべく多くの合成数m_{i, b}を見つけ出します。

なお、この方法では最大で10^{32}程度の大きさの整数を扱うことになるので、多倍長整数や128ビット整数を扱える処理系・言語を用いる必要があります。Python 3は多倍長整数に標準で対応しています。

解答コード例

コンテスト中に提出したコードを手直ししたものを以下に示します。なお、標準入出力を利用しています。


感想

少々暴力的な解き方ではありましたが、とりあえず正解できました。公式解説やほかの参加者の方によるコード・解説を踏まえて、もう少しスマートなやり方についても考えたいところです。

*1:原文には「素数ではない」とありますが、制約条件から整数1と解釈される文字列は考えなくてよいので、「合成数である」と読み替えて構いません。

*2:すなわち、非自明な約数を見つけられないことがあります。