Problem C: Grated Radish ～大根おろし～. 成績 Submit 数： 0 Accept 数： 0 問題セットの中で最難問題なので解けな くても仕方が無いかなと思いつつ， 1 チー ム位 submit して欲しかった.

Presentation on theme: "Problem C: Grated Radish ～大根おろし～. 成績 Submit 数： 0 Accept 数： 0 問題セットの中で最難問題なので解けな くても仕方が無いかなと思いつつ， 1 チー ム位 submit して欲しかった."— Presentation transcript:

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

2 成績 Submit 数： 0 Accept 数： 0 問題セットの中で最難問題なので解けな くても仕方が無いかなと思いつつ， 1 チー ム位 submit して欲しかった

3 回転してしまえ “ 方向から削る ” と難しいこと言っている が全体を 回転させ，指定の面積削っ てまた 回転させればよい 切断する直線は x 軸垂直方向に限定でき る

4 求積とデータ構造 断面の外周を左回りになるように線分と 弧を登録すると場合分けが一切要らない 正の面積と負の面積が相殺してくれる + + + ー ー

5 難しいポイント 削られる角度と面積ではどれだけ削って いいかわからない と削られる面積は表されるが この方程式は簡単には解けない θ

6 二分法の導入 常に断面は凸図形よって削られる面積は 削られる深さに対して単調増加 どこまで削るかの深さをパラメータとし て目標の表面積だけ削られるように二分 法を実行 x x x

7 二分法（バイナリサーチ） 関数 となる を高速に求める手 法 – 条件 – 関数 は単調 – 関数 は連続 – 関数 は簡単

8 二分法の動作例 0.5 0.25 0.75 0.563 0.625 0.391 0.6875 0.473 0.71875 0.01.0 0.517 x^2 = 0.5 を解く 0.0 <= x <= 1.0 は明らか 中点 x = 0.5 をテス ト x^2 = 0.5 の解は 0.5 <= x <= 1.0 と判明 中点 x = 0.75 をテス ト x^2 = 0.5 の解は 0.5 <= x <= 0.75 と判明 中点 x = 0.625 をテスト x^2 = 0.5 の解は 0.625 <= x <= 0.75 と判明 中点 x = 0.6875 をテス ト x^2 = 0.5 の解は 0.6875 <= x <= 0.75 と判明 中点 x = 0.71875 をテス ト．．．

9 二分法の作り方 解が存在する十分 大きな区間から開 始 区間の中間値に関 数を適用して区間 を狭める 以降繰り返し 二分法の擬似コード xmin = 十分に小さな値 ; xmax = 十分に大きな値 ; while(xmax - xmin > ε){ xmid = 0.5*(xmax + xmin); if(f(xmid) < y)xmin = xmid; else xmax = xmid; }

10 二分法の応用 最大値 – 条件を満たすならば下限の値を大きくし，満 たさないならば上限の値を小さくしていく – 例：文字列 s1, s2, s3 に共通する最長部分文 字列の長さ n 番目の値 – ある値以下には何個要素があるという関数を 簡単に実行できる場合に二分法を使うことが 出来る – 例： m 以下の二数の積の中で n 番目の値

11 楽をしようと（参考） java.awt.geom.*; –AffineTransform : Affine 変換をしてくれるクラス –Ellipse2D : 円 –Line2D : 直線 –Point2D : 点 –Area : 領域の和、差、積などを簡単に作れる –PathIterator : Area の領域をたどる – などなど これを使うとさっくりかけます – 交線判定、内点判定などなど超便利

12 が、 誤差ではまる。 – 円が QubicBezier で近似してたり – 切ると、短い線分がなぜか出てきたり そんなわけで今回は使えません。（ぉ – 誤差の許容をどうがんばっても超えるので – でも、便利なので、 Java を使うチームはちょっとく らい API みてもいいかも。 使うには要慣れ、本番でいきなりつかわないよーに（笑