CodeIQ MAGAZINECodeIQ MAGAZINE

数学の問題をプログラミングで解こう!「セカンド・イクエイション」問題解説

2015.11.16 Category:CodeIQ問題解説・リーダーボード Tag: ,

  • 7
  • このエントリーをはてなブックマークに追加
riverplus

「数学の問題をプログラミングで解こう!」シリーズ。

今回は二次方程式を題材にした問題を出させて頂きました。人によっては懐かしく思われたかもしれません。
できた方もそうでない方も、ぜひ本記事で解法をチェックして下さい!
by @riverplus Kawazoe

問題のおさらい

3つの自然数 a, b, c に対し、これらを係数に持つ次の二次方程式を考えます。

    a x2b xc = 0 … (※)

例えば、(a, b, c) = (1, 6, 4) のとき、方程式(※)は、x2 + 6x + 4 = 0 となります。
この方程式は実数解を持ちます。x = -3+√5 と x = -3-√5 の二つです。
一方で、(a, b, c) = (1, 6, 10) のとき、方程式(※)は実数解を持ちません。

b ≦ 3 の範囲で、方程式(※)が少なくとも一つの実数解を持つような自然数の組 (a, b, c) は、全部で 4 組あります。
(a, b, c) = (1, 2, 1), (1, 3, 1), (1, 3, 2), (2, 3, 1) です。

自然数 m に対し、bm の範囲で方程式(※)が少なくとも一つの実数解を持つような自然数の組 (a, b, c) の個数を F(m) と定義します。

例えば F(3) = 4、F(4) = 12、F(10) = 287、F(100) = 620174 です。

標準入力から、自然数 m(1 ≦ m ≦ 3000)が与えられます。
標準出力に F(m) の値を出力するプログラムを書いてください。

方針

二次方程式の解の条件に関する問題です。真っ先に思い浮かぶのが判別式ですね。二次方程式 a x2b xc = 0 が実数解を持つには、判別式 Db2 ー 4 a c が 0 以上であればよいです。つまりはこの条件を満たす (a, b, c) の組がいくつ存在するかということです。

F(m) の定義によると、3 つの係数のうち、b についてのみ bm という条件が記されています。そこで b を右辺に移してみましょう。

    a cb2/4  … (☆)

ついでに係数 4 も右辺に移しました。b の値をひとつ固定したとき、積 acb2 / 4 以下となるような (a, c) の組がいくつあるかを考えることになります。

単純には、ac の組をひとつひとつ列挙する方法が考えられます。つまり ac について二重ループを行うコードを書くという方法です。が、これは非効率な方法です。ac の取り得る値の範囲はいずれも最大で|b2/4|ですから(|・|は小数点以下を切り捨てる記号)、全組み合わせは|b2/4|×|b2/4| ≒ |b4/16|通りです。b のループも合わせると、つまりは O(m5) の計算量となり、膨大な実行時間を要してしまいます。

これより若干よいやり方として、ac の両方のループでなく、a の片方のループのみを書くという方法が考えられます。a の値をひとつ固定したとき、不等式(☆)を満たす c の個数は|b2/4a|個となることを利用します。つまり a を 1 から|b2/4|の範囲でループさせ、|b2/4a|の和をとったものが答えとなります。計算回数がぐっと抑えられます。

#include <iostream>
using namespace std;

int main() {
    int m, k;
    long long answer = 0;
    cin >> m;
    for (int b = 1; b <= m; b++) {
        k = b * b / 4;
        for (int a = 1; a <= k; a++) {
            answer += k / a;
        }
    }
    cout << answer << endl;
}

しかしながら、本問をクリアするにはこの方法でも不十分です。この方法だと計算量はO(m3) となるわけですが、m が最大で 3000 となる本問ではまだ厳しいです。さらなる高速化のアイデアが必要になります。

対称性を利用する

そこで本問では対称性を利用することを考えましょう。不等式(☆)をじっと見てみます。すると、この式は変数 ac に関して対称である、つまり ac を入れ替えても内容が変わらないことに気が付きます。したがって、ac のときに題意を満たす (a, c) の組の個数と、ac のときの個数は、ちょうど等しくなることが分かります。

例を見ましょう。次の図は、b = 7 のときの題意を満たす (a, c) の組を a-c 平面上にプロットしたものです。(☆)式は a c ≦ 49/4 となります。ac のときの点(赤)の個数と、ac のときの点(青)の個数がぴったり同じになっています。

したがって、青の部分の計算は不要で、赤の点の個数だけ求めて 2 倍すれば、赤+青を求めたことになります。さらにそこに a = c のときの個数(上図の黒の点)を足せば、最終的な答えが得られます。赤の点の個数を求めるには、a を 1 から √(b2/4) = b/2 の範囲でループさせます。当初のアプローチよりも、ループの範囲がさらに抑えられます。計算量は O(m2) となり、制限時間内でクリア可能となります。

以上の処理をコードにしたものが以下です(C++)。

#include <iostream>
using namespace std;

int main() {
    int m, k;
    long long answer = 0;
    cin >> m;
    for (int b = 1; b <= m; b++) {
        int k = b * b / 4;
        for (int a = 1; a <= b / 2; a++) {
            answer += 2 * (k / a - a); // 赤青の点
        }
        answer += b / 2; // 黒の点
    }
    cout << answer << endl;
}

みんなのコード

本問の挑戦者で、コードを公開して頂いた方のコードを Togetter でまとめました。(随時追加していきます。)こちらもぜひチェックして下さい!

CodeIQ「セカンド・イクエイション」問題 みんなのコード

CodeIQ運営事務局より

Kawazoeさん、ありがとうございました!
現在、Kawazoeさんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

  • 7
  • このエントリーをはてなブックマークに追加

■この記事を書いた人

avatar

@riverplus Kawazoe

数学・パズル好きのソフトウェアエンジニアです。某社で研究開発をしています。Project Euler の問題開発チームメンバー(最近はあまり活動せず)。twitter: @riverplus Web Site: riverplus.net

■関連記事

数学の問題をプログラミングで解こう!「ロンリー・ルーク」問題解説... 問題のおさらい 自然数 n, k に対し、縦横 n×n のマス目にチェスのルークの駒を k 個配置することを考えます。 このとき、自身から見て上下方向・左右方向のいずれにも他の駒が存在しないような駒を「はぐれルーク」と呼びます。 例えば以下は、(n, k)=(4, 5) のときの駒の配置例を示...
【謎解きプログラム】どんな数字になる?【整数のキャスト】... 【謎解きプログラム】どんな数字になる?【整数のキャスト】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24...
【謎解きプログラム】テキストのバイナリは?【テキスト バイナリ】解答と解説... 【謎解きプログラム】テキストのバイナリは?【テキスト バイナリ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 ...
【謎解きプログラム】条件に当てはまる文字列は?【正規表現】解答と解説... 【謎解きプログラム】条件に当てはまる文字列は?【正規表現】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「2...
数学の問題をプログラミングで解こう!「クロッシング・ワード」問題解説... 問題のおさらい クロスワードの盤面では、格子状のマス目に白マスまたは黒マスを配置します。 以下は、縦 3 個×横 4 個のマス目に白マス・黒マスを配置する例です。 白マス・黒マスの配置には次のルールがあります。 黒マスによって白マスの領域が分断されてはならない。 黒マスが縦・横に連続し...
【謎解きプログラム】乱数で発生する数値は?【組み合わせ】解答と解説... 【謎解きプログラム】乱数で発生する数値は?【組み合わせ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ