<問題の詳細>
ACM問題集にある問題: 10168 Summation of Four Primes (4素数の和) を例にプログラムを考えてみたい。

問題の内容は、与えられた整数 N (N<=10000000)に対し、Nを4つの素数の和で表せというもの。もしNは4つの素数の和で表現できなければ、"Impossible."で答えろという。 また、4つの素数について、条件は一切なく、好きな組み合わせで良いという。なお、Nの個数に関し、その上限はとくに問題文に記述されていないが、数十個、数百個のNを素早く計算できないといけないだろう。

<自動判定の話>
つくったプログラムが正しいかどうかは、ここに貼り付けて送信すれば、その場で判定される。フォームに問題ナンバー (Problem #)(この問題では 10168)、登録者ID (ID with suffix)(サーバに登録すればその場で発行してくれる。登録料は勿論必要なし。誰でも参加できる。)、プログラムに使用した言語(C/C++/Pascal/Java の4つに限定されているが、C/C++が無難。Perl 等のスクリプト言語は残念ながら採用見込無) を記入または選択して、フォームの下半分の Source code: のところにソースプログラムを貼り付けるだけでOK。なお、コメント (Comment)欄の記入は必要なし。

自動判定の原理は簡単。送信したプログラムがその場でコンパイルされ、実行される。出てきた答えと用意された答えとの照合が行われ、ひとつでも答えが合わないと Wrong Answer(略してWA) を食らう。無事パスしたら、Accepted (略してAC)をもらう。自分の成績簿にその結果がその場で反映される。プログラム問題の多さ、自動判定レスポンスの良さ等と相まって、世界中(とくにコンピュータサイエンス関係の大学生)に大人気。多くのひとが日夜、多くの難問にチャレンジしている。残念ながら、日本では認知度がそれほど高くないようで、上位100以内にランキングされる日本人はとても少ない。

ちなみに、ほかの多くのプログラムの自動判定結果を眺めるのも楽しい。実行に使用したCPU時間、メモリ量、言語、登録者、問題ナンバーがこれで判る。

<実行時間の厳しさ>
さて、大変重要なことだが、許される実行時間は僅か10秒まで。10秒過ぎると実行が無条件に打ち切られ、Time Limit Exceeded (略してTLE) を食らう。しかも、サーバのCPUはペンティアムIII。どちらかというと遅いPC。ということで、10秒以内に数十個か数百個のNを計算し、正解を出さないといけない。数分間、数十分、数日かけてやっと答えの出るプログラムはACされない。プロの世界はやはり厳しいものだ。

<休憩>

<問題の整理>
問題にもどって、どう解答するかをまず見通しを立てよう。つぎの事実を知ると心強い。

ゴールドバッハの予想: 4以上の偶数は2つの素数の和で表すことができる。証明はされていないが、コンピュータの計算可能な範囲内では数学者達が確認済みなので、信じていいだろう。

どういうことかというと、4 = 2+2、6=3+3、8=3+5 のように、等号の左に4以上の任意の偶数が与えられると、等号を満たす2つの素数は必ず存在するということだ。(2, 3, 5 は素数)

ちなみに、大数学者オイラー宛のゴールドバッハからの手紙には、正確にいうと、つぎの等価予想が書いてあった。「5よりも大きい自然数は3つの素数の和であらわすことができる。」

これらの事実をまとめると、問題解決の戦略は以下のようにできる。

N が奇数ならば、なるべく大きな素数(Pとする)+2+残りの偶数1つ(Cとする)、に分解、
N が偶数ならば、なるべく大きな素数(P)+3+残りの偶数1つ(C) に分解することにしよう。

つまり、C=N-P-(2か3) で、N と P から C を算出。

2以外の素数はすべて奇数なので、N を以上のように奇数と偶数に分けたわけだ。また、C はゴールドバッハの予想より、2つの素数の和にさらに分解できるので、これで、N に対し、合計4つの素数が得られるわけだ。

P をなるべく大きな素数にするのは、C の値を小さくしたいから。C の値が5000以内なら、すべての組合せを事前に計算しておくこともできる。

5000という間隔で見積もると、N の最大値=5000*2000 になるので、約 2000個のP と 約2500対(偶数だけでいいので、5000の半分で済む)の和がCになる素数ペアを用意しておけば、ほぼゼロ秒(計算量の世界では O(1) という)で計算できる。

なお、2000個のP から正しいものを1つ選び出すのは難しくないだろう。2000個のPを昇順で並べておき、N/5000 番目のPを使えばよいのだから。

<ルックアップ・テーブルの多用>
上の文章に、事前に用意する云々の言葉が数回出ていたが、10秒という難関を突破するのに、とくにここのACM問題解答プログラムでは多く用いられている技法のひとつ。つまり、結果を事前に、手元のコンピュータを使って計算しておき、自動判定のためのプログラムソースに計算結果をテーブルとして埋め込むのだ。

(補足説明) ただ、もうひとつの厳しい判定条件にも気をつけないといけない。つまり、ソースプログラムの 長さは最大40KB まで。なんでもかんでもテーブルにしてはいけないという制限条件。

手元のコンピュータでは数分でも、数日でも構わないので、弾き出された結果を、テーブルに加工しておき、サーバに送り込む。入力データに合う結果をテーブルから探し出せばいいので、インチキといえばインチキ。だが、その方法でしか10秒クリアできない問題も結構あるという。

もうすこしわかり易く書くと、手元のコンピュータで、2000個のP、及び、Cに対応する2500対の素数ペアを算出しておく。それらをテーブルに書き込み、判定用「インチキ」プログラムを特別につくっておく。サーバに送り込まれた判定用「インチキ」プログラムでは、入力データの N に対し、N/5000 番目のPを使う。つぎに、C=N-P-(2か3)という式でCを算出し、テーブルから、Cに対応する素数2つを選び出す。それで、4つの素数が揃ったことになる。それを答えとして出力すればOK。プログラムの計算時間は限りなくゼロに近い。ベストタイムが狙えるかも。

ここでいうテーブルの実体は勿論配列。例えば今回の偶数を2つの素数の和で表す場合は、配列のインデックスはその偶数/2の値、配列の値は2つの素数。

(補足説明) ただ、よく考えたら、値が5000以内の素数判定なら、ノーマルな方法でも余裕で1秒以内でクリアできるので、Cの計算についてはテーブルなしでも全然OK。しかし、Pについてはやはりテーブルに用意したほうが無難だろう。

最後に境界条件をまとめよう。

最小の素数が2なので、N は7以下(ゼロやマイナスの整数も含む)ならば “Impossible.”と答えないといけない。

8以上のN はすべて4つの素数の和で表すことができるが、
   N=8=2+2+2+2
   N=9=2+3+2+2
   N=10=3+3+2+2
では、Cに偶素数ペア 2+2 を使うので、特殊ケースと考えていいかもしれない。11以上のNなら、Cは奇素数ペアの和で表現できる。

(補足説明) 偶素数:2 ひとつだけ。奇素数:3,5,7...、無数にある。偶素数+奇素数=奇数になるので、偶数になるには、偶素数同士、つまり、2+2 の一通りしかない。

<残りはプログラミングのみ>
プログラムの見通しはこれで立てたので、残りの作業はプログラミングのみだ。アイディア的に面白いのは実はここまで。プログラミングはいわば確認作業のようなもの。

テーブルのデータが多いので、面白くないと思うが、参考のため、ソースプログラムを掲載しておく。

<<素数テーブルの生成プログラム>> p10168-pre.c

<<解答プログラム>> p10168.c
 最後の偶数については、強引に2つの素数に分解している。

<<解答プログラム2(高速版)>> p10168-2.c
テーブルに改良したバージョン。最後の偶数Cに対応する素数ペアは片方判れば良いので、片方だけをテーブルにしてある。ベストタイムを狙ったつもりだが、結果は 0.016秒、4位になっている。これ以上速くするには、printf 関数も自作しないといけないかもしれない。

<<解答プログラム3(高速版2)>> p10168-3.c
printf 関数を使わないバージョン。送信して確認した結果、実行時間は 0.010秒、3位に浮上。これ以上速くすることは私に無理。

<ちょっとした遊び>
問題文の最後に、さりげなく変わった文章が載っている。

「You can fool some people all the time, all the people some of the time but you cannot fool all the people all the time.」 

そうかもしれないね。つぎのようなことも言えるかも。

「We can love some people all the time, all the people some of the time but we cannot love all the people all the time.」

Comments are closed.

Post Navigation