結果

問題 No.2555 Intriguing Triangle
ユーザー navel_tosnavel_tos
提出日時 2023-12-01 21:33:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 55 ms / 2,000 ms
コード長 6,293 bytes
コンパイル時間 231 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 70,584 KB
最終ジャッジ日時 2023-12-01 21:33:50
合計ジャッジ時間 2,615 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
56,272 KB
testcase_01 AC 40 ms
56,264 KB
testcase_02 AC 41 ms
56,264 KB
testcase_03 AC 41 ms
56,264 KB
testcase_04 AC 42 ms
56,236 KB
testcase_05 AC 36 ms
53,460 KB
testcase_06 AC 40 ms
56,272 KB
testcase_07 AC 41 ms
56,272 KB
testcase_08 AC 36 ms
53,460 KB
testcase_09 AC 39 ms
53,460 KB
testcase_10 AC 50 ms
66,092 KB
testcase_11 AC 37 ms
53,460 KB
testcase_12 AC 48 ms
64,028 KB
testcase_13 AC 40 ms
55,596 KB
testcase_14 AC 45 ms
63,880 KB
testcase_15 AC 41 ms
59,456 KB
testcase_16 AC 45 ms
61,824 KB
testcase_17 AC 41 ms
56,272 KB
testcase_18 AC 42 ms
56,236 KB
testcase_19 AC 40 ms
56,272 KB
testcase_20 AC 49 ms
53,460 KB
testcase_21 AC 55 ms
70,584 KB
testcase_22 AC 42 ms
56,272 KB
testcase_23 AC 36 ms
53,460 KB
testcase_24 AC 37 ms
53,460 KB
testcase_25 AC 38 ms
53,460 KB
testcase_26 AC 39 ms
59,456 KB
testcase_27 AC 43 ms
61,984 KB
testcase_28 AC 41 ms
56,272 KB
testcase_29 AC 43 ms
61,824 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#Advent Calendar Contest 2023 - A Intriguing Triangle

'''
■余弦定理ごり押し版
AB,AC,AD,AE = b,c,d,e
BD,DE,EC = x,a,y
BD+DE+EC = z
∠ABC,∠ACB = B,C
∠BAD,∠CAE = θ1,θ2
と定義し、x,y(,z)の全探索を行う。

三角形の成立条件より、探索範囲を以下の通りに絞る。
b + c > z, c + z > b, z + b > c ･･･(1)

△ABCの余弦定理より
c^2 = b^2 + z^2 - 2bz cosB
b^2 = c^2 + z^2 - 2cz cosC ･･･(2)

∠ABC(=B),∠ACB(=C)に着目した△ABD,△ACEの余弦定理より
d^2 = b^2 + x^2 - 2bx cosB
e^2 = c^2 + y^2 - 2cy cosC ･･･(3)
(2)のcosB,cosCを(3)に代入し、両辺をz倍すると
zd^2 = zb^2 + zx^2 - x(b^2 + z^2 - c^2)
ze^2 = zc^2 + zy^2 - y(c^2 + z^2 - b^2) ･･･(4)
となる。(4)の右辺は整数型である。

∠BAD(=θ1),∠CAE(=θ2)に注目した△ABD,△ACEの余弦定理より
x^2 = b^2 + d^2 - 2bd cosθ1
y^2 = c^2 + e^2 - 2ce cosθ2 ･･･(5)

0° < θ1,θ2 < 180°のとき、θ1 = θ2 と cosθ1 = cosθ2 は等価である。
さらに cosθ1 = cosθ2 に対して(5)を代入・整理すると、条件は
ce(b^2 + d^2 - x^2) = bd(c^2 + e^2 - y^2) ･･･(6)
となる。

この式を愚直に評価したいのだが、d,eは整数型と限らないため誤差が生じる。
(誤差評価は行っていませんが、誤差を10^(-6)まで許容するとACするようです)
なので誤差が生じない、整数型での評価を目指す。

(6)の両辺を2乗後にz^3倍すると
c^2 * ze^2 * (zb^2 + zd^2 - zx^2)^2 = b^2 * zd^2 * (zc^2 + ze^2 - zy^2)^2 ･･･(7)
となる。ここでb,c,x,y,zは整数であり、(4)よりzd^2,ze^2も整数である。
従って(7)は整数型で評価可能である。

(7)の変形、もしかしたら b^2 + d^2 - x^2 > 0, c^2 + e^2 - y^2 > 0 の証明が必須？
△ABCが成立するとき、△ABD, △ACEも成立するので、三角形の成立条件より
b + d > x, c + e > y が成り立つ。両辺を2乗し、x^2やy^2を移項すると証明できる。
が、これは必要かは自信ありません


■誤差どうなるの(要検証)
直感的には、decimal.Decimalを使えば大丈夫。有効数字28桁。
float型(小数点以下16桁)だとちょっとまずそう。

(2)のcosB,cosCを(3)に代入した「だけ」だと
d^2 = b^2 + x^2 - (b^2 + z^2 - c^2)x/z
e^2 = c^2 + y^2 - (c^2 + z^2 - b^2)y/z ･･･(8)
となる。/zの部分で浮動小数点誤差が生じ、(8)で求めるd^2,e^2の誤差は高々10^-16。
√(10^-16) = 10^-8 なので、√を取ると誤差がでかくなる(適当)
のでd,eの誤差は高々10^-8としておく。

評価したい式は
ce(b^2 + d^2 - x^2) = bd(c^2 + e^2 - y^2) ･･･(6)
で、対称性から左辺と右辺の誤差評価結果は等しい。
とりあえず左辺を考えると、c(≒10^2) * e(最大誤差10^-8) * (d^2+e^2-x-2 (≒10^4))
なので誤差が10^-2までありえる、本当かこれ？実験するか。

ce(b^2 + d^2 - x^2) - bd(c^2 + e^2 - y^2) ･･･(9)
として、(9)の誤差を雑に探索。
本来正解(誤差 == 0)になるはずの場合、(9)は±2.9 * 10^-8 程度ぶれる。
(a,b,c,x,y,z) = (44,66,96,11,20,75), (40,98,70,9,5,54), (9,100,80,41,32,82) など

逆に本来不正解(誤差 != 0)の場合、(9)は± 4.2 * 10^-2 程度にまで迫る。
(a,b,c,x,y,z) = (67,69,25,7,1,75), (76,57,55,17,16,109), (34,22,63,1,7,42) など
10^-2に迫るのが怖いが、ともあれ本制約下では、
abs( (9) ) < 10^-2 ～ 10^-7 ならYes で評価すれば犯罪ACできる･･･と思う。
'''

#入力受取
a,b,c = [int(input()) for _ in range(3)]

#BD,DE,EC = x,a,y  BD+DE+EC = z として、x,y,zの全探索を行う
for z in range(a, b+c):
    #三角形の成立条件を確認
    if b+c <= z or c+z <= b or z+b <= c: continue

    #x,yの全探索
    for x in range(1,z):
        y = z-(x+a)
        if y<1: continue

        #zd^2,ze^2 = D,E として(4)を計算
        D = z * b**2 + z * x**2 - x * (b**2 + z**2 - c**2)
        E = z * c**2 + z * y**2 - y * (c**2 + z**2 - b**2)

        #(7)が成立するか確認
        if c**2 * E * (z * b**2 + D - z * x**2)**2 == \
           b**2 * D * (z * c**2 + E - z * y**2)**2:
            print('Yes'); exit()

#条件を満たす三角形がなければNoを出力
print('No')


#ここからデバッグ用
import math
from time import perf_counter as pf
from random import randint as ri
def check_clear(b,c,x,y,z):  #整数値で評価
    D = z * b**2 + z * x**2 - x * (b**2 + z**2 - c**2)
    E = z * c**2 + z * y**2 - y * (c**2 + z**2 - b**2)
    return (c**2 * E * (z * b**2 + D - z * x**2)**2)-\
           (b**2 * D * (z * c**2 + E - z * y**2)**2)

def check_about(b,c,x,y,z):  #小数点誤差を許容
    D = b**2 + x**2 - (b**2 + z**2 - c**2)*x/z
    E = c**2 + y**2 - (c**2 + z**2 - b**2)*y/z
    return c*math.sqrt(E)*(b**2 + D - x**2) - b * math.sqrt(D) * (c**2 + E - y**2)

def check_all():
    ans = []
    S = pf()
    corner = 10**18
    cb,cc,cx,cy,cz = 0,0,0,0,0
    for b in range(1,101):
        if b%10==0:
            print('progress:',b)
            print('section time:',pf()-S)
            S=pf()
        for c in range(1,101):
            for x in range(1,101):
                for y in range(1,101):
                    for a in range(1,101):
                        z = x+y+a
                        if b+c<=z or c+z<=b or z+b<=c: continue
                        if check_clear(b,c,x,y,z) == 0:
                            ans.append((check_about(b,c,x,y,z),b,c,x,y,z))
                        else:
                            p = check_about(b,c,x,y,z)
                            if abs(p) < abs(corner):
                                corner = p
                                cb,cc,cx,cy,cz = b,c,x,y,z
    return ans,corner,cb,cc,cx,cy,cz

def check_rand(time):
    S=pf()
    corner = 10**18
    ca,cb,cc,cx,cy,cz = 0,0,0,0,0,0
    while pf()-S < time:
        b,c,x,y,a = [ri(1,100) for _ in range(5)]
        z = x+y+a
        if b+c<=z or c+z<=b or z+b<=c: continue
        if check_clear(b,c,x,y,z) != 0:
            p = check_about(b,c,x,y,z)
            if abs(p) < abs(corner):
                corner = p
                ca,cb,cc,cx,cy,cz = a,b,c,x,y,z
    return corner,ca,cb,cc,cx,cy,cz
0