「ペア・ドロップ」問題 みんなのコード

「ペア・ドロップ」問題のみんなのコードです。
いつもありがとうございます!!!

「ステップ・アップ・サム」問題 解説

 CodeIQでの14問目の出題、「ステップ・アップ・サム」問題の解説です。
 問題文はこちら

 自然数 n を連続する自然数の和で表す問題です。
 先頭の自然数a自然数の個数を m とおきます。すると、自然数の和は次のようになります。

 \begin{eqnarray} 
Sum &=& a+(a+1)+(a+2)+\cdots+(a+m-1) \\
&=& \sum_{i=1}^m (a+i-1) \\
&=& \frac{1}{2}m(2a+m-1)
\end{eqnarray}

 これが n に等しくなる am の組を全て求めればよいわけです。

 \begin{eqnarray} 
\frac{1}{2}m(2a+m-1) = n \\
m(2a+m-1) = 2n
\end{eqnarray}

 この式をじっと見てみると、2n が、m と 2a+m-1 の積であることが分かります。
 つまり、m は 2n の約数です。
 したがって、2n を割り切るような自然数を探せば、それが m の候補となります。

 そのような m を探すには、単純には、1 から 2n までの全ての自然数で 2n を割ってみればOKです。
 が、それでは長い計算時間を要してしまいます。
 そこで、「m が 2n の約数ならば 2n/m もまた 2n の約数である」という事実を利用します。
 したがって、1 から 2n まででなく、1 から √(2n) までの自然数で割り算を行えば十分です。

 m の候補が見つかれば、そのときの a の値も実際に求めてみて、題意を満たすかチェックしましょう。

 自分のコードはこちらです。

 挑戦者の方々のコードをまとめました。本問は、上記以外にもいろいろな解き方があると思います。
 ぜひ自分以外の人のコードを見て学んでみてください!
 togetter.com

「カット・アンド・スクエア」問題 別解

 CodeIQにて「カット・アンド・スクエア」問題というのを出題しました。

 問題文はこちら。解法はこちらです。

 以下では、解法pdfで言及した別解について解説します。

 

 上 n/2 桁の数を a、下 n/2 桁の数を b とおくと、題意は次のようになります。

10n/2 a + b = a2 + b2

 ここで、A = 2a - 10n/2B = 2b - 1 と変数変換を行うと、題意の式は次のようになります。

A2 + B2 = 10n + 1

 整数を2平方和で表す問題に帰着されます。

 

 この問題を解くときのポイントは、「①10n + 1 を素因数分解する」「②素因数分解した素因数のそれぞれを2平方和で表す」の2点です。

 

n = 6 の場合

 まず「①10n + 1 を素因数分解する」ことを考えます。単純には試し割りのアルゴリズムが有効です。コードは詳細します。106 + 1 = 101 × 9901 となります。

 次に「②素因数分解した素因数のそれぞれを2平方和で表す」ことを考えます。例えば x2 + y2 = 101 となる整数組 (x, y) を見つけるということです。これも単純には、x の値をまず一つ固定し、y = √(101 - x2) が整数となるかチェックするという方法が考えられます。結果、102 + 12 = 101 と 992 + 102 = 9901 が得られます。

 ①②ができれば、あとは単純です。ブラーマグプタの二平方恒等式を使います。

A2 + B2 = 101 × 9901

    = (102 + 12) × (992 + 102)

    = (10・99 - 1・10)2 + (10・10 + 1・99)2 = 9802 + 1992 ・・・ (1)

    = (10・99 + 1・10)2 + (10・10 - 1・99)2 = 10002 + 12 ・・・ (2)

 あとは (A, B) から (a, b) への変換を行い、題意を満たすかをチェックすればOKです。結果、(a, b) = (990, 100) が正解と分かります。

 

n = 10 の場合

 n = 10 の場合も同様です。①素因数分解の結果は、1010 + 1 = 101 × 3541 × 27961 となります。

 ②素因数のそれぞれを2平方和で表した結果は、102 + 12 = 101 と 542 + 252 = 3541 と 1442 + 852 = 27961 となります。

 ここから先の (A, B) の組を見つけるところがちょっとややこしいです。ブラーマグプタの二平方恒等式では、2つの2平方和の積が、2平方和として2通りに表せます。これが3つになると、計4通りの組み合わせが存在することになります。

 結果、(A, B) = (1, 100000), (64700 76249), (48320, 87551), (19801, 98020) の4つが解となります(A, B とも正の場合のみ記載)。n = 6 の場合と同様、(a, b) への変換を行い、題意を満たすかをチェックすればOKです。ただし A または B が負になる場合ももれなくチェックしましょう。

 (a, b) = (17650, 38125), (25840, 43776), (74160, 43776), (82350, 38125), (99010, 9901) の5つが正解です。

 以上の方針だと、n = 16 程度までなら、一瞬の実行時間で答えを得ることができます。計算量は O(√(10n+1の最大の素因数)) です。

 

さらに大きな n の場合

 n がさらに大きな値の場合の高速化を考えます。

 ①素因数分解については、上では単純な試し割りのアルゴリズムを紹介しましたが、ポラード・ロー素因数分解法などの高速なアルゴリズムが有効です。

 ②素数の2平方和への分解については、セレの方法などが存在します。H. Davenport 著「The Higher Arithmetic: An Introduction to the Theory of Numbers」の p.120~122 に詳しく書かれてあります。上記 Amazon のページでキーワード「Serret」でなか見検索すると確認できると思います。同ページのルジャンドルの方法とともに、参照コードをこちらに書きました。

 この方針で、n = 36 以下の全ての n に対する答えを ideone 環境で約 1.2 秒で得ることができました(Python)。コードはこちらです。

 10n + 1 が大きな素因数を持つ場合はこの方法でも高速に解けません。n = 38 の場合(1038 + 1 = 101 × 722817036322379041 × 1369778187490592461)は、上記コードでも数分待っても答えは得られませんでした。

 

コードの公開について

 CodeIQでKawazoe (@riverplus) が出題している問題については、任意で、掲載期間の終了後にコードの公開をお願いしています。(Kawazoeの出題する問題に限ります。)

コードの公開のしかた

 ご自身のブログで公開して頂くか、あるいは Ideone などのサービスを利用して下さい。
 Ideone の使い方に関しては下記のページをご覧下さい。
 オンラインコンパイラ ideone の利用方法について #ideone #codeiq - Tbpgr Blog
 Ideoneの使い方 (2014年8月) - Qiita

出題者への知らせかた

 次に、公開したら、下記(1)(2)のいずれかの手段で出題者(Kawazoe)までコードのURLをお知らせ下さい。

 (1) Twitter で、「@riverplus」を文中に含めたツイートを行う。
  (2015/07/20変更:以前は専用のハッシュタグでのツイートをお願いしていましたが
   ツイート検索で引っかからない場合があるので変更しました。)

 (2) このページのコメント欄に記入する。出題者が代わりにツイートします。

よろしくお願いします!

公開するとどうなるの?

 Togetter で皆様のコードのツイートをまとめて紹介させて頂きます。
 他の人のコードを見るのはとても勉強になります。
 新しいアイデアやコードの書き方など学びましょう!

 もし、上の(1)(2)をやったのに紹介されなかったという方、私が見落としている可能性大です。 すみませんがこのページのコメント欄で教えて下さい。あるいは、下のまとめは誰でも編集可能ですので、ご自身で加えて下さっても構いません。

これまでのコードのまとめ