ガジェット通信

見たことのないものを見に行こう

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

DATE:
  • ガジェット通信を≫

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

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

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

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

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

例えば、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(a,b,c,d) を求めるプログラムを書いてください。

―――――

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

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

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

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

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

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

参考:正弦定理(Wikipedia)

参考:余弦定理(Wikipedia)

参考:整角四角形問題(ラングレーの問題)(外部サイト)

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

#include
#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 がちょうど整数値になるときに期待通りの答えが得られないことがあります。これは計算誤差によるものです。例えば (a,b,c,d)=(20, 60, 50, 20) のとき、期待する x の値は 50 ですが、実際に計算を行うと 49.999999999997… のような値になります。これを 106 倍した値の整数部分は 49999999 となり、正解の 50000000 と異なってしまいます。そこで上記のコードでは、微小な値(1010)を x に足してから整数にキャストするという対策を入れています。

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

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

  n を d で割った余りが 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 程度になり、そのような回数の繰り返し計算には長い時間を要してしまうためです。

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

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

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

#include
#include
using namespace std;

long long G(long long n) {
long long answer = 0, k = (long long)sqrt(n – 1);
set s;
for (long long p = 1; p

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。

TOP