こんばんは。 です。
この記事は partake.in 8日目の記事です。
昨年 (競技プログラミング アドベントカレンダー Div.2013 3日目 - pepsin-amylaseの日記 - TopCoder部) に引き続き、数学の勉強をしましょう。
まずは微分です。これは基本的には「関数の最小値/最大値を見つけたい時」に便利です。その根拠となる定理を紹介します。
有界閉集合上で定義された微分可能な関数は必ず最大値と最小値を持ち、それを与える定義域上の点は以下に限られる（必要条件）。
前半はいわゆる最大値の定理です。後半が大事で、条件に列挙された点、つまり基本的には微分して0になるところを調べ尽くせばよいわけです。紙と鉛筆で数学をやっているときはもう少し強い条件が欲しくなる（たとえば wikipedia:鞍点 を取り除くためにヘッセ行列を調べるなど）ところですが、プログラミングコンテストですので、有限の点が列挙できたらあとは基本的にコンピュータに調べさせましょう。
プログラミングコンテストでよくある目的関数として、いくつかの関数の min, max をつなげたものが挙げられます。たとえば、次の問題を考えてみましょう。
平面上にn点が与えられる。n点からの距離の最大値が最小になる点Aを探し、そのときの最大の距離を出力せよ。
いわゆる最小包含円の問題ですが、これを点Aに関する最小化問題として定式化すると、目的関数は max(点1からの距離, 点2からの距離, ..., 点nからの距離) となります。それぞれの距離の関数は三平方の定理を用いて書き下せば微分可能であることがわかります。さて、このように微分可能な関数が min/max で繋がれている場合はどうすればいいでしょうか。
この場合は最大距離を与える点ごとに定義域を分割するのが効果的です。つまり、平面を点1が最も遠くなるような点、点2が最も遠くなるような点、と言った具合に分割します。こうするとそれぞれの分割された領域内で目的関数は距離関数となり微分可能ですので先の定理を使えます。今回の場合、点が2個以上の場合はそれぞれの定義域内に停留点が存在しない (停留点は最大距離を与える点そのものに限られるが、そこは定義域に含まれない) ので境界のみを調べればよいことになります。
あとは同様に議論を繰り返すことで、境界の線分（垂直二等分線）の入れ替わる点である3点からの距離が等しくなるところと境界の線分が最小になる場合、つまり2点の中点をすべて列挙すればよいというよく知られた結論が得られます。
min, max にかぎらず、有限の点で微分可能でない場合にはこのように区間を分割して、分割の境界も調べれば十分です。
Code Festival 2014 あさぷろ Hard の D 問題です。問題はこちら。D: Rail Tour - CODE FESTIVAL 2014 Hard | AtCoder
平面上に高速に動ける折れ線があり、ここでは速度 v で動ける。それ以外のところでは速度 1 で動ける。スタートとゴールの点が与えられるので所要時間を求めよ。
http://www.slideshare.net/amylase/rail-tour 自分で作ったスライドなので手抜きって言わないでください！！！！
基本的には経由点が有限であることを示すために微分を使っています。
これまで見てきた問題では基本的に変数が定義域上を自由に動けたものでした。ではこれらの変数の動きが等式によって制限されている場合はどうすればよいでしょうか。
この場合は wikipedia:ラグランジュの未定乗数法 を使うのがプログラミングコンテストにかぎらず一般的です。
これによって等式を消去し、普通の最小化問題として解くことができるようになります。
2011年の JAG 冬コンテストからの問題です。問題はこちら。no title
n (< 8) 人が原点から一斉に分速 v_i で移動する。1分後にこの n 人が作る凸包の面積を最大化せよ。
n 人の順番を固定するとそれぞれの人達がなす角を変数とした目的関数が書けます。これはなす角の和が360度という等式制約のもとでの最大化問題なのでこれに対してラグランジュの未定乗数法を適用すればOKです。
cos さんのブログにより詳しい解説が乗っています。 Hull Marathon (AOJ 2373) - cos65535の日記
tozangenzan さんのブログに幾何的な考察による方針が示されています。コードに落ちる段階で同じような感じになります。 AOJ 2373: HullMarathon - tozangezan's diary
この場合は wikipedia:KKT条件 がよく知られています。
これはラグランジュの未定乗数法を不等式制約を扱えるように一般化したものです。特に重要なのはWikipediaの最後に「スラック変数に関する条件」として示されている条件で、これには相補性条件という名前がついています。これは本質的には、次の場合分けを示したものです。
今年の台湾での地区予選の問題から。問題はこちらの L 問題です。 http://icpc2014.pu.edu.tw/2014%20ACM-ICPC%20Problem.pdf
https://twitter.com/h_chiro/status/536003833604743168
（ジャッジが見つからなかったのでこの解法が正しい保証はないです、すみません）
問題がまず不等式制約付き最小化問題なのでKKT条件の適用を考えます。相補性条件に着目すると、次の場合分けをすればよさそうです。
t_2, ..., t_n について、
上2つが等号成立する場合で、一番下が等号成立しない場合です。各変数についてすべて場合分けした 3^(n-1) (< 4782969) 通りについて制約なしの最適化問題だと思って解きます。等号成立しない場合の制約については、それが実行可能解であるかどうかをきちんと確かめる必要があります。実行可能解でない場合は不等式制約をどちらかに突き抜けているはずで、この場合は目的関数の凸性からどちらかの等号が成立している場合が最適になるので無視してOKです。
蟻本第2版の幾何パートで説明されていますので詳細はそちらに。
多角形や多面体の面積を求める際に使われるテクニックです。被積分関数が2次以下であるという性質を活かして wikipedia: シンプソンの公式 で誤差なく積分することができます。
確率を扱う問題においては点が平面上を動いたり複数の点が線分上を動く場合があります。このような場合にはそれぞれの点が選ばれる確率密度を考えるのが一般的な手法です。そして、その関数を定義域のうち条件が満たされる部分を積分領域に取って積分することで確率を求めます。
2011年の模擬国内予選です。問題はこちら no title
平面上に 2N (N < 100) 個の点がある。これをランダムにえらんだ直線を用いて分割する。これにより N 個ずつに分割される確率を求めよ。
2つの点が独立に一様に選ばれるので、同時分布は一様分布になります。従って積分領域の面積を求めればよいことになります。
片方の点を固定したときの偏角ソートを考えるとよいです。この時のもう片方の取りうる部分の長さ (スライドの y2) を積分します。被積分関数が変化する点で区間を分割し、各区間は y2 が線型に変化することから台形公式で誤差なく積分できます。区間の分割点を洗い出すには偏角ソートの順番が入れ替わる部分である2つの点を結んで得た直線との交点と、y2 の区間のうちの片方が端に到達する部分である1つの点と長方形の頂点を結んで得た直線との交点を調べれば十分です。
2013年の夏合宿4日目が類題です。問題はこちら。 H: Gravity Point - Japan Alumni Group Summer Camp 2013 Day 4 | AtCoder
実は去年の記事を書いた段階で、線形代数の次だから2014年は微積分にしようと考えていました。来年は確率統計にしようか幾何にしようかという感じですが、どっちも闇が深そうなので戸惑っています。
内容としては学部初級レベルの知識を必要とする問題の解説になった感じですが、区間を大量に分割してコンピュータに全場合を検討させるなど、特有のテクニックも多少あったかと思います。これより詳しい話は最適化ガチ勢の人に聞いてください。
明日はマラソン部門から colun さんの「オーバーフィッティング回想録」と not_522 さんの「幾何の小手先テクn選」です。どちらもその道のプロによる記事で非常に楽しみですね！