数字の最大桁の値は一様分布に従うと思いきや、違うらしい。この法則によると、最大桁が1である確率は、30%を超える。50%の確率で、数字の最大桁の値は、1または2となるらしい。この問題では、この法則を用いて、金融機関のtransactionの監査を行う。金融機関で取引された金額リストを取得して、すべての数字の最大桁の値dをサンプリングする。Lawに従わない値dが存在すれば、それらの取引には何らかの不正があると考え厳重に監視する。プロコンの問題という観点では単純な実装ゲーだったが、この法則と問題の内容が面白かった。d=1,2,...,9を計算してstaticなテーブルに入れておくとよい。今回は、求める数値が9つなので起動時に計算しても問題ないが、求める個数が大きくなった場合はメタプログラミングの対象になるのかなと思った。何とか考えながら、いろいろ調べてたらこんな変態postを発見。なんだこれは(笑)面白そうじゃなイカ。ベクトルの物理的意味を考える今更感が拭えないが、固有値、固有ベクトルが物理的に意味するところを探ろうと思う。(間違っているところがありましたら、ご指摘ください。)ポイント1行列とは、線形写像の表現方法の一つである。以下のような線形写像を考える。この写像を行列を用いて表すと以下のように書くことができる。x2]に掛けると以下のようになる。この写像fを二次元平面上で考えてみる。fは、上図のように黒い点を青い点に写すような写像である。fには、x軸方向のベクトルを2倍にし、y軸方向の値を3倍にするという働きがある。ポイント2ベクトル空間の軸の取り方は複数個ある。二元平面を書くとき、当たり前のように私たちは水平な線(x軸)と垂直な線(y軸)を引く。0]、y軸をベクトルで表すと、[0;1]という風にかける。このようにそのベクトル空間の軸となるようなベクトルを基底とよぶ。基底を用いると、その空間のすべてのベクトルを基底の線形結合で表すことができる。実は、既定の取りは複数個存在する。1]を基底にとってみる。このとき、と2つのベクトルは基底[2;1]、[-1;1]の線形結合で表すことができる。同様に、任意の2次元ベクトルは、これらの基底の線形結合で表すことができる。一般に、n次元空間から、n個のベクトルを選んで、それらn個が互いに一次独立であれば、それらのベクトルはその空間の基底となる。1]を基底としてグラフを書けば、水平線と、垂直線を軸にとる。1]を基底に選ぶということは、以下のような軸のもとでグラフを書くということを意味している。以下の行列Aについて考える。この行列は、写像を表現したものだといえる。1]毎に適応すると、となる。ここで注目することは、上の結果がそれぞれAの列ベクトルと一致しているということである。基底に対する写像の結果によって行列の形が一意に決まるように見える。β[0;1]にfを適応すると、(※fは線形変換であることに注意)となるので、任意のベクトルに対する写像のふるまいは、基底に対するふるまいによって決定される。1]を基底とした場合の写像fについて考えてみる。先に述べたように、基底に対する写像のふるまいを見ればよい。上の式から分かるように、fはv1方向成分を9倍したものを新しいv1要素に、v1成分を9倍したものとv2成分を4倍したものを足したものを新しいv2成分に置き換えるような写像といえる。0]をv1、v2に変換するような行列Pを考える。(何の前触れもなくPが登場しましたが、面白いことがわかるのでちょっとだけ我慢してください。v2にAを適応したときに出て来ました。0]に戻すという操作に対応しています。(行列を右から左に見て行くことに注意。0]に対する振る舞いを見てみます。これは、v1、v2のもとでのfの振る舞いの式と同じ形(基底にかかる係数部分に注目!)をしています。Pという表現は、基底(座標軸)を取りなおした場合に、fはどういう形をしているか?を表したものになっています。Pに変換する処理を相似変換といいます。相似変換は座標の取り方を変えただけで、写像そのものは変わっていないことから、変換の前後で以下の値が不変のまま保たれます。固有値ポイント4固有ベクトルを基底にとって写像をみると、写像の本質が見える。行列Aの固有値、固有ベクトルはそれぞれです。1]のもとでみてみましょう。1]に変換する行列Pは、です。相似変換をすると、となります。9はAの固有値と一致しています。以上をふまえると、一般に以下のことがいえます。xnを基底とした座標系で表現すると、写像fは、x1要素をλ1(x1に対応する固有値)倍、x2要素をλ2倍、....するという簡単な写像に対応している。座標の見方を変えるだけで、線形変換の本質的な部分が見えるということですね。おまけこのブログを書いてる最中に固有値に関して面白い特性を知ったので今後のためにメモしておく。固有値の和は、トレースと一致する固有値の積は、行列式と一致するこの2つは、とても興味深いです。時間があるとき証明でも読んどこうかな。行列式を効率的に計算する方法を考える。n*n行列Aの行列式は、と定義される。ε()は、与えられた順列が奇順列の場合は-1、偶順列の場合は1となるような関数である。上の定義より、n*n行列の行列式をそのまま計算すると、O(n*n!)の計算量が必要となってしまう。大きなサイズ(n>20)の行列の行列式を簡単に計算するために、以下の性質を用いる。行列Aのi行から、j行の定数倍を引いても、行列式の値は変わらない。上記の性質を使って行列Aを上三角行列に変更する。行列式の定義を見ると、上三角行列の行列式は、対角成分の積と等しいことに気付く。三角行列への変換はO(n^3)、対角成分の積を求める処理はO(n)なので、全体でO(n^3)の計算量で行列式を求めることができる。ベクトルって何に使うの?ふと、固有値・固有ベクトルって何がそんなに嬉しいのか?何の役に立つのか?と思っていろいろ調べていた。(対角化してべき乗計算が速くできますだけだと、ちょっと勉強する動機づけとしては弱い。rankの論文に固有値・固有ベクトルが使われていたのを思い出したので、これをちょこっと紹介。(解釈に間違いなどありましたら、ご指摘ください。rankアルゴリズムについて。これは、いわずと知れたgoogleの検索処理において中心的な役割を果たす処理です。rankの基本的な考え方は、”たくさんリンクを張られているサイトほど重要なサイトである”ということです。リンクを張られているサイトが検索で上位に現れます。加えて、同じリンクを張られているでも、重要なページ/人気のあるページからリンクを張られているのか、重要でない/人気でないページからリンクを張られているのかを区別しています。(例えば、あなたのページがクラスメイトの太郎くんからリンクをはられているのと、yahooのカテゴリページからリンクされているのでは意味が違いますよね?)ここまで、まとめると、リンクをたくさん張られているサイトほど重要とみなす重要なサイトからのリンクほど、大きな重みを付けるとなります。あるサイトの重要度を上記の定義にしたがって、定式化してみます。(※本当は、リンク元のページから受け取る重要度をそのページのリンク総数で割るという処理がありますが、簡単のため省略しています。1,..,nはそれぞれウェブページiの重要度です。(ウェブページは全部でn個あるとしています。ウェブページiからあなたのページにリンクがあれば1、なければ0です。cは定数で、常に全体のウェブページの重要度の総和が一定となるように正規化しています。上の式から分かるように、あなたのページの重要度は、他のページの重要度がわかっていないと計算できません。逆に、他のページの重要度も、あなたのページの重要度の影響を受けています。いうことで、連立方程式をたてて、すべてのページに適切な重要度を割り当てます。連立方程式は、ベクトルx、グラフの隣接行列Aを用いて以下のように書くことができます。隣接行列は先に説明したのと同様のリンクの接続情報です。以下の方程式を解いてx(すべてのウェブページの重要度)を求めることが目標です。両辺を定数cで割って、左辺と右辺を入れ替えると見慣れた形が現れます。xは隣接行列Aの固有ベクトルになっています。実は、私たちが毎日お世話になっているGoogle検索に固有値/固有ベクトルが使われていたのですね。何のために固有値とか勉強するんだろ?と疑問に思っている高校生/大学生の人や、固有値・固有ベクトルの有効性を生徒さんに簡単に話したい先生方の参考になれば本望です。このページでは、実際のpagerankを簡素化して説明しました。実際の処理をもっときちんと知りたいという方は、ラリーページとセルゲイブリンがスタンフォード時代に書いた論文をご参照ください。行列関係用語まとめ行列関係の用語についてまとめ。対角成分のみが1、残りは0である行列。単位行列をスカラー倍したもの。対角成分意外が0である行列。行数と列数が等しい行列。行列Aとその随伴行列A*が等しいとき、Aをエルミート行列とよぶ。随伴行列(共役転置行列ともよばれる)とは、行列に転置をしたあと、各要素をその複素共役に置き換えたもの。例)例からも分かるように、エルミート行列の対角成分は、実数でないといけない。もとの行列のサイズと転置した行列のサイズが同じにならなければならないため、エルミート行列は正方行列である。自身と転置した行列が等しくなうような行列。例)例からも分かるように、実対称行列は、エルミート行列のsubsetである。逆行列と随伴行列が等しくなる行列。例)ユニタリ行列は、自身と随伴行列をかけると単位行列となる。このことから明らかに、ユニタリ行列であることと、列(行)ベクトルが正規直交基底であることは同値。逆行列と転置した行列が等しくなる行列。例)ユニタリ行列と同様に、直行行列であることと、列(行)ベクトルが正規直交基底であることは同値。直交行列は、ユニタリ行列のsubsetである。行列積ABが単位行列となるとき、BをAの逆行列いう。逆行列が存在する行列のこと。ベクトル空間全体をはることのできる単位ベクトルの集合。それぞれの基底は一次独立。直交基底、かつ、それぞれの基底の大きさが1であるもの。階数:行列を列ベクトルとみなしたときに、線形独立な列ベクトルの数。Aの階数は、rank(A)と書く。行列は、ベクトルに対する一次変換演算とみなすことができる。このとき、あるベクトルxには、その方向が変わらない一次変換というものが存在する。逆に行列側からみると、その変換に対して方向を変えないベクトルは固有に決まる。このベクトルを固有ベクトルという。方向を変えない変換は、単にベクトルをスカラー倍するだけの写像と考えることができる。この倍率に対応する値を固有値と呼ぶ。固有値/固有ベクトルを利用することで、行列のべき乗を高速に計算できる(行列の対角化)。問題概要R*Cの単位ブロックからなる長方形の鉄板がある。この鉄板から1辺がkの正方形を切り出す。4隅のブロックを切り落として、ブレードを作る。この鉄板は厚さが不均一なため、重心とブレードの中点が一致しないことがある。各ブロックの重さが与えられるので、重心とブレードの中点が一致するような最大のブレードのサイズを求める。正方形の左上のブロックを選ぶ。c)を超えない間、kをインクリメント。y+k)のブレードの重心および中点を計算する。一致すれば、答えに反映する。これで、smallは通る。全体の処理は、O(N^5)。largeを通すには、計算量を減らす必要がある。y+k-1)のブレードの重心情報を利用すれば、O(N)で出来る。これは良くやる動的計画。(y+y+k)/2)なので、O(1)。これで全体の計算量はO(N^4)に落ちる。きわどいが、これでも通る。Editorial解は、O(N^3)だった。ACrushとかrngさんとかもO(N^3)でやっていた。この方法は、非常に興味深い。処理の概要は以下のとおり。{0,1,...C-1}のブレードの重心を予め計算しておく。y-1)の情報を利用すれば、O(1)で出来る。0)の場合は、1.をそのまま使える。0),(x-1,y+k)と、(0,0),(x-1,y-1)の情報を使ってO(1)で求めることができる。よって2.の処理は、(x,y,k)のループのみとなり、O(N^3)コードに落とすときの工夫だが、2.の場合分け(x=0とかy=0とか)をごちゃごちゃしなくていいように、上行と左列にdummyのバッファを入れておくとよい。Jam2011年8月10日水曜日サルでも分かるFFT(4)前回「サルでも分かるFFT(3)」で、FFTのC++による実装を書きました。n)で動くのですが、まだまだ遅いです。出力用バッファは毎回newしているビット逆転で毎回Nビットなめている同じWを何回も計算しているこの辺の処理を工夫して、定数項を小さくします。一つ目と二つ目は、in-placeに変換を行うことで解決できます。入力のデータを直接いじって入力用バッファに結果を書き込みます。三つ目は、ループを一つ増やしてinnermostなloopの外で計算することで解決します。(余談ですが、exp()とかhypot()は相当重い処理です。)四つ目は、ビット逆転では、LSBとMSBが逆転しているということを利用すれば、効率的に書くことができます。sourceのを参考にしました。}}前回は、時間間引き(時間成分を偶数、奇数に分ける)のFFTを書きましたが、上のソースは周波数間引き(周波数成分を偶数、奇数に分ける)で書いています。どちらも同じように書けますが、バタフライ演算の向きが逆になります。ビット逆転のところが興味深いですが、ビット演算を使わない書くと処理の意味が分かります。LSBとMSBを逆に考えて1をインクリメントしています。}}さて、最終テーマであるFFTを用いた多倍長整数乗算の高速化です。普通に多倍長整数の乗算をやると、O(n^2)の時間が必要です(nは桁数)。100万桁同士の掛け算をすると、30分~1時間程度かかるのではないかと思います。n)で乗算ができます。100万桁同士の掛け算でも数秒で終わる計算量です。数学的な詳しい解説は、ここのサイトを参照。ここでは、大まかな処理だけをまとめます。「文字列xとyが与えられる。