競技プログラミング Python

Angular Bisector and Tangent - Project Euler Problem 296

Python: Competitive Programming 4/N

公開日: 2023-11-14
更新日: 2023-11-14

  Table of Contents

Problem: Angular Bisector and Tangent

Problem

辺の長さが整数で BC ≤ AC ≤ AB を満たす三角形 ABC がある. k は角 ACB の二等分線である. m は ABC の外接円に対する C での接線である. n は B を通る m に平行な線である. n と k の交点を E とする.

BE の長さが整数で周長が 100 000 を超えない三角形 ABC はいくつあるか?

この問題は計算は大変ですが, 解答方針の立て方自体は三角形の相似と内角の二等分線の性質を利用するだけという 良問です.

解答方針を立てるまで

Python Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import math
    
class Solution:
    """ 
    Problem
        https://projecteuler.net/problem=296
    
    Solution
        Using the similarity between the triangle ACD and BCE
        and BE = BD
    
    Usage
        Solver = Solution()
        Solver.find_solution()
        >>> 1137208419
    """
    def gcd(self, a, b):
        while b > 0:
            a, b = b, a % b
        return a
    
    #def check_length(self, AB, AC, BC):
    #    return BC <= AC & AC <= AB

    def find_solution(self, perimeter:int=100000):
        count = 0
        for BC in range(1, perimeter//3 + 1):
            for AC in range(BC, (perimeter - BC)//2 + 1):
                k = self.gcd(AC, BC)
                step =  AC//k + BC//k
                min_AB = math.ceil(AC / step) * step
                max_AB = min(AC + BC, perimeter - AC - BC + 1)
                count += math.ceil((max_AB - min_AB) / step)

        return count

実行時間が遅い問題について

実行時間が遅い問題に直面した場合,

  • アルゴリズムの改善
  • マルチコアとメモリの暴力で殴る

という対応策が考えられます. 今回は「マルチコアとメモリの暴力で殴る」の方針での対応策を採用します. そもそも, 上記で紹介した解答を実行時のシステムモニターを見てみると, 少なくとも僕の場合はCPU１コアのみが稼働している状態となっていたので, これを30コアにすればオーバヘッドが発生するかもしれませんが, 単純に20~30倍近くの実行スピードが確保できると期待できます.

###

Python code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

import math
from multiprocessing import Pool
    
class Solution:
    """
    Note
        faster version using the multiprocessing module
    
    Problem
        https://projecteuler.net/problem=296
    
    Solution
        Using the similarity between the triangle ACD and BCE
        and BE = BD
    
    Usage
        Solver = Solution()
        Solver.find_solution()
        >>> 1137208419
    """
    def gcd(self, a, b):
        while b > 0:
            a, b = b, a % b
        return a

    def compute(self, BC):
        count = 0
        for AC in range(BC, (self.perimeter - BC)//2 + 1):
            k = self.gcd(AC, BC)
            step = AC//k + BC//k
            min_AB = math.ceil(AC / step) * step
            max_AB = min(AC + BC, self.perimeter - AC - BC + 1)
            count += math.ceil((max_AB - min_AB) / step)
        return count
    
    def find_solution(self, cpu, perimeter:int=100000):
        self.perimeter = perimeter
        with Pool(processes=cpu) as pool:
            return sum(pool.map(Solver.compute, range(1, perimeter//3 + 1)))

Solver = Solution()
Solver.find_solution(cpu=30, perimeter=100000)

爆速の実行スピードが確保できるようになった.

References

Share Buttons
 Share on:
Feature Tags
Leave a Comment
(注意：GitHub Accountが必要となります）
CONTENTS