Problem C: Grated Radish ～大根おろし～

Problem C: Grated Radish
～大根おろし～
成績
• Submit 数：0
• Accept 数：0
• 問題セットの中で最難問題なので解けなくて
も仕方が無いかなと思いつつ，1チーム位
submit して欲しかった
回転してしまえ
• “ 方向から削る”と難しいこと言っているが
全体を
回転させ，指定の面積削ってま
た回転させればよい
• 切断する直線は x 軸垂直方向に限定できる
求積とデータ構造
• 断面の外周を左回りになるように線分と弧を
登録すると場合分けが一切要らない
• 正の面積と負の面積が相殺してくれる
+
ー
+
ー
+
難しいポイント
• 削られる角度と面積ではどれだけ削っていい
かわからない
•
と削られる面積は表されるが
この方程式は簡単には解けない
θ
二分法の導入
• 常に断面は凸図形よって削られる面積は削
られる深さに対して単調増加
• どこまで削るかの深さをパラメータとして目標
の表面積だけ削られるように二分法を実行
xxx
二分法（バイナリサーチ）
• 関数
– 条件
– 関数は単調
– 関数は連続
– 関数は簡単
となる
を高速に求める手法
二分法の動作例
x^2 = 0.5 を解く
中点
= 0.5
0.0x<=
x <=をテスト
1.0 は明らか
x^2 = 0.5 の解は
0.5
x <=
1.0
と判明
中点<=
x=
0.75
をテスト
x^2 = 0.5 の解は
1.0
0.5 <=
<= 0.75
と判明
中点
x =x0.625
をテスト
x^2 = 0.5 の解は
0.563
0.517
0.473
0.391
0.25
0.625 <= x <= 0.75 と判明
中点 x = 0.6875 をテスト
x^2 = 0.5 の解は
0.6875 <= x <= 0.75 と判明
0.0
0.5
0.625
0.6875
0.75 1.0
0.71875
中点 x = 0.71875 をテスト．．．
二分法の作り方
• 解が存在する十分大
きな区間から開始
• 区間の中間値に関
数を適用して区間を
狭める
• 以降繰り返し
二分法の擬似コード
xmin = 十分に小さな値;
xmax = 十分に大きな値;
while(xmax - xmin > ε){
xmid = 0.5*(xmax + xmin);
if(f(xmid) < y)xmin = xmid;
else xmax = xmid;
}
二分法の応用
• 最大値
– 条件を満たすならば下限の値を大きくし，満たさ
ないならば上限の値を小さくしていく
– 例：文字列s1, s2, s3 に共通する最長部分文字
列の長さ
• n 番目の値
– ある値以下には何個要素があるという関数を簡
単に実行できる場合に二分法を使うことが出来る
– 例：m 以下の二数の積の中で n 番目の値
楽をしようと（参考）
• java.awt.geom.*;
–
–
–
–
–
–
–
AffineTransform : Affine変換をしてくれるクラス
Ellipse2D : 円
Line2D : 直線
Point2D : 点
Area : 領域の和、差、積などを簡単に作れる
PathIterator : Areaの領域をたどる
などなど
• これを使うとさっくりかけます
– 交線判定、内点判定などなど超便利
が、
• 誤差ではまる。
– 円がQubicBezierで近似してたり
– 切ると、短い線分がなぜか出てきたり
• そんなわけで今回は使えません。（ぉ
– 誤差の許容をどうがんばっても超えるので
– でも、便利なので、Javaを使うチームはちょっとくらいAPI
みてもいいかも。
• 使うには要慣れ、本番でいきなりつかわないよーに（笑

Download Report