こんばんは。 です。
この記事は 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選」です。どちらもその道のプロによる記事で非常に楽しみですね！
ほんとは昨日の夜書くつもりだったのだけど、なんか眠かったのでズレました。
基本的に推敲せず書きっぱなしです。ほとんど自分用メモ。
今年の参加記に興味がある人はそこまでジャンプしてください。
クラスの友人に誘われて実践的プログラミングの講義を取ったのが ICPC との出会いでした。
誘ってきた友人は5月頃にあっさり授業を切ってしまい、当然ほかに知り合いもいないぼく1人で寂しくプログラムを書いていました。
この講義では最終的に履修者でチームを作って ICPC に出るのですが、このような状態ですので金子先生の「はい3人組つくってー」攻撃で困っていたところに atetubou が救いの手を差し伸べてもらったのが彼との出会いでした。
ぼくと atetubou ともう1人の女の子（彼女は予選当日に用事があって結局2人で戦うことになった）のチームで初めての ICPC に挑むことになったわけです。
とはいっても全員がこの講義で競技に入門した初心者。当時のぼくはソートが必要なときにバブルソートを再発明して頑張っていたようなレベルで、当然勝てるわけはありませんでした。
コンテスト自体は、当時の実力を考慮すれば奇跡的なのですがぼくがCのDPを思いついて3完し39位でした。
結果はこちら: http://icpc2010.honiden.nii.ac.jp/domestic-contest/result
atetubou にさそわれこの年も ICPC に出ることにしたのですが、もう1人をどうするかという問題がありました。どうしようかと困っていたところにちょうど ICPC に興味を示した当時知り合ったばかりの学科の同期 y3eadgbe がチームに参加したいということでめでたく atetubou, y3eadgbe, amylase というチームでICPCに出ることと相成りました。
このチームでは結局3回ICPCに出て、そのうち1回は幸運にも国内予選を突破できたのでICPCのことを考えるときはまず真っ先にこのチームのことが思い起こされます。
この年は特にICPCに向けて何かをした覚えはありませんが、ちょうどこの時期に本郷へ進学して地下生活を始めると同時に simezi_tan に布教されてTopCoder SRMに継続的に参加するようになりました。
その甲斐あってか、この年は4完だったように思います。公式サイトが死んでいて standings が確認できないですが。
この年に atetubou も理学部情報科学科に進学し、完全地下チームとなりました。
この年は ~shiokawa, wakaba の面々と毎週3回地下に集合し、AOJ Virtual Arena で開かれている会津大の練習会に参加しました。今思えばこの時に競技力が高まった気がします。
ぼくは基本的に演習量が足りていなかったので、練習会でいろんな問題に触れるうちに問題のパターンを覚え、解ける問題がどんどん増えていく時期でした。競技に限らず物事を学ぶ上で一番楽しい段階ですね。
その中でも一番重点的に力を注いだ分野が幾何です。練習会で毎回幾何が出るたびにぼろぼろと取りこぼし、これはちょっとまずいのではないかと思い、ライブラリづくりを兼ねて幾何の勉強をしました。
いろんな人が言っていると思いますが、幾何の勉強法はライブラリ整備を兼ねて簡単な問題から順に解いていくのが一番効果的だと思います。こんどそのための幾何問題集とか作れたらいいなあ。
練習会で atetubou が実装力で頭ひとつ抜けていることもわかったので、ぼくとy3が一生懸命アルゴリズムを考えてatetubouに実装してもらうのを基本戦略に据えました（幾何がでたらぼくが書きます）。並列せず前列と後列にわかれるスタイルですね。
この年の国内予選はこれらの対策がバッチリあたり、なんと全体3位という予想外の好成績で国内予選を突破します。 http://www.cs.titech.ac.jp/icpc2012/domestic-contest-result.html
C, D のややこしい実装は実装担当として鍛錬を積んだatetubouの敵ではなく、Eに解ける幾何が来たことで5完を達成しました。
この年も国内予選突破を目指し日夜練習……にはあまり励みませんでした。ぼくが国立情報学研究所にある研究室に配属されたのもあって、本郷の地下から疎遠になってしまったからです。
結果、この年は7位（学内5位）で国内予選落ちです。 http://sparth.u-aizu.ac.jp/icpc2013/d_result.php
今見返せば、この年が東大1強の最たる年だったような気がしてきますね。
去年の練習不足により、atetubouから三行半をつきつけられたぼくとy3。
そこにちょうどチームメイトが2人とも引退してフリーになっていた not さんを引き込み、国内予選突破を目指すことにしました。
成功した2012年の方針を踏襲し、会津練習会に毎週参加してチームとしての動きを確認しながら練習を重ねました。
模擬予選では5位（学内4位）に食い込み、「いけるか……？」という雰囲気で本番を迎えます。
動きとしては A, B, C を個人がそれぞれとき、Dをy3が解いている間にEまで方針を詰めてぼく & not で最後の方に出てそうな幾何の問題を詰めに行くというのを予定していました。
競技開始と共にy3が問題を読みさくっと実装。サンプルが合わないトラブルがありBのnotさんと交代するも問題の誤読とわかり修正して提出、AC。
ぼくがCを詰めている間にAC。
ぼくがCに取り組んでいる間に not さんが「これは一瞬なので」ということを見ぬいたので、PCを交代。
ちょっと実行に時間がかかったものの予定通りさくっと提出。
→WA
すぐにコードを印刷してCに交代。
これまたすぐにバグを発見して修正し、Dを走らせ直しながらCに復帰。
→AC
見た瞬間に二分探索を検討しましたが、そのあとの入ってるかどうか判定する部分で自信がなくなり not さんに相談すると「外側の端の点だけ見ればよくてそれで時間が一意になるからにぶたんいらないです」という旨のコメントをいただく。
にぶたんのまま書いてたら結構実装などが面倒だったと思われるのでちゃんと相談してよかった。
→AC
D を書いている間（Cを書く前）にy3と相談。
葉につながる辺は通らなくてよいことに気づき残った木の上でいかに通る回数をケチるか考えていくと、どうも直径部分だけは1回であとは2回とおればいいのではないかという結論に至りました。証明はしていないのですが、sampleも会うし結構あってそうなのでこれで行くことに。
→WA
コードを見ると木の直径を見るときに辺のコストを考慮しないようになっていたのでそれを指摘し再提出。
→WA
実はさっきの嘘解法なのでは……とかと不安になっていたがバグを発見し再提出。
→AC
この段階で3WAを背負ってしまい6問通さないことには苦しい展開。
Fは辞書順最小の定石で可能性判定をかければいいということになっていて、Gはやらないだけの幾何の匂い。
ここでさいころの各面を頂点とし、隣接する面同士に辺を貼ったグラフを考えれば、それぞれの頂点を訪れる回数がt_iになるパスがあればよいことに not さんが気がつく。
これは練習会の時に似た問題を見たことがあって、たしかフローで解けるはずとぼくが思い出し、この方針で行くことに。
F を書くも最後のサンプルが合わず。
y3がフローが流れている場合でも連結なパスが再現できるとは限らないことに気が付き修正。
終了10分前にサンプルが合い祈りながら走らせるも終了したのは競技終了10分後……。
というわけで5完の16位でした。 http://icpc.iisf.or.jp/2014-waseda/domestic/results/
あとでGについて他のチームと話していて「3 つ以上の円が共通領域もしくは共通点をもつことはない．」と問題に書いてあるらしいことがわかり、not, y3ではじめに検討していたらしい方針でちゃんと解けるっぽいことが判明し絶望。基本的には円の内側で分断されないので中心を結んだ線分でグラフ双対やる感じだったらしいとのこと。
おそらく文章に主題がないからだと思いますが、なんかあとで読み返すと本当にまとまりがない文章でした。まあ2011年あたりの力をつけていく部分などは少しは参考になるのではないかなあと思います。
海外の地区大会に出るかどうかは未定です。もし行くことになったら一緒に行く方はよろしくお願いします、行かないことになったらJAGの皆さんよろしくお願いします。
この記事は partake.in の3日目に当たる記事です。
こんばんは。 です。
今日は競技プログラミングのための線型代数と題しまして、みなさんの大好きな数学の勉強をしてもらうために筆を執りました。よろしくお願いします。
本記事は次の知識を仮定します。知らない人は超特急で仕入れましょう。
本記事は線形代数っぽい問題での考え方に重きをおいた解説をしていますので、次の知識があると読みやすいです。
つぎのような連立一次方程式を考えます。
もちろんみなさんは解けますよね？
上の式の 2 倍を下の式から引いて
下の式を -1 倍して
下の式の 2 倍を上の式から引いて
このように項を消して整理していくことで解を得ます。
実はこの連立一次方程式は行列の形て次のように書きなおすことができます。
実際に成分を計算することでもとの連立一次方程式と同値であることがわかります。
一般に n 元 m 連立の一次方程式は m 行 n 列の行列を用いて書きなおすことができます。各行がひとつの等式に対応します。
このように書きなおした行列の方程式についても、冒頭で項を消して整理するのと同じ操作をすることで解くことができます。これがいわゆる掃き出し法です。蟻本にも載っていますし、ライブラリとして持っている方も多いかと思います。
典型的な実装は、係数行列に定数ベクトルの列を追加した拡大係数行列に対して掃き出していくものです。蟻本の実装もそうなっています。
掃き出し法をもちいて、昨年度のアジア地区予選の問題を解いてみましょう。
問題はこちらです。no title
ある d 次多項式 f が存在し、入力として f(0), f(1), ..., f(d+2) が与えられる。ただし、入力のうちちょうど1つは誤った値である。誤った値がどれであるか指摘せよ。
とおくと、入力の各値を用いてに関する連立一次方程式を立てることができます。これを用いると f を決定することができますが、このとき入力値の選び方により2通りの場合にわかれます。
前者は自明ですね。では後者について証明しましょう。d 次多項式は通る d+1 点を指定すると一意に定まるという定理 *1 を用います。残った値が正しく再現できているとすると、構成した多項式と使った入力値のうち正しいものと再現しようとした点を用いて決まる多項式は同一となるはずですが、前者はもとの f とは異なるものに一意に定まっているはずで後者は f にほかならないので矛盾します。
この事実を用いて、各点を外して連立一次方程式を立てることを繰り返せば解けます。
さて、いろいろな連立一次方程式に掃き出し法を適用していくと、様々なケースに出会います。
まずはこちらのケース。
これに掃き出し法を適用すると、途中でに次のようになります。
最後の式がおかしいですね。このような連立一次方程式は不能であるといい、解が存在しません。
次はこちら。
先ほどの例に似ていますが、最後の定数が違います。こちらに掃き出し法を適用すると次のようになります。
この場合は z を移項し
とすることで、z をパラメータとした解を表示する事ができます。この場合は連立一次方程式が不定であるといい、解が複数存在します。
さて、連立一次方程式の解には3つの場合があることがわかりました。
このような状態を調べるために、線型代数で用いられる行列の階数（ランク）を定義します。今回は、競技プログラミングに適した形で導入します。
これを用いて、次のようにして解の様子を調べることができます。
掃き出し法は連立方程式の解を変えずに変形を繰り返すアルゴリズムです。係数行列と拡大係数行列の階数が異なるとき、掃き出し法の終了後の行列は不能な連立一次方程式の例のように定数ベクトルの部分だけに非ゼロの成分が残ります。これは 0 = 1 を意味し、矛盾します。したがって、この場合には解が存在しないのです。
先に述べたように掃き出し法は解を保存しますので、係数行列のランクは連立方程式を解くときに変数をいくつ消去することができるかを示していると解釈できます。したがって、これによってちょうど変数が全て消去できるならばそれが一意の解となり、余る変数があるならば余った変数を用いて解のパラメータ表示ができるので解は複数個あることになります。ちなみに、このときのパラメータの個数を解の自由度と呼びます。一意解が存在することは解の自由度が 0 であるともいえます。
今年の JAG 春コンテストから例題を1つ解いてみます。
問題はこちらです。J: Tree Reconstruction - Japan Alumni Group Spring Contest 2013 | AtCoder
有向グラフが与えられる。ここに非負流量の循環フローが流れていることがわかっている。すなわち、各辺に非負の流量が設定されていて、各頂点は流量保存則を満たす。あなたは各辺の流量を知らないが、できるだけ少ない辺を調べてすべての辺の流量を決定したい。いくつの辺を調べればよいか求めよ。
頂点 v に関する流量保存則は v に入る辺の流量の和と v から出る辺の流量の和が等しいというもので、これは各辺の流量を変数と見た時に一次式です。したがって、すべての頂点について立式して連立することで連立一次方程式を得ます。この連立一次方程式はすべての流量が 0 という自明解を持ちます（フローが全く流れない場合に対応します）ので、不能ではありません。不能でないとき、連立一次方程式は解の自由度を持ちますが、これは消去しきれずに残った変数の個数のことでした。したがって、この残った変数の値（= ある辺での流量）がわかれば、解が一意に定まることになります。以上の議論から、出力すべき答えはこの連立一次方程式の解の自由度で、これは掃き出し法によって求められます。
出題者による解説もあります。
SRM 590 の Div.1 Medium 問題に、連立一次方程式の解の数え上げによって解く問題が出題されました。
問題はこちらです。TopCoder Statistics - Problem Statement
いくつかの非負整数が書かれたカードが与えられる。このカードの部分集合のうち、部分集合すべての xor を取った値が、ある整数 limit 以下になるようなとり方は何通りあるか求めよ。
xor sum について考えます。例えば、limit が 22 = 0b10110 であったとき、考えられる xor sum は次のようになります（? は don't care）。
要するに、1 が立っているところを 0 にして以下を don't care にしたものを列挙しています。これらの表す集合は互いに重複しないので、それぞれの場合について考えます。たとえば xor sum = 0b100?? のときについて考えます。
カードの数を 18, 6, 20、各カードを選択するかどうかをとすると、
これを bit wise に考えると、例えば最上位ビットは次のようになります *2。
これを定数が don't care でない各ビットについて連立させた方程式の解の個数を数え上げればよいことになります。これは mod 2 上での連立一次方程式です。mod を取るときの話をしていませんでしたが、mod を取る数が素数の場合は基本的には割り算のところを修正する（逆元を掛けるようにする）だけで問題なく掃き出し法が使えます。実際に掃き出し法を行うことで、解のパラメータ表示を得ます。このとき、各パラメータが 0, 1 のみを取ること、パラメータが異なれば解も当然異なることを考えると、この方程式の解の個数は 2^(解の自由度) であることがわかります。
全体として、xor sum の各ケースについて連立一次方程式の解を数え上げて足せば、求める答えになります。
公式の解説もあります。
最後に、グラフと線型代数の関係について簡単な話題を紹介します。
プログラミングコンテストにおいて、入力としてグラフが与えられることがとても一般的です。受け取ったプログラムの中でこれを保持する形式としては、次の2つがよく知られています。
コンテストにおいては、隣接頂点が取り出しやすく（したがって全探索がシンプルに書ける）、疎なグラフに対して空間計算量が有利な隣接リストを用いることが多いですが、今回は線型代数の話題なので隣接行列を扱います *3。
隣接行列は、グラフ G = (V, E) に対して定まる次のような行列です。
この行列に対して線形代数的な操作を施すことで、グラフに関する様々な情報を調べることができます。詳しくは、2年前の競技プログラミングアドベントカレンダーで fura2 さんの書かれた次の記事が参考になるでしょう。
今年の夏合宿4日目に出題された問題です。
問題はこちらです。F: Graph Automata Player - Japan Alumni Group Summer Camp 2013 Day 4 | AtCoder
有向グラフ（頂点数 300 以下）が与えられる。任意の時刻において、各頂点は 0, 1 いずれかの状態を持つ。時刻 t でのグラフの状態が与えられた時、時刻 t+1 での 頂点 v の状態は次のように決まる。
v から出ている辺で時刻 t での行き先の頂点の状態が 1 であるような辺が奇数個ならば 1、そうでなければ 0。
ある時刻での状態が与えられるので、T（1億以下）だけ前の状態を求めよ。条件を満たす状態が複数ありうる場合や状態が矛盾している場合は適切なエラーを出力すること。
グラフの接続行列を A、時刻 t での状態ベクトルをとすると、次の式が成立します。
これを用いて連立一次方程式を立てて解きます。これは解の個数も含めてすでに解説済みですね。
出題者による解説もあります。
この記事は競技プログラマのための記事であるにも関わらず、登場するアルゴリズムが掃き出し法だけです。そう、線形代数を背景とした問題の多くは掃き出し法のライブラリさえ持っていれば解けるんです。今年はもうあと1ヶ月しかありませんが、来年からのコンテストではぜひ線形代数や連立一次方程式を背景とした問題を解きまくってくださいね！
結果についていろいろ思うところはありますがひとまずお疲れ様でした。チーム戦楽しかったです。
どちらにせよ、あのセットだとやっぱり6問通したかったですね……。
今まで4回チームを組んでくれてありがとう、ぼくも多くのものを得られて楽しかったです。