結果
| 問題 | No.2555 Intriguing Triangle |
| ユーザー |
 navel_tos
|
| 提出日時 | 2023-12-01 21:33:47 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 55 ms / 2,000 ms |
| コード長 | 6,293 bytes |
| コンパイル時間 | 236 ms |
| コンパイル使用メモリ | 82,048 KB |
| 実行使用メモリ | 69,604 KB |
| 最終ジャッジ日時 | 2024-09-26 15:54:50 |
| 合計ジャッジ時間 | 2,435 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 41 ms
54,648 KB |
| testcase_01 | AC | 42 ms
55,092 KB |
| testcase_02 | AC | 41 ms
54,912 KB |
| testcase_03 | AC | 42 ms
55,168 KB |
| testcase_04 | AC | 45 ms
56,320 KB |
| testcase_05 | AC | 39 ms
52,608 KB |
| testcase_06 | AC | 43 ms
54,784 KB |
| testcase_07 | AC | 44 ms
54,656 KB |
| testcase_08 | AC | 39 ms
53,120 KB |
| testcase_09 | AC | 40 ms
53,632 KB |
| testcase_10 | AC | 53 ms
64,768 KB |
| testcase_11 | AC | 40 ms
52,992 KB |
| testcase_12 | AC | 50 ms
63,744 KB |
| testcase_13 | AC | 41 ms
54,144 KB |
| testcase_14 | AC | 47 ms
62,080 KB |
| testcase_15 | AC | 41 ms
59,392 KB |
| testcase_16 | AC | 44 ms
60,672 KB |
| testcase_17 | AC | 41 ms
54,272 KB |
| testcase_18 | AC | 43 ms
56,064 KB |
| testcase_19 | AC | 41 ms
54,656 KB |
| testcase_20 | AC | 37 ms
52,224 KB |
| testcase_21 | AC | 55 ms
69,604 KB |
| testcase_22 | AC | 41 ms
54,656 KB |
| testcase_23 | AC | 38 ms
52,864 KB |
| testcase_24 | AC | 37 ms
52,820 KB |
| testcase_25 | AC | 40 ms
53,248 KB |
| testcase_26 | AC | 39 ms
58,240 KB |
| testcase_27 | AC | 44 ms
60,416 KB |
| testcase_28 | AC | 40 ms
54,624 KB |
| testcase_29 | AC | 43 ms
60,800 KB |
ソースコード
#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