人工知能と競プロやってくブログ

深層学習・機械学習・AI・atcoder・競技プログラミングについて調べてやってみたことをまとめるブログです

AtCoder Beginner Contest 144 [ D - Water Bottle ]をPythonで解く(400点、🟫茶diff、図形問題)

問題

atcoder.jp

数学問題。

解法

水の体積が、水筒の半分以下か以上かで処理が異なる。

水の体積が水筒の半分以下のとき

半分以下の時、水は三角柱の形でこぼれる。

f:id:uchidamax:20210805233400p:plain
水の体積が半分以下

θの角度が求める答え。

水の面積 x / a
水の底辺yの値を求める。三角形の面積の公式から
x / a = b * y /2
これをyについて解く。両辺に2をかけて
2 * x / a = b * y
y = 2 * x / (a * b)

ここまでとけたら、atanを計算すればθは出る。
atan(b / y)

水の体積が水筒の半分以上のとき

半分以下の時、水は台形でこぼれる。

f:id:uchidamax:20210805233733p:plain
水の体積が半分以上
θの角度が求める答え。

水の面積 x / a
水筒の面積 a * b
水筒の空気部分の面積 a * b - x / a (水筒の面積 - 水の面積)

水筒の空気部分の三角形の辺yの長さを求める。
三角形の面積の公式から
a * b - x / a = a * y / 2
これをyについて解く
2 * a * b - 2 * x / a = a * y
y = 2 * b - 2 * x / a2

ここまでとけたら、atanを計算すればθは出る。
atan(y / a)

実装

参考

blog.hamayanhamayan.com

https://img.atcoder.jp/abc144/editorial.pdf