CodeIQ MAGAZINECodeIQ MAGAZINE

数学の問題をプログラミングで解こう!「コード・トライアスロン2」問題解説

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

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

「数学の問題をプログラミングで解こう!」シリーズ。
特別版ということで、3 問を続けて解くという変わった問題でした。
一つでも間違ったら NG ということで、かなり難度の高い問題だったのではと思います。
みなさんは完全制覇できましたか?
ぜひ出題者のkawazoeさんによる本記事で解法をチェックして下さい!
by CodeIQ運営事務局

第1問:ラングレーの問題

四角形ABCDについて、∠ABD=a,∠CBD=b,∠ACB=c,∠ACD=d とおきます。

∠ADB を求めることを考えましょう。

例えば、a=30°,b=50°,c=40°,d=40°のとき、∠ADB=30°となります。

さて、abcd の値(単位は度)に対し、∠ADB の値(単位は度)を 106 倍したものの整数部分を F(abcd) と定義します。

例えば、F(30,50,40,40)=30000000 です。
同様に、F(20,60,50,20)=50000000,F(45, 40, 10, 95)=4515341,F(70, 30, 50, 50)=62122012,F(30, 50, 90, 15)=133176131 となることが示せます。

F(abcd) を求めるプログラムを書いてください。

―――――

「ラングレーの問題」という平面幾何の問題を題材にしました。一見、簡単そう?と思ってノートに図を描いてみるものの、さっぱり手が進まず、困った方もおられたかもしれません。実はこの問題、abcd の組み合わせによっては補助線を引いたりすることで解けるのですが、中学校の初等幾何の範囲で一般的に解くやり方は知られていません。

そこで本問では、高校範囲の数学を使って一般的な解法を得る必要があります。

話を簡単にするために、BC の長さを 1 とします。まず、⊿ABCと⊿BCDに正弦定理を用います。

移行して整理すると、AB と BD は次のように表されます。

次に、⊿ABDに余弦定理を用います。∠ADB=x としています。

それぞれ AD と x について整理します。

参考:正弦定理(Wikipedia)
参考:余弦定理(Wikipedia)
参考:整角四角形問題(ラングレーの問題)(外部サイト)

これで全ての準備が整いました。与えられた abcd を使って AB と BD を求め、さらに AD を求めれば x が計算できます。さらにそれを整数値にキャストすればそれが答えです。コード例を以下に示します(C++)。度数法と弧度法の変換に気をつけましょう。

#include <cmath>
#define PI 3.1415926535897932384626433832795

double Sin(int x) {
    return sin(x / 180.0 * PI);
}

double Cos(int x) {
    return cos(x / 180.0 * PI);
}

double Acos(double x) {
    return acos(x) / PI * 180.0;
}

long long F(int a, int b, int c, int d) {
    double AB = Sin(c) / Sin(a + b + c);
    double BD = Sin(c + d) / Sin(b + c + d);
    double AD = sqrt(AB * AB + BD * BD - 2 * AB * BD * Cos(a));
    double x = Acos((AD * AD + BD * BD - AB * AB) / 2 / AD / BD);
    return (long long)((x + 1e-10) * 1000000);
}

なお注意点が一つあります。浮動小数点型の変数を使うと、x がちょうど整数値になるときに期待通りの答えが得られないことがあります。これは計算誤差によるものです。例えば (abcd)=(20, 60, 50, 20) のとき、期待する x の値は 50 ですが、実際に計算を行うと 49.999999999997… のような値になります。これを 106 倍した値の整数部分は 49999999 となり、正解の 50000000 と異なってしまいます。そこで上記のコードでは、微小な値(1010)を x に足してから整数にキャストするという対策を入れています。

第2問:余りを1にする割り方

自然数 n に対し、次の性質をもつ自然数 d の総和を G(n) と定義します。

  nd で割った余りが 1 に等しい。

例えば、G(13)=27 です。13 を 2,3,4,6,12 で割った余りはいずれも 1 だからです。

同様に、G(100)=155,G(102)=101,G(30031)=96767,G(62122012)=101219327 となることが示せます。

G(n) を求めるプログラムを書いてください。

―――――

次は割り算の余りに関する問題です。

単純には、n を様々な d で一つ一つ割ってみて、余りが 1 かどうかチェックすればよさそうです。が、このやり方はうまくいきません。第1問の答えは最大で 180×106 程度になり、そのような回数の繰り返し計算には長い時間を要してしまうためです。

この問題は、「nd で割った余りが 1」という表現にこだわると考えにくいです。発想を変えましょう。「n-1 は d で割り切れる」と読みかえても意味は同じです。そこで、n-1 の約数の求め方を考えましょう。

n-1 を様々な d で割ってみるというのが基本アプローチですが、1 から n-1 までの全ての数で割り算をしていたのではやはり時間がかかります。そこで、dn-1 を割り切るとき、その商 (n-1)÷d もまた n-1 を割り切る という事実を利用しましょう。n-1 までの数で割り算をする必要はなく、√(n-1) まで試した時点で探索を打ち切ってかまいません。

コード例は以下です。重複を除くために std::set を使っています。

#include <set>
#include <cmath>
using namespace std;

long long G(long long n) {
    long long answer = 0, k = (long long)sqrt(n - 1);
    set<long long> s;
    for (long long p = 1; p <= k; p++) {
        if ((n - 1) % p != 0) continue;
        s.insert(p);
        s.insert((n - 1) / p);
    }
    for (set<long long>::iterator i = s.begin(); i != s.end(); i++) {
        if (*i != 1) answer += *i;
    }
    return answer;
}

第3問:回文数の和

先頭にゼロを持たない自然数であって、逆から読んでも同じ数になる数を回文数と呼びます。

例えば、1,22,343,440044,7890987 は回文数です。

10,2020,30000,456665 は回文数ではありません。

自然数 m に対し、m 以下の回文数の総和を H(m) と定義します。

例えば、H(20)=56 です。20 以下の自然数では 1~9 と 11 が回文数だからです。

同様に、H(100)=540,H(10000)=545040,H(987789)=533115672,H(101219327)=557319321362 となることが示せます。

H(m) を求めるプログラムを書いてください。

―――――

回文数の和を求める問題です。単純な解法として、1 から m までのすべての数を調べて回文数かどうかをチェックするというアプローチがありますが、時間がかかり過ぎてしまいます。

アプローチを変えましょう。回文数を探す のではなく、回文数を作る という考え方です。

最初に適当な数を選びます。この数の並びを逆にして、元の桁にくっつけてやれば、回文数が一つ出来上がります。例えば、123 から 123321 という回文数が作れます。また、先頭の 1 桁を除いたものを元の数にくっつければ、別の回文数 12321 を作れます。これを様々な数について行えば、すべての回文数を列挙することができます。

この方法で、√m 回程度の計算で答えが得られます。コード例は以下になります。いったん文字列型に変換してから加工するのが楽かもしれません。

#include <sstream>
#include <algorithm>
using namespace std;

long long H(long long n) {
    string s, t;
    long long answer = 0, p, m;
    for (m = 1; ; m++) {
        stringstream ss;
        ss << m;
        s = ss.str();
        t = string(s.rbegin(), s.rend());

        ss.clear();
        ss.str("");
        ss << s + t;
        ss >> p;
        if (p <= n) answer += p;

        ss.clear();
        ss.str("");
        ss << s + t.substr(1);
        ss >> p;
        if (p <= n) answer += p;
        else break;
    }
    return answer;
}

みんなのコード

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

CodeIQ「コード・トライアスロン2」 みんなのコード

CodeIQ運営事務局より

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

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

■関連記事

【謎解きプログラム】乱数で発生する数値は?【組み合わせ】解答と解説... 【謎解きプログラム】乱数で発生する数値は?【組み合わせ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24...
「放物線とマス目の関係」問題の解答と解説... table.nabe{ margin-left:30px; } .nabefloat{ float:right; } table.nabe td, table.nabe th{ padding:3px; } table.nabe th{ ...
【謎解きプログラム】データをバイナリで見てみよう【バイナリ】解答と解説... 【謎解きプログラム】データをバイナリで見てみよう【バイナリ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「...
数学の問題をプログラミングで解こう!「プライム・ペア」問題解説... 問題のおさらい 自然数 k に対し、1 から k までの自然数のうち k と互いに素なものの個数を F(k) と定義します。 (F(k) はオイラーのφ関数とも呼ばれています。参考:オイラーのφ関数(Wikipedia)) 例えば F(12)=4 です。1 から 12 のうち 12 と互いに素...
【謎解きプログラム】データベースを扱ってみよう【SQLite】解答と解説... 【謎解きプログラム】データベースを扱ってみよう【SQLite】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 ...
【謎解きプログラム】弾幕の軌跡を作ってみよう【描画】解答と解説... 【謎解きプログラム】弾幕の軌跡を作ってみよう【描画】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

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