Hatena::Grouptopcoder

pepsin-amylaseの日記

 | 

2014-12-08競技プログラミングのための微積分

微分

22:47

まずは微分です。これは基本的には「関数の最小値/最大値を見つけたい時」に便利です。その根拠となる定理を紹介します。

有界閉集合上で定義された微分可能な関数は必ず最大値と最小値を持ち、それを与える定義域上の点は以下に限られる(必要条件)。

  • 定義域の境界
  • 停留点、すなわち勾配が零ベクトルになる。

前半はいわゆる最大値の定理です。後半が大事で、条件に列挙された点、つまり基本的には微分して0になるところを調べ尽くせばよいわけです。紙と鉛筆で数学をやっているときはもう少し強い条件が欲しくなる(たとえば wikipedia:鞍点 を取り除くためにヘッセ行列を調べるなど)ところですが、プログラミングコンテストですので、有限の点が列挙できたらあとは基本的にコンピュータに調べさせましょう。

min, max の扱い

プログラミングコンテストでよくある目的関数として、いくつかの関数の min, max をつなげたものが挙げられます。たとえば、次の問題を考えてみましょう。

平面上にn点が与えられる。n点からの距離の最大値が最小になる点Aを探し、そのときの最大の距離を出力せよ。

いわゆる最小包含円の問題ですが、これを点Aに関する最小化問題として定式化すると、目的関数は max(点1からの距離, 点2からの距離, ..., 点nからの距離) となります。それぞれの距離の関数三平方の定理を用いて書き下せば微分可能であることがわかります。さて、このように微分可能な関数が min/max で繋がれている場合はどうすればいいでしょうか。

この場合は最大距離を与える点ごとに定義域を分割するのが効果的です。つまり、平面を点1が最も遠くなるような点、点2が最も遠くなるような点、と言った具合に分割します。こうするとそれぞれの分割された領域内で目的関数は距離関数となり微分可能ですので先の定理を使えます。今回の場合、点が2個以上の場合はそれぞれの定義域内に停留点が存在しない (停留点は最大距離を与える点そのものに限られるが、そこは定義域に含まれない) ので境界のみを調べればよいことになります。

あとは同様に議論を繰り返すことで、境界の線分(垂直二等分線)の入れ替わる点である3点からの距離が等しくなるところと境界の線分が最小になる場合、つまり2点の中点をすべて列挙すればよいというよく知られた結論が得られます。

min, max にかぎらず、有限の点で微分可能でない場合にはこのように区間を分割して、分割の境界も調べれば十分です。

例題 Rail Tour

Code Festival 2014 あさぷろ Hard の D 問題です。問題はこちら。D: Rail Tour - CODE FESTIVAL 2014 Hard | AtCoder

問題概要

平面上に高速に動ける折れ線があり、ここでは速度 v で動ける。それ以外のところでは速度 1 で動ける。スタートとゴールの点が与えられるので所要時間を求めよ。

解法

http://www.slideshare.net/amylase/rail-tour 自分で作ったスライドなので手抜きって言わないでください!!!!

基本的には経由点が有限であることを示すために微分を使っています。

等式制約がある場合

これまで見てきた問題では基本的に変数が定義域上を自由に動けたものでした。ではこれらの変数の動きが等式によって制限されている場合はどうすればよいでしょうか。

この場合は wikipedia:ラグランジュの未定乗数法 を使うのがプログラミングコンテストにかぎらず一般的です。

これによって等式を消去し、普通の最小化問題として解くことができるようになります。

例題 HullMarathon

2011年の JAG 冬コンテストからの問題です。問題はこちら。HullMarathon | Aizu Online Judge

問題概要

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の最後に「スラック変数に関する条件」として示されている条件で、これには相補性条件という名前がついています。これは本質的には、次の場合分けを示したものです。

  • 不等式制約が等号成立する場合、それは等式制約である。
  • 不等式制約が等号成立しない場合、それでよいので関数は初めからなかったものと思う (ゆえにスラック変数は 0 になる)。

例題 Security System

今年の台湾での地区予選の問題から。問題はこちらの L 問題です。 http://icpc2014.pu.edu.tw/2014%20ACM-ICPC%20Problem.pdf

問題概要

https://twitter.com/h_chiro/status/536003833604743168

有理数と書かれている部分はもとの問題では実数です。

解法

(ジャッジが見つからなかったのでこの解法が正しい保証はないです、すみません)

問題がまず不等式制約付き最小化問題なのでKKT条件の適用を考えます。相補性条件に着目すると、次の場合分けをすればよさそうです。

t_2, ..., t_n について、

  • 1つ左との差が 0
  • 1つ左との差が alpha
  • それ以外

上2つが等号成立する場合で、一番下が等号成立しない場合です。各変数についてすべて場合分けした 3^(n-1) (< 4782969) 通りについて制約なしの最適化問題だと思って解きます。等号成立しない場合の制約については、それが実行可能解であるかどうかをきちんと確かめる必要があります。実行可能解でない場合は不等式制約をどちらかに突き抜けているはずで、この場合は目的関数の凸性からどちらかの等号が成立している場合が最適になるので無視してOKです。

 |