グラフをトーラスとか射影平面に描画するアルゴリズムの話

入力として与えられたグラフをsphereとかtorusとか射影平面(N1)にembedできるかどうかを判定し、できるならば具体的に一つembeddingを出力せよという話。nは頂点数。基本的にかなり大雑把な話しかしないので雰囲気だけつかんでくれたらと思う。

K5とK_3,3が平面的グラフの禁止マイナー(obstructionと呼ぶらしい)であるというKuratowskiの定理はあまねく知れ渡っていることであるが、実はTorus上で考えるとこの二つのobstructionはどちらもembeddできることが分かる。ちなみに後で出てくるが、N1描画の時の禁止マイナーなグラフは全部で103種類存在する。

- sphere ... O(n)のアルゴリズムがある。実装されてる。

- N1

   - O(n) ... 複雑すぎて実装むりぽ。

   - O(n^2) ... MR Algorithmと呼ばれるものがある。O(n)を簡単にしたもの。実装済み。

- torus

   - O(n) ... あまりにも複雑。当然実装はされていない。

   - O(n^3) ... JM Algorithmと呼ばれているものがある。めちゃ複雑。実装したよ、ていう人が過去にいたけどそれダウト、って言う人もいる。

   - 2^O(n) ... NM Algorithm 及び Woodcock's Algorithmが有名。Woodcockの方が定数倍的な意味で早いが実装は十分複雑。どちらも実装はされてるぽい(?)

ここに出てきた固有名詞のついてるアルゴリズムはどれも "embedding extension"と呼ばれるアプローチを取っている。

"embedding extension"とは、入力されたグラフGのある部分グラフを"frame"と呼び、基本的には記号Kで表す。まずこれをtorusまたはN1上にframeをembedするところから始まる。

例えばframeとしてはK5やK_3,3と位相同型なグラフを採用することが多い(これらはtorusにもN1上にもembed可能)

このembeddingは定数通りしかないため、それらを全列挙し、各embeddingに対してグラフの残りの部分(K-bridgeと呼ばれる)のembeddingを試してみて、うまくいくものがみつかったらそれを返すというものである。

frameとして簡単なグラフ(例えばただの閉路とか)を採用すれば実装は楽になるが時間計算量は高くなり、複雑なグラフ(K5とか)を採用すれば場合分けがやばいけど時間計算量は落ちる。そこにtrade offの関係がある。

- N1にembedする場合(NM Algorithm)

　frameとしてK5もしくはK_3,3と位相同型なGの部分グラフを採用する。これらのN1上へのembeddingはそれぞれ27、6通りしかない。そして残りの部分を頑張る。

　一般に、曲面にグラフをembedした場合は幾つかの辺で囲まれた面ができる。具体的には、曲面からグラフの線分をハサミで切り取り除いたものを考え、そのそれぞれの連結部分のことを"face"と呼ぶ。

　まずframeを選びN1上にembedしたら幾つかのfaceができ、残りの部分(K-bridge)をどのfaceにembedすれば良いか、という問題が生じてくる。しかし、基本的にK-bridgeを埋め込むことができるようなfaceは高々3通りしかなく、しかも3通りのfaceがあるようなbridgeは定数個しかないことが知られている。そして残りのbridgeについては高々2通りしかなく、その割り当ては2-SATで解ける。そこでこの定数個の3通りの割り当てを全列挙し、それぞれの場合に対して2-SATのインスタンスを生成し、解けば良い。この2-SATはclauseがO(n^2)個あるので、全体としてこの2-SATはO(n^2)で解けるのでNM-AlgorithmはO(n^2)で出来てしまう。

- Torusにembedする場合(NM Algorithm , Woodcock Algorithm)

　NM Algorithmはframeとして閉路を採用する。 グラフの中にK5またはK_3,3と位相同型な部分グラフを見つけこれをKとする。さらにKの中から部分グラフK'をとる。(KがK5ならK'はK4, KがK_3,3ならK'はK_2,3)とする。 このK'には実は"ある良い性質"を持った閉路が必ず一つ以上存在することが分かっていて、その「良い性質を持った閉路」をframeとして採用する。直感的に言うとトーラスの筒のところを一周させるようにframeをembedする。もしグラフがTorus上embeddableならばこのようにして列挙した閉路で探索していくと必ずうまくいくものが見つかるということが保証されている。続きの話を直感的に説明すると、この閉路によってトーラスを切り、筒状の立体を得る。そして残りの部分をこの筒状のfaceに頑張ってembedする。

　しかしN1では各faceに対してその境界を見てみると同じ頂点が2回現れることがない。しかしTorusでは2回現れることがありうる。この違いによってbridgeをfaceに割り当てた後でもembedの仕方が何通りか存在してしまい、計算量が膨れてしまう。ここにN1とTorusの大きな違いがある。

　Woodcock AlgorithmはframeとしてK_5またはK_3,3と位相同型な部分グラフを採用する。embedの仕方とかも全通り列挙してあとはNM Algorithmと同じようなことをやる。

　JM法は理論的には多項式時間O(n^3)で解けるアルゴリズムである。これは、冒頭で言った103種類のobstructionと位相同型なグラフをframeとして採用するらしい。そしてembeddingを全通り試して上手いことやるとO(n^3)で解けるらしいが定数倍などもかなりヤバイらしい。

ちょっと詳細を省きすぎてしまった感があってアレなのでそのうちグラフのembeddingの基本的な事柄について丁寧な記事を書きたい。ところで平面性判定や平面embeddingがO(n)でできるという事実に驚いた。

Graph Golf参加記

　NII主催のグラフコンペティション Graph Golfに助教とM2の先輩と僕の3人チームで参加して優勝し、12/10に札幌で開かれたCANDAR'15にて講演をしました。(めっちゃ高そうな盾とかもらいました！！！)ということでGraph Golfの問題内容や背景、および僕らのとった手法の概略について適当に書いていきます。

前提知識として知っておいてほしい単語は以下の2つくらいです。

• グラフ(点と点が繋がってるアレのこと)
• 次数(頂点に繋がってる辺の本数のこと)

問題内容
　自然数nとdが与えられる。頂点数nでどの頂点の次数もd以下であるようなグラフのうち
1. 直径
2. ASPL
が小さいものを構成せよ。ただし直径が小さい方良く、直径が同じで会った場合はASPLで比較する。

Graph Golfのページを見ればわかるのですが実際には与えられるnとdは決まっていて、このようになっています。

グラフの直径(diameter)は最短経路長のうち最大のものです。

ASPL(Average Shortest Path Length)というのはその名の示す通り最短経路長の平均の値のことで、要するにワーシャルフロイド法などで求めた全点対の距離の平均の値のことを指します。

＊表の各セルのパーセントのところはASPLには理論的に下限があって、その下限に対して今得られているベストなグラフには何パーセントの誤差があるのか、というのを表しています。

問題背景
　この問題は元々はOrder/degree Problemとして有名な問題で、今まで特に有効な手法などは与えられていませんでした。もともとグラフの頂点数(order)、直径(diameter)、次数(degree)の間には関係があって、３つのうち二つを固定してもう一方を最適化するという研究はあって、中でも一番有名なのは直径と次数を固定して頂点数を最大にするDegree/diameter Problemというものです。これについてはCombinatorics Wikiが詳しいです。
　今回のOrder/degree Problemの実用上の応用としてはネットワークトポロジーの設計ひいてはスーパーコンピュータの設計にあります。いわばCPUがn個あってそれぞれはd個のケーブルでつなげることができるとした時に平均ホップ数をできるだけ小さくしたいという設計思想があるわけです。

基本手法
　ナイーブな手法について説明します。まず初期グラフ(n頂点d-regularなランダムグラフ)を生成します。d-regularというのは全ての頂点の次数が等しくdであるという意味です。
　ここで、今持っているグラフから辺を2本選び、それぞれをa-b, c-dとします。その辺を図のようにa-c, b-dとつなげ変える操作をswitchと呼びます。

今持っているグラフに対してswitch一回によって得られる新しいグラフを近傍(neighbor)と呼ぶことにします。この操作によってグラフのどの頂点も次数が変化しないことがわかるので、元のグラフが次数制限を満たしていればその近傍もまた次数制限を満たしていることは明らかです。
　次に今持っているグラフの評価関数(evaluation function) f(G)を定義します。ここではそのグラフのASPL値を評価関数として採用しましょう。
　そうすると、一つの素朴な反復アルゴリズムを与えることはできます。初期グラフからスタートして近傍を取り、評価してその評価値が何かしらの条件(例えば今持っているグラフの評価値より良いなど)を満たしていた時に解を更新していくというものです。
　このように近傍を探索して解を更新していくアルゴリズムの枠組みを局所探索(local search)と呼び、特に評価値が良くなったら即更新、というものを貪欲法(greedy)と呼びます。また、今回のswitchのように2本のエッジを付け替えるものを近傍として定義したgreedyのことを2-opt法と呼び、主に巡回セールスマン問題(TSP : Traveling Salesman Problem)に対する一つの手法として有名です。
　これ以上更新が行えなくなった時の解のことを局所最適解と呼びます。評価関数が凸だったら局所最適解が全体の最適解であることが保証されるのですが、今回はそういうわけではありません。したがって、初期解の場所によっては悪い局所最適解に行き着くこともありうる、という問題点をこの局所探索ははらんでいます。
　さらに、この局所探索は評価関数の呼び出しを非常に大きな回数行います。したがって評価関数の時間計算量が大きな障害になります。今はASPLを評価関数として用いているので時間計算量は各頂点からのBFSによってO(VE)=O(n^2 d)だけかかります。これでは到底現実的な時間では良い解を得ることはおろか局所最適解を得ることすら困難です。
　ということで、この2点をどう克服したかについて簡単に紹介しようと思います。

GPGPUによるASPLの評価
　特にトピックとしてあげるまでもないのですが、ASPLの評価をGPGPUを使って並列化しました。隣接行列のk乗の(i,j)成分はiからjへの長さkのパスの本数を意味しています。したがって隣接行列を2乗、3乗、・・・としていき初めて(i,j)成分が非ゼロになった時のkの値がi-j間の最短経路長になります。実際は累乗の計算はグラフの直径と同じ回数まで求めればよく、あとは行列積をCUDAで書けばOKです。しかも今回は隣接行列がsparse行列(非ゼロ成分の個数が少ない)なので、その点をうまく利用することができます。

ASPLの近似
　このトピックがこの記事のメインとなります。要するに長い時間をかけてASPLを計算するのではなくその近似値を高速に評価しよう、という話です。実はO(1)時間の評価関数を考えました。
　まず前提としてグラフの直径を3に限定します(それ以外の直径のグラフに関してはGPGPUで頑張りました)。Graph Golfでいうとn=10000, d=64といった大規模なグラフをターゲットにします。
　ここで発想のモチベーションがいくつかあるので書いておきます。

• 「switchというちょっとの変化をちょっとの時間で捉えよう」という思想。
• 評価関数自体を求めるのではなく、switchによる評価関数の差分を何かしらのテーブルを使って求めよう。
• 小さい閉路があると望ましくない。

三番目は、辺の本数が決まってる→無駄な辺をなくしたい→同じ頂点対に対して短いパスが多くなったら困る→小さい閉路をなくしたい
というところから来ています。ここでグラフの頂点vを適当に一つとってきてvからBFSでグラフを展開してみましょう。このような感じになります。

　一番上がv、その下の段にはvと隣接している頂点(当然d個)、さらにその下にはvからの距離が2の頂点(個数はグラフに依存。多いほどASPL的に良い)、最後にvからの距離が3の頂点が並んでいます。ここで、もしグラフ(直径は3)に三角形四角形が存在しないと仮定しましょう。すると、距離2の頂点の個数はd(d-1)となり最大になります。したがってASPLの下界を達成し最適なグラフとなります。また、vを含む三角形や四角形があると距離2の頂点数がその分減ってしまい、結果としてASPLに悪影響をおよぼしてしまいます。つまり、グラフの三角形の四角形を減らせば良い、ひいては三角形の個数と四角形の個数を評価関数に採用すれば良さそうじゃね？となってくるわけです。そこで三角形の個数を△、四角形の個数を口として、評価関数を以下のように定義しました :

f(G) = 3△+2口

　3と2がでてくる理由はこの図のように

• 三角形が一つあると(i-j),(j-k),(k-i)の3つのペア
• 四角形が一つあると(a-c),(b-d)の2つのペア

に影響を与えるからです。また、実は直径3のグラフのASPLというのは

　このような関係が成り立つことが証明できます。つまり上で定義したfを減少させるというのはASPLの上界を下げるということにつながります。

O(1)時間で評価

　ASPLはグラフに含まれる三角形と四角形の個数を使って近似でき、それを評価関数に採用すれば良いという話をしました。ここでは、switchによる三角形と四角形の個数の増減をO(1)で評価する方法について説明します。まず前処理として、以下の三つをテーブルとして持ちます。

• A[][] : 隣接行列
• A2[i][j] : iからjへの長さ3のパスの本数
• A3[i][j] : iからjへの長さ3のパスの本数(ただし同じ辺を二度以上通らないパス)

　こうすると、例えばグラフに辺i-jを追加した時に増える三角形の個数はA2[i][j]で取得でき、逆に辺i-jを削除した時に減る三角形の個数もまたA2[i][j]で取得できます。

　四角形の場合もそれぞれA3[i][j]で取得できます。

　　　　　　　

　目標はswitch後の△と口の増減です。そして今持っているのはswitch前のグラフについてのテーブルです。switchという操作はa-b , c-dの削除およびa-d, b-cの追加と捉えることができます。まず三角形についてですが、a-bとc-dを削除する時は大丈夫でしょう。しかしそのあとa-dとb-cを辺を追加する時にはテーブルではa-bは繋がったままの値しか取得できないので、A2[a][d]で増えると想定している三角形の中にはa-bを利用しているものもあります。実際はこれらの三角形は増えることはないので、その分、つまりa-b, a-dを利用する三角形の個数をカウントして引かなければいけません。実際これはA[b][d]と等しくなります。四角形について考えるとさらにややこしくなります。

　調整が必要なのでデバッグとかはかなり大変なのですが、このようにすれば個数の上限をO(1)で評価することが可能になります。

　最後にテーブルの書き換えについての話をします。解を更新するとグラフ自体も変化するためテーブルの値も動的に書き換えなければいけません。詳細は省きますがA2の書き換えはO(d)、A3の書き換えはO(d^2)でできます。

焼きなまし法

　ここまででO(1)で評価できる近似について述べました。これを使うとn=10000 d=64のグラフでも、いろいろなテクニック(多くの三角形四角形に含まれてる順で近傍を探していく)を使えば、3時間ちょっとで局所最適解にたどり着きます。しかしやはりより良い解を得るためにgreedyではなく焼きなまし法を使うことができます。実際Graph Golfの問題に置いては焼きなまし法はかなり有効で、greedyで得られる局所最適解と比べてかなり良いグラフを得ることができると経験的にわかっています。実際私たちも一位をとったほとんどのグラフは焼きなまし法で得ることができました。

まとめ

• 三角形と四角形の個数でASPLを近似できる
• この事実を使うとO(1)の評価関数を設計できる
• 焼きなまし法は強い
• 北海道は寒い

発展

　実は、直径が3のグラフのASPLの近似はさらに良いものがあります。というか結構簡潔で美しい等式が証明できます。(それは三角形四角形の個数以外にも幾つかの図形の個数を用いるのでO(1)で評価できるとは限りませんが...)

　この辺の細かいことは論文に書こうと思っています。

東大受験記

2015年の夏に
東京大学大学院情報理工学系研究科数理情報学専攻
を受験したので書いてみようかなと思いました。2015年1月から振り返ります。

1月 : 親に東大行ってみたいと伝える。
2月：春休み突入。なんか友人の一人が線形代数勉強してるとか言っててこわ・・・と思いながら自分も線形代数の復習を始める(斎藤正彦の本)
3月：おもむろにTOEFLを調べた結果、どうやらパスポートが必要だということに気づく。そしておもむろに自分のパスポートの期限が切れていたことに気づく。
4月：新学期に入り線形代数の勉強に飽きる。パスポートを作る。初めて都庁に行った。議員になりたいと思った。パスポートを作って満足し、TOEFLの申し込みをどんどん先延ばしにする。
5月：いつまでにTOEFL受ければいいのかを考え始める。調べた結果かなりヤバイということに気づく。慌てて申し込む。
6月：Graph Golfというコンペティションが始まり、熱中する。TOEFLを受けてあまりの難しさに抱腹絶倒する。Graph Golfに熱中する。
7月：過去問に取り掛かる。おもむろに絶望する。現実逃避にGraph Golfを頑張る。TOEFLのスコアレポートが東大に届いていないことが判明。おもむろに絶望する。
8月：なんとかTOEFLが間に合う。過去問に取り掛かるものの半分も解けないことに気づく。現実逃避にGraph Golfを頑張る。

試験1日目(共通数学)：
　完全に諦めてもう試験をばっくれてしまおうと思ったもののさすがに良心が痛むので記念受験しに行く。とりあえず休憩時間は「夜は短し歩けよ乙女」を読む。問題を読んでおもむろに解く。

試験2日目(専門数学)：
　1日目で思ったより答案が埋められたので受験会場に行くことを決意。「夜は短し歩けよ乙女」を読む。問題を読む。すると競プロとかでよく眼にするデータ構造に関する問題が出題されているのを見て勝利の予感を感じる。おもむろに手を動かして気づいたら他の問題の答えが出来上がっていたことに気づく。
　試験終了間際になって色々ミスをしていたことに気づくものの、当初の想定よりもかなり出来が良かったので嬉しく思った。しかし受かるとは思えなかった。

口頭試問：
　どうせ落ちると思っていたので「夜は短し歩けよ乙女」を携えながら普通の私服で会場に向かう。すると周りの人がみんなスーツでビビる。

合格発表：
　なんかTwitterみたらTLで合格番号の紙の画像が貼られていたのを見つける。なぜか自分の番号が載っているのを確認。一応自分の目で確認する。最後に自分の指導教員が自分の第一志望の先生であることを確認して喜ぶ。

教訓：
・割とかなり早い段階から準備していたがTOEFLの申し込みが非常に遅れてしまったことが非常に悔やまれる。
・そもそもTOEFLの対策を全くしなかったというのは論外だと思う。
・過去問が解けないからと言って無意味に絶望してもしょうがない。
・ダメ元でも受験会場には行ってみるべき。
・東工大よりも喜ぶ親戚は多い。

やっていてプラスになったなと思ったこと：
・線形代数(斎藤正彦)
・東工大の院試の過去問(割とかなりやってて、東工大を解けるようになるために色々勉強しようと思って色々勉強したら色々知識が増えた)
・「エレガントな問題解決」(オライリーの本)

Tseitin transformationとは

計算複雑性理論については疎く、最近ようやく本腰を入れて勉強し始めたのですがTseitin transformationというものがとても面白かったので紹介します。こういう考え方は苦手すぎて理解にすごく時間がかかってしまう...

僕が勉強したときはwikipedia(en)とこの記事を参考にさせていただきました。

ここでは

変数 : xのこと.今回はa,b,cとかx,y,zとかで表す。

リテラル : x、!xのこと

Boolean function :ここでは and, or , →, notで構成された式のこと.変数に0か1を代入すれば0か1が返ってくるとする。φで表す。

DNF : リテラルをandでつなげたものをorでつなげてできたBoolean functionのこと
CNF : リテラルをorでつなげたものをandでつなげてできたBoolean functionのこと

clause : リテラルをorでつなげたもの。CNFはclauseをandでつなげてできたものと言い換えることができる。

Boolean functionのサイズ : 文字列としたときの長さ

二つのBoolean functionが等価 : 任意の割り当てに対して同じ値が返ってくること。

充足可能性問題(SAT) : 与えられたBoolean functionが1を出力するような割り当てがあるかどうかを判定する問題。NP-completeである。

とします。サイズの定義に関しては変数の個数とかそういうのもありますけどどれも結局linearの関係にあってオーダー的には成り立つので今回は文字列長としておきます。

任意のBoolean functionを等価なDNFもしくはCNFに変換しようとすると、変換後のCNFは元のサイズの指数長になりえます。しかし例えば充足可能性を問題にしている場合には
φが充足可能 ⇔ φ' が充足可能
となるような変換であれば良いわけで、等価である必要はありません。今回紹介するTseitin transformationというのを使うと「充足可能性を保存して、かつ元のBoolean functionの線形オーダーのサイズであるようなφ'」を得ることができます。おそらく例を見るのが一番わかりやすいと思います。

例 :

充足可能性を保存するような変換をすると

こんな感じになります。p⇔qというのは要するにpとqが等しい値をとれば1を返すような論理関数です。(xorの否定)

イメージ的には連立方程式みたいなものだと思っています。

最後にそれぞれの()の中身を等価なclauseに変換してやればオッケーです。この作業は分配法則とか使ってうにゃうにゃやればできるはずです。こうして得られたものは確かにCNFになっているし、サイズも指数的に増えていません。変数が増えているために等価にはなっていないのですが、a,b,c,dがφを充足するときはそれぞれのv,w,x,y,zを()の中と等しい値にしてやればφ'は従属されるし、逆にφ'を従属するような割り当てa,b,c,dはφを充足します。つまり充足可能性を保存しているわけです。

分かってから見れば当たり前なのですが新しい変数をおくという発想は面白いと思いました。

CodeForces #306 Div2 D : D. Regular Bridge

問題：
橋を持つk-正則グラフを作れ。ただし作れないときはNOと答えよ。

解法：
明らかにk=2のときはグラフはCycleとなるのでNO.
一般に、kが偶数であるときはNOとなる。
(証明)
kが偶数のときにk-正則グラフに橋が存在すると仮定する。
すると、その橋を取り除くことによって二つのグラフに分解することが出来る。
しかし、それぞれのグラフについて、次数の和は奇数となってしまうので矛盾。

以上よりkが偶数の時はNOと答えれば良い。ではkが奇数の時はどのようにして構成出来るか？

kが奇数の時は
完全二部グラフK(k-1,k-1)を構成し、それぞれの頂点集合をA,Bとする。
Aの各頂点マッチングを結ぶ(k-1は偶数なので存在する)
頂点vを新たに一つ用意し、vとBの各頂点を結ぶ。
このように構成したグラフの次数について見ていくと、vの次数はk-1で、そのほかの次数はkとなる。
よってこのグラフを二つ用意しそれぞれのv同士を結べばその辺が橋になり、しかもグラフはk-正則となる。

ソースコード:
https://gist.github.com/knewknowl/4c17af4dde6f43e9bdc7

Codeforces Round 311 D Vitaly and Cycle

問題

http://codeforces.com/contest/557/problem/D
多重辺や自己ループを含まないグラフが与えられる。またこのグラフでは辺の重みは全て1として考える。
この辺にいくつか辺を追加して長さ奇数の閉路(ただし自己ループではない)を一つ以上含むグラフにしたい。ただし元々辺があるノード間に新たに辺を追加するのはできない。

最小何本の追加で達成できるか。またその最小本数の追加は何通りあるか。

解法

入力で与えられるグラフの頂点数をn,エッジ数をmとする。
追加する最小本数tは0,1,2,3のどれかである。
グラフの最大次数が0の時、辺は1本もないのでt=3で、追加の仕方は全部の頂点から3個選んだ通りになるのでnC3となる。
グラフの最大次数が1の時、長さ3の閉路を作ればよく、この時t=2である。この時は辺とその辺に含まれない頂点の中から1個選べば良いのでm*(n-2)である。
それ以外の時、BFSまたはDFSによってグラフに奇数の閉路がないか調べる。あった場合はt=0で追加の仕方は1通り。奇数の閉路があった場合、頂点を2色で塗り分けて同じ色どうしの頂点をエッジで結べば長さ奇数の閉路ができるので n1 chose 2 + n2 choose 2で計算できる。ただしn1,n2はそれぞれ色1,2で塗られた頂点の個数。

Codeforces Round 311 C : Arthur and Table

問題
http://codeforces.com/contest/557/problem/C
n本の脚がついたテーブルがある。各脚の長さがL[i]で与えられる。このテーブルの脚を何本か切り落としてテーブルをStableな状態にしたい。テーブルがStableであるとは
・一番長い 脚の本数が残っている脚の中で過半数を占めている
ということを指す。また、脚が1本だけのテーブルはStableであるとする。
テーブルの各脚を切り落とすにはコストが必要でそれぞれのコストがd[i]で与えられる。
Stableにするための最小コストを求めよ。
制約としてn<=10^5, L[i]<=10^5, 1<=d[i]<=200

解法
脚の長さでソートしたあと、最長の脚をL[i]にした時の最小コストというのを各iについて求めれば良い。
最長の脚をL[i]にした時の最小コストというのは、
1. L[i]より長い脚を全て切る
2. L[i]より短い脚を、L[i]の脚が過半数になるようにコストが小さい順に切っていく
ことによって得られる。
1はコストの累積和をあらかじめ計算しておけば簡単に求められる。
2は今脚L[i]をみている時に、それまでみていた脚の中でコストjの脚が何本あるかというヒストグラムを保持しておけば高速に求められる(d[i]が200以下であるため)

CF Round 309 C Kyoya and Colored Balls

問題:

http://codeforces.com/contest/554/problem/C
k色ボールが全部でn個ある。
各色のボールはa[i]個ある(つまりn=Σa[i])
このボールを以下の条件を満たすように横に並べる時、その並べ方は何通りあるか。ただし同じ色のボールは区別しない。

条件: 全ての色i=1,2,...,k-1に対して、並べた色iのボールの中で一番左側にあるものをp[i]と表すと、p[i]はp[i+1]の右側にある。

入力はkと各a[i]で、制限はn<=1000, k<=1000である。

解法:

例えばk=2の場合を考えてみます。
一番左にくるのは必ず色kでなければならず、その時残りのボールの並べ方について考えてみます。
まず最初に色1のボールa[1]個を横一列に並べると、一番左に置いたもの以外の色2のボールa[2]-1個は色1のボールに割り込む形で入れていくことが可能です。
例えばa[1]=○5,a[2]=3の場合だと、まず最初に
1 1 1 1 1 2
と並べたあと残りのa[2]-1=2個のボールは
○ 1 ○ 1 ○ 1 ○ 1 ○ 1 ○ 2
この6個ある○の中のどこかに2個入れるということになります。これは重複組み合わせになっているのでconbinationを使って求めることができます。
3色以上の場合も同様で、まず最初に色1を並べる。そのあとに一番左に置いたあとに色2を並べる。その次に一番左に色3を置いたあとに置けるところに色3のボールを置いていく...というのを繰り返すことで求めることが出来ます。

Code Festival : B - 枕決め

問題:

http://code-festival-2014-morning-middle.contest.atcoder.jp/tasks/code_festival_morning_easy_d
m人の人がいる。それぞれの人は好みの枕の高さの範囲[xi,yi]が与えられる。
n個の枕がある。それぞれの枕の高さはh[i]で、これも与えられる。
枕は一人一つ使うものとして、最大で何人の人が枕を使うことが出来るか、人数を求めよ。

解法:

貪欲法で解ける。
まずは点と区間でソートする。
priority_queueを用意する(突っ込むものは区間で、ソート基準は右側の座標の小さい順)

点x[i]について、
1.その点を含むような区間をすべてpriority_queueに入れる。
2.priority_queueから区間を取り出し、もしそれがx[i]を含むものであったらx[i]はその区間とマッチング。そうでないならばpriority_queueから点を取り出し続ける。
3.マッチングの個数を出力

CF Round310 Div1 C : Case of Chocolate

問題

http://codeforces.com/problemset/problem/555/C
n×nのグリッド上にチョコレートがある。
直線:x+y=n+1上の点からスタートして上または左に食べ進んでいく。
すでに訪問済みの座標にくるまで直進していく。
座標と方向のクエリが与えられるので、各クエリごとに何個のチョコレートを食べることができるかを求める問題。

解法

(sx,sy)から上に進む場合を考える。
この時、今までのクエリの開始地点のx座標の中でsxより大きいものの中で最小の座標mxを求める。そのクエリq'が
・上方向のクエリだったら、xからmxの間にあるチョコレートに対するクエリは存在しないので、q'が進めた分 + mxとxとの距離 が食べられるチョコレートの数となる。
・左方向のクエリだったら、そのクエリの開始座標のy座標まで進める。
つまりq'を二分探索で求めれば良い。

AOJ埋め

簡単な問題をたくさん解いた。

2021 : 姫血液の問題。memo[ノード][冷凍残り時間]でdjikstra
1145 : ゲノム文字列の問題。構文解析. 長さがインデックスになるまで解凍する感じ。
1138 : 馬車チケットの問題。memo[ノード][持ってるチケット]でdijkstra
1140 : 掃除ロボットの問題。bfsで各汚れ間の距離を出して10!通り試す。
1136 : 折れ線を探す問題。回転したやつとかを全部探索するだけ。回転は虚数掛けると楽
1127 : 宇宙ステーションの問題。最小全域木やるだけ。
2399 : プライバシーを守る問題。やるだけ。
2019 : 姫が護衛を雇う問題。貪欲法。
1165 : 角角画伯の問題。やるだけ。
2151 : 姫が護衛を雇う問題。memo[ノード][残り予算]でdjikstra
2402 : 星間ダイクストラの問題。五角形にして星同士の距離やってdijkstra
2182 : Eleven Loverの問題。なめるだけ。
1189 : 素数洞窟の問題。メモ化探索。
1187 : ICPCのランキング付けの問題。プレディケート書いてソートするだけ。
2014 : WとBの柵の問題。やるだけ。
1335 : 漸化式立ててメモ化。漸化式考えるの楽しかった。
2007 : お釣りを渡す店員が親切な問題。持ってる金全部渡してみるというのがわかれば楽
2012 : 宇宙ヤシガニの問題。探索の順番。
1142 : 列車の文字列の問題。やるだけ。
1125 : できるだけ沢山木をとる問題。英語読むだけ。
1137 : ローマ数字の足し算の問題。YARUDAKE.

こんな問題がDとかに来てていいのかよ、って感じの問題が散見された。

AOJ 2182 : Eleven Lover

問題:

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2182

解法:

11の倍数は
偶数桁目の和 - 奇数桁目の和 ≡ 0 (mod 11)
で判定できる。
そこで、F[i][j] = 0からk桁目まで「先頭から足し引きを交互にして11を法としてjになる」ようなkの個数(k<=i)
とすれば良い。
ただし0-leadingは許さないので、string[i+1]='0'ならばF[i][j] = 0にする。

ソースコード:

https://gist.github.com/knewknowl/a31bbb3cc1a625a0989a

ARC 39 C:幼稚園児高橋君

問題

http://arc039.contest.atcoder.jp/tasks/arc039_c

解法

C[座標][i]=方向iに訪問済みマスが何個連続してるか
を持たせながら移動しつつ更新した。

C[移動 前][i番目のコマンドの向き]=歩いた距離
C[移動後][i番目のコマンドの逆の向き]=歩いた距離
C[移動後][向きj] = C[移動後+j][j]+1
みたいな感じで更新した。

AOJ 1164 : 締まっていこう

問題:

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1164

簡単にいうと板に釘がいくつか打ち付けられていて、あとヒモが通っているのでヒモをピンッってした時のヒモの長さを答える問題。

解法:

引っかかっている釘、その直前に引っかかった釘、どれだけ巻き付いているか(角度)をスタックに入れる。角度は符号つき角度[-π, π]で考える。

ヒモABがACに連続的に移動する時を考える。

ABからACに移動する時に次に引っかかる釘をKとする。(もしそのような釘がなければK=Cとする)

この時, ∠BAKとスタックの先頭の角度を比較し

・それらが異符号ならばスタックの先頭は外れるので、

B ← pre(A)(Aの直前の釘)とAを結んだ直線と直線BCとの交点

A ← pre(A)

としてスタックをpopする。

・それらが同符号ならばスタックの先頭は外れないので、三角形ABC内の釘を凸法みたいな感じで選んでいき、スタックに入れていく。

解けた時は最高に「ハイッ」てやつだった。

https://gist.github.com/knewknowl/88bec89ce563a6755719

ARC 39 B: 高橋幼稚園

問題

http://arc039.contest.atcoder.jp/tasks/arc039_b

解法

n<=kならなるべく均等に配れば良いので、n人にまずk/n個ずつ配ってその後残ったk%n個のアメをn人に配れば良いのでnC(k%n)通り

n>kならばどんなに頑張っても幸福度は0なのでどう配っても良い。この場合は
k個のアメにn-1個の「仕切り」を考えてそれの並べ方を考えれば良い。(仕切りiと仕切りi+1の間のアメの個数が子供iがもらうアメの個数となる)
ので、(k+n-1)!/k!/(n-1)! = (k+n-1)Ck 通りとなる。

ソースコード

https://gist.github.com/knewknowl/f275cbbf7cf65aa3b3ab

AOJ 2586 : 流れ星に願いを

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2586
空間上にn個の球がある。
それぞれの球は速度(vx,vy,vz)で移動し1秒でvrだけ半径が減少し、
二つの球が接触もしくは半径<=0になったらその球は消滅する。

それぞれの球が消滅するまでの時間を求めよ。

解法

まず二つの球が接触するかどうかを判定するために球iと球jのt秒後の距離をf(t)とおくと
f(t)は下に凸な関数になっているので三分探索を使って極小値を求める。この極小値が0以下ならば二つの球は接触するので、極小値を与えるtと0との間で二分探索をすれば良い。

こうすれば接触時間と消滅時間がわかるので、それらの時間をソートして最初に起こるイベントから順に処理していけば良い。

・・・よく考えたら接触時間は二次方程式になるので三分探索する必要はなかった。

ソースコード

https://gist.github.com/knewknowl/9913126a26b210230e4d

AOJ 2584 : Broken Cipher Generator

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2584

解法

?がついてるところはAにすれば良い。あとは愚直に構文解析するだけ。
構文解析のやり方は
https://gist.github.com/draftcode/1357281
がすごくわかりやすくて良いと思います。

ソースコード

https://gist.github.com/knewknowl/98ba3331fc465b42416c#file-brokenciphergenerator-cpp

SRM 658 Div1 Med : Mutalisk

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13761
n個の箱があってそれぞれの箱にx[i]個の玉が入っている。
１ステップで3つの箱を選択し、
最初に選択した箱から9個以下
２番目に選択した箱から3個以下
最後に選択した箱から1個以下
の玉を取り出すことが出来る。( 例えば玉が6個しかなくても最初に選択して6個取り除いても良い)
全ての箱から玉を取り出すには最小で何ステップ必要かを求める問題。

解法(Div1)

(heekyuさんのコードを参考にしました。とてもシンプルで分かりやすいコードです)
二分探索+DP.
r回で全部なくすことが出来るかどうかをDPで判定する。
dp[f][i][j][k] = x[0]~x[f]までを1をi回,3をj回,9をk回使って全て0以下にすることが出来るかどうか
とすると、
仮に9をa個、3をb個使うとするとx[f]を0にするためには1は x[f] - 9*a - 3*b 個必要になる。この値をneedOneとしてdp[f+1][i-needOne][j-b][k-a]を調べれば良い。
このとき{60}みたいな入力に対しては1と3と9を同時に使おうとして実際の答えは60/9+1 = 7なのに60/(1+3+9)+1 = 5ってなっちゃうのでそこを注意する。
具体的には a+b+needOne <= rかどうかで判定すれば良い
たとえば{60}の例だと
1が5個、3が5個、9が5個で合計15個 > 5=r →はじかれる
1が0個、3が0個、9が7個で合計7個 <= 7=r   →はじかれない

解法(Div2 Med)

Div2Medだとn=3と固定されているので,
dp[i][j][k] = x[0]にi個、x[1]にj個、x[2]にk個入っているときの最小ステップ数
とすれば、1,3,9は3!=6通りの並べ方があるのでそれぞれに対してdp[i-1][j-3][k-9]+1みたいなことをすれば良い。

SRM 658 Div2Hard : OddEvenTreeHard

問題

http://lealgorithm.blogspot.jp/2015/05/srm-658-div1-easy-oddeventree.html
と同じだけど、x[i][j]='?'というのが許されている。(?だとOddとEvenどちらでも良い)

解法

Div1の方とほぼ同じ。
まず対称性の確認とかx[i][i]=='O'だったらはじくとかやって、ワーシャルフロイドでx[i][j]+x[j][k]の偶奇とx[i][k]の偶奇の確認(もしx[i][k]が?だったら埋める)というのをやり、
それでもどこかに?があった場合はまずそれをOにしてみて矛盾する箇所がないか確認して、もし矛盾したらEにする、というのを行うとxから?がなくなるので後はDiv1と同じ構成方法を用いて構成する。

ソースコード

https://gist.github.com/knewknowl/2b26f73992fb90439370

SRM 658 Div1 Easy : OddEvenTree

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13759&rd=16461

偶奇が二次配列で与えられるのでa[i][j]の偶奇とノードiからノードjへの距離の偶奇が一致すうりょうに木を構成する問題。条件を満たす木が存在しなければ存在しないと答える。

解法

まず対称行列になっているか、a[i][j]+a[j][k]の偶奇とa[i][k]の偶奇が一致するかを確かめる(木なのでdist[i][j]+dist[j][k]=dist[i][k]である)

次に,ノードiからノードjへの距離が奇数でありかつiとjが連結でないならば、iからjに枝を張って良い。そしてこの操作を繰り返して木になるならば、それが答えになる。
例えばノード0からスタートして、a[0][i]=Oddとなるようなiに対して0-iで全て枝を張り、張ったiに対してa[i][j]=Oddとなるようなjに対して枝を張り、...ということを繰り返せば良い。

HackerRank : clique

問題

ノード数がNでエッジ数がMのグラフの中で最大クリークの最初サイズを求める問題。

https://www.hackerrank.com/challenges/clique

解法

Turán's theoremというのを使えば、ノード数Nでクリークサイズr+1となるようなグラフのエッジ数の最大値は

で求められるので二分探索。

このようなグラフをTuránグラフと言うらしい。完全r部グラフの形をしている。

VK Cup 2015 - Round 3 : C. Idempotent functions

Problem:

http://codeforces.com/problemset/problem/542/C

Algorithm:

Given some x and do below for many times:
 x <- f(x)
Observe the transition of x and find out that there is loop.(the shape is like "ρ")
For example, suppose n=6 and f is
f : i -> i+1 (i=1,2,3,4,5)
   6 -> 3
and when x=1, then
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> ...
and the loop is 3->4->5->6 -> ...
also, if we start with x=5, then
5 -> 6 -> 3 -> 4 -> ...

when x is in the loop, then x moves only in the loop. So, let k is the length of loop(in this example, k=4) and m is some multiples of k, f^m(x) moves x to x(if x is in the loop).
For x that is not in the loop will go to loop for big k. Let s is minimum number of step that is needed to go to loop for all x.(in this example, 2 steps needed to go loop and s=2), then f^(m+s)(x) moves all points to loop. and this is Idempotent.

And we must be carefull that there is some "ρ".
So, we need s to be the longest "stick" and m to be the LCM of length of loops.

Hacker Rank : Even Tree

問題

https://www.hackerrank.com/challenges/even-tree
木が与えられるので、エッジを取り除いてノード数が偶数であるような木幾つかに分解したいので最も多くエッジを取り除くためにはどうすれば良いかを求める問題。

解法

各エッジに対して「このエッジを取り除いて二つに木を分割した時に双方の木に含まれるノード数がどちらも偶数である」ならば、そのエッジを取り除く。そうでなければ取り除かない
とすれば良い。ノード数が800なので十分間に合う。

AOJ 1196 : 橋の撤去

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1196
簡単に言えば木が与えられてどっかのノードからスタートして全ての辺を取り壊していく話。

解法

どの辺を何回通るか、というのを考えると、葉とつながってる辺は1回、普通の辺は行きと帰りと撤去で３回、スタート地点とゴール地点によっては行きと撤去の２回、の３通りがある。
２回の辺をできるだけ多くしたいけどこれの最大値=木の直径*2
になっている。
木の直径は簡単に求められる。

GCJ 1B: A. Counter Culture

問題

自然数xに対して
・1増やす
・10進表示を逆順にする
という操作を任意に行うことが出来る。
1からスタートして入力nまでたどり着くまでに最小で何ステップ必要か。

解法

nが1桁だったらそのままnを出力すれば良い。
逆順にしても桁数が減るわけではないので一桁ずつ減らして行くことを目標に考える。
つまり入力nがm桁だとすると、n を 10^(m-1) -1 に持って行くまでに最小で何ステップ必要かを考える。そのためにはデクリメントを出来るだけ少ない回数適用すれば良いが、色々考えてみるとnの10 進表示を2等分して、後ろの方を00…01の形にした後にreverseして前者を00…1にすれば最終的にnは100…001の形になって2回デクリメントすて1桁減らすことが出来る。
つまり、nを二等分して前半をreverseして得られる数字、後半の数字をそれぞれ求めてそれらを00…01にするまでに必要なステップ数(求めた数字-1) + 1(reverseの分) + 2(99..99にするのに必要な分)
を求めた後に99…99をまた再帰的に求めれば良い。
しかしnが例えばn=100321とかだとreverseの分を足す必要はないので注意。

(こんな感じ)

Hacker Rank : Wet Shark and Two Subsequences

問題

https://www.hackerrank.com/challenges/wet-shark-and-two-subsequences
n項の数列{x_i}とrとsが与えられるので、
以下の条件を満たす数列の部分集合A,Bがいくつ存在するかを求める問題
・|A|=|B|
・sum(A)+sum(B)=r
・sum(A)-sum(B)=s

解法

sum(A)=(r+s)/2

sum(B)=(r-s)/2

となるのでdp[i][j][k]=i番目までの和がjとなるようなサイズkの部分列の個数

してdp.

AOJ 1195:暗号化システム

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1195&lang=jp

解法

インクリメントするのは2^n通りくらいあるから全試しすれば良い。

AOJ 1194:バンパイア

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1194&lang=jp

解法

二分探索。

ビルのx座標が整数値でしかも絶対値が20以下なので

H[i] = 区間[i,i+1]のビルの最大値

とおいてt秒あとの区間[a,a+1]の太陽の高さを求めてかぶってるかどうかを判定すれば良い。

SRM Div2Med ProblemSetsEasy

div1easyと同じだった(div2の方が制約が簡単)

問題

easy用に使える問題がE個

easyもしくはmed用に使える問題がEM個

med用に使える問題がM個

medもしくはhard用に使える問題がMH個

hard用に使える問題がH個

ある。

これらからeasy問題、med問題、hard問題の問題セットをいくつ作ることができるか

解法

二分探索。なぜか落ちてて悲しかった。

TCO 15 1B Med The Tips

問題

n個の宝を探す宝探しゲームをする。
ノーヒントで宝iを探せる確率はp[i]
G[i][j]=Yならばi番目の宝が見つかればi番目の宝にj番目の宝の場所も記されているのでj番目の宝も見つけられる。

見つけられる宝の個数の期待値を求める問題。

解法

i番目の宝が見つかる確率をp[i]とおく。

G'[i][j]を「iからjまで連結しているならば1」として隣接行列を作る。

この時p[i]は「1- (iに到達できるnodeがどれも見つからない)」なので余事象で簡単に計算できる。

yukicoder No168. ものさし

問題

http://yukicoder.me/problems/296
頂点1から頂点nまでの任意のパスに含まれる全ての辺の中での最小の長さを10単位で切り上げする問題。

解法

ダイクストラっぽくやりました。
精度が怖いのでlong longで距離をとって平方根は二分探索でとりました

CF 534D. Handshakes

問題

http://codeforces.com/problemset/problem/534/D
n人の人がいて、適当な順番で部屋に入る。部屋に3人以上いたら、適当な3人組は部屋の外に出て行ってよい(出て行ったら二度と部屋に来ない)(出て行かなくても良い)
どの人も、部屋にx人いたらx人全員と握手をする。
さて、それぞれの人が「何人と握手したいか」という希望を入力として与えられるとき、全員の希望を満たすような部屋の入り方の順番はあるかどうか。あったらその順番を出力せよ。

解法

「希望人数が多い人」から握手させていけば良い。

CF 534C. Polycarpus' Dice

問題

http://codeforces.com/problemset/problem/534/C
n個のサイコロがあってサイコロiの目は1〜diのいずれかが出る。
このn個のサイコロをふって出た目の総和がAだとする。
このとき、各iに対して「サイコロiの出た目の数としてあり得ない目の数」の種類数を求める問題。
例えば、普通の6面のサイコロを2個ふってその目の和が8だったら、どちらのサイコロも1の目が出ることはあり得ないため、答えは{1,1}となる。

解法

各サイコロiに対してその目の出うる目の数の下限と上限を考える。
「サイコロiがxを出して他のサイコロが全部本気出してもAには届かないよなぁ」
というxのうち最大のもの+1が下限で、これをx1
「サイコロiが本気出してyの目が出たとき他のサイコロが全部1の目になってもAより大きいなぁ」
というyのうち最小のもの-1が上限(の候補の一つ)で、これをy1
とおくと、
サイコロiのでうる目の値は
[max(1,x1) , min(y1,di)]
となる。あとはdiからこの区間内の整数の個数を引けば良い。

ただしn=1の時はA=出たサイコロの目のはずなので、di-1を出力すれば良い。

GCJ Qualification Round 2015 Problem C. Dijkstra

問題

i,j,kのみで構成されたL文字の文字列sをX個連結した文字列を適当に3つに分割して、
「分割した部分文字列の各要素を四元数として見て積をとると順にi,j,kとすることが出来るかどうか」
を判定する問題。
例えば、
L=2,X=6,s="ji"のとき、連結して出来た文字列は
jijijijijiji
であるが、これを
jij | iji | jijiji
と分割することによってそれぞれの積をとるとi,j,kになるので答えはYESとなる。

制限

テストケース数<=100

L<=10000
L*X<=10000(small)
L*X<=10^16(large) , X<=10^12(large)

解法(small)

以下の性質を利用する。
・a,b,cが四元数のとき(a*b)*c=a*(b*c) (四元数の結合則)
連結して出来た文字列をtとしたとき、
t = ○ | △ | □
と分割してそれぞれの積が順にi,j,kとなっているならば
○*△=(○の積)*(△の積)=i*j=k
○*△*□ = (○*△)*(□の積) = k*k = -1
となるはず.
よって、連結して出来た文字列を順に掛けて行って途中でi,kが出てかつ全部掛けたら-1になっていれば良いのでO(L*X)で出来る。

解法(large)

以下の性質を利用する。
・四元数の要素である1,-1,i,-i,j,-j,k,-kはどれも4乗すると1になる。
sをX個連結した後に3分割するので、各分割の中にはsがそれぞれ幾つか含まれていなければならない。その個数をそれぞれa,b,cとする。また、sの文字を全て掛けたものをhとおく。この時、
・最初の分割の積=h^a * (sの途中までの積) = i
・真ん中の分割の積=h^b * (sの途中から別のsの途中までの積) = j
・最後の分割の積=h^c * (sの途中からsの最後までの積) = k
みたいな感じになる(厳密にはa+b+c=X-2やa+b+c=X-1の場合等がありえる)
そしてh^4=1なので、a,b,cは4で剰余をとってよかったりする。
そう考えると考えるべき状態数は
a,b,cが0,1,2,3のそれぞれの場合について考えれば良いのだから、
X = min(X, 12+X%12)
として良い。こうするとX<24だから十分間に合う。

SRM636 Div2 Hard : ChocolateDividingHard

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13388

h×wのグリッドが与えられる。各グリッドには0~9の文字が欠かれている。このグリッドを、切り込みを入れて4×4に分割する。

それぞれのブロックの中のグリッドの数字の和の最小値を最大にする問題。

制約：h,w<=75

解法

上手く切り込み入れて和の最小値をk以上にすることが出来るかを判別。

縦の切り込みを全通り試して、k以上に出来るかを貪欲にやる。
判定は、累積和やったりして多分O(75^4logN)くらいで危ない気がしたけどなんか通った。

n項間線形漸化式を持った数列の一般項

体K上の数列{x_i}がp=0,1,2,...に対して

の関係を満たすとき、線形回帰数列と言います。例えば加算個の状態を持ったマルコフモデルとかでの定常分布でこういう式が出てきて一般項を求めたい、もしくは三重対角行列の行列式を求めるときにこういう感じの漸化式が出てくると思いますが、今回はそれを解決したいと思います。
なお、本記事は
斎藤正彦著『線形代数入門』『線形代数演習』(東京大学出版会)
を参考にさせて頂いております。ちなみにこの本はとても良い本です。

出来るだけ事前知識を必要としないように書くつもりですが、やはり線形代数の基礎的な知識(次元や基底の定義とか)は必要だと思います。

目標

さて、まずは「体K上の数列の集合」を考えます。(大体KはRもしくはCです)
この集合の部分集合として上の漸化式を満たすものの全体をVとします。今回はこの空間Vが実は線形空間でしかもその次元がnであることを示した後、n個の基底の構成方法を述べることによってVの任意の元すなわち上の漸化式を満たす数列がこれらの基底の線形結合で表せる、ということを述べます。

まず、二つの数列{a_i},{b_i}に対して加法とスカラー乗法を定義しますがこれは簡単で
{a_i}+{b_i} = {a_i+b_i}
k*{a_i} = {k*a_i}
と定義します(普通のやつです)

Vが線形空間かどうか

そして数列{x_i},{y_i}∈Vの時、{x_i}+{y_i}及びk*{x_i}は明らかにVの要素になっている(実際に計算すれば確かめられます)ので、Vはこれらの演算で閉じていて、Vの零元を{0,0,...}と定義すれば確かに零元になっていて結合則とかもろもろは体K上の数列であることから実際に計算してみれば明らかですので、Vは線形空間となっています。

Vの次元は?

VからK^nへの写像Tを「数列の最初のn項を取り出す写像」つまり

と定義します。これはT(ax+by)=aT(x)+bT(y)より明らかに線形写像で、任意のK^nの要素に対してそのn個の数を最初のn項にした数列がV内に存在するため全射で、違う数列は違う値に移されるため、全単射である。従って同型写像である。

同型写像が存在する時、どちらの空間も次元が等しいため、

dimV = dim(K^n) = n

です。これはV内のn個の線形独立な数列を見つけたらVの任意の要素がこれらの線形結合で表されることに他なりません。

解

1.特性多項式

ここが一番大事なところです。そのためにまずVからVへ移す写像DとIを考えます。

Iは恒等写像で、Dはずらし変換、即ち

と定義します。DがVからVへ移すことはDによって数列のn項間の関係が変化しないことから明らかです。また、写像f,gの加法と乗法及びスカラー乗法を

(f+g)(x) = f(x)+g(x)

(fg)(x) = f(g(x))

(k*f)(x) = k*f(x)

と定義すると、Iは当然ながらDも

D(ax+by) = aD(x)+bD(y)

となります。そしてDの冪乗D^nもDをn回合成した写像として定義することが出来ます。

この定義に基づくとこの画像で確かめている通り

(aD+bI)と(cD+dI)は交換可能(AB=BA)であることが分かります。

最初の漸化式の左辺をpに関する一般項とする数列{0_p}は、恒等的に0、即ち零元だから

0_p = (D^n(x))_p + (a_1*D^(n-1)(x))_p + ... + (a_{n-1}*D(x))_p + (a_n*I(x))p = 0

写像の和算の定義より右辺は

となり、これがどのpに対しても0だから

となります。この()内のDをスカラーuに変えて多項式にしたものを特性多項式と呼びます。これをΦ(u)で表すことにします。すると上の式はΦ(D)x=0と表記できます。注意してほしいのはこれの左辺は数列を表すものであって、スカラーではないということです。

2.特性多項式の根から解を生成する

代数学の基本定理より、特性多項式の根はn個あります。これらのn個の根をそれぞれb1,b2,...,bnとします。

この時、Φ(u)=(u-b1)(u-b2)...(u-bn)

と表され、先ほど確かめた通り、交換可能な者同士の積ならばDとIに関しても展開した結果が普通の展開と結果が同じになるので、Φ(D)=(D-b1I)(D-b2I)...(D-bnI)となります。

ここで、各(D-biI)と(D-bjI)は交換可能だから、あるkに対してxが(D-bkI)x=0となっている時、かけ算の順序で(D-bkI)を最後に持ってきて

Φ(D) = (D-b1I)...(D-bnI)(D-bkI)x = 0

は明らか。

従って、(D-biI)^mi x=0 (miは解biの重複度)

の解を全てのbiに対してmi個ずつ見つけ、これらが線形独立であることを証明すれば、n個の基底が見つかったことになる。

mi=1のとき

(D-bi)x=0よりDx=bi*x

Dxは一項ずらすものなので、これは明らかに公比がbiの等比数列である。つまり例えば

x_k = (bi)^{k}

が解である。

mi>1のとき

(D-bi)^m (x)=0

天下り的だが

x_k = k^j *(bi)^{k-1} (j=0,1,...,mi-1)

を考えると確かにこれらは(D-bi)^mi(x) = 0のmi個の解になっている。

以上より、m1+m2+... = n個の解が構成出来た。

また、これらの解が線形独立であることは実際にこれらの数列の線形結合が0に等しいならば自明な線形関係が成り立つ(係数が全て0である)ことによって示すことが出来る。

最後らへんは結構投げやりだが、これによって線形回帰数列を求めることが出来た。

拡張ユークリッドの互除法

不定方程式の中でも比較的有名なベズー方程式を解くアルゴリズムとして比較的有名な拡張ユークリッドの互除法を、線形代数の視点から考えてみました。
具体的には
・拡張ユークリッドの互除法によって得られるもの
・解空間はどのように構成出来るか
について色々考えました。必要な知識は
・拡張してないユークリッドの互除法
・行基本変形
・線形代数の基礎すぎる知識(各行が線形独立な行列は正則だよとか)
・線形代数の各種すぎる定義(A+B={x+y ; x∈A,y∈B}とか線形独立とか)

です。線形代数が好きでユークリッドの互除法を拡張したい人にはぴったりなトピックだと思います。

問題

零でない整数a,b,cにたいして、

ax+by=c

の解空間を構成せよ。

考察

ベズーの補題より、gcd(a,b)がcを割り切ることが解の存在性の必要充分条件です。

よくよく考えると、gcd(a,b)=dとおくとax+byはdの倍数なので割り切らない時は解が存在しないので対偶をとると解が存在する条件が「dがcを割り切る」ということが分かります。逆に割り切るならば解が存在することも示したいのですが、これは具体的な解の構成方法を示すことによって示します。以下ではcはdを割り切りc=mdというのを前提に話を進めます。

1.拡張ユークリッドの互除法とは？？

(1.1)ax+by=d

(a,b)に対してgcd(a,b)を求める手続きがユークリッドの互除法です。この手続きを行列の行基本変形に拡張して考えることによって(1)を解くことが出来ます。それが拡張ユークリッドの互除法です。要するに方程式(1.1)を解くアルゴリズムです。

(1 0) (a) = (a)

(0 1) (b) = (b)

に対して、(a,b)に対して行われるユークリッドの互除法は

・片方から片方の定数倍引く

・入れ替える

なのでどちらの操作も同等な基本行列が存在します。そして有限回で終了するのでその有限個の行列を左から掛けていくことによって最終的には右辺のベクトルが(d,0)になってその時の係数行列の１行目の2つの要素が方程式(1.1)の解になっているという訳です。なお、2行目の2つの要素は(ax+by=0)の解となっています。

2.方程式(1.1)の解空間はどんな空間？？

まず(1.1)の解空間を考えます。色々知っている人は斉次なんちゃらと似てると思いますがその通りです。色々しっていなくても必要な知識さえあれば証明できますが、結論から言うと

(x0,y0)を(1.1)の非ゼロな要素,(z0,w0)をax+by=0の非ゼロな解

とすると(1.1)の任意の解は任意の整数kで

(x0 + k*z0 , y0 + k*w0)

と表すことが出来ます。

3.ax+by=c=mdの解空間は？？

結論から言えば

(m*x0 + k*z0, m*y0 + k*w0)

と表すことが出来ます。証明は2と同じ感じでした。

解

入力されたa,b,cに対して,

拡張ユークリッドの互除法によって得られた係数行列の成分を

(x,y)

(z,w)

とする。また、この時d=gcd(a,b)である。

・dがcを割り切らない時は解なし、つまり空集合

・dがcを割り切る時は、m=c/dとして

{ (m*x + k*z , (m*y + k*w) ; k∈整数 }

が解であり、従って割り切るときは必ず解が存在するのでベズーの補題が示されたことになります。

CF 527 C .Glass Carving

問題

http://codeforces.com/problemset/problem/527/C

解法

二分探索

yukicoder 158 奇妙なお使い

問題

http://yukicoder.me/problems/125

解法

DP.

f(i,j,k) : 1000円をi枚 100円をj個 1円をk個持ってるときにいける回数とする.

1000円を沢山持ってると後々で困ったりするので、Db円やDc円を払うときは1000円、100円を出来るだけ使うようにする必要がある。つまり払うときの枚数は貪欲にすれば良い。なので、(i,j,k)持ってるときに

・Bさんのとこに行った後の枚数(ib,jb,kb)

・Cさんのとこに行った後の枚数(ic,jc,kc)

を求めると

f(i,j,k) = max(f(ib,jb,kb),f(ic,jc,kc))+1

とすれば求まる。

KODER COMBAT : Divide It

Problem

https://www.hackerrank.com/contests/koder-kombat-mar/challenges/divide-it

Solution

When we used i segments and got t-divided paper and add a new segment to it , we can get k new intersections(k=0,1,...,i-1) and t+i+1-divided paper.
Let (t,i) is a state of t-divided paper using i segments.
Then, (t,i) -> (t+1,i+1) , (t+2,i+1) , ... (t+i-1,i+1).

Code

int main() {

    int t;cin>>t;

    while(t--){

        int m;cin>>m;

        for(int i=0;i<m;++i){

            if(1+i*(i+1)/2>=m){

                cout<<i<<endl;

                break;

            }

        }

    }

    return 0;

}

HackerRank: AntiPalindromic Strings

問題

https://www.hackerrank.com/challenges/antipalindromic-strings
m種類のアルファベットによって表記されるn文字の全ての文字列の中で、その2文字以上の連続部分文字列として回文を一つも含まないようなものは何通りあるか。

解法

nとmで表せる。

CF 518 C. Anya and Smartphone

問題

http://codeforces.com/problemset/problem/518/C
スマホのホーム画面のアイコンを選択するのに最小のタップ数を求める感じの問題。

解法

読んで書くだけ

CF 518D. Ilya and Escalator

問題

エスカレーターの前にn人並んでいる。先頭の人は1分毎に確率pで勇気を振り絞ってエレベーターに乗り、1-pでその場にとどまる。エレベーターに乗れるのは先頭の人だけ。また、一度乗ったエレベーターは二度とおりることはない(こわい)
この時、t分後にエレベーターに乗っている人数の期待値を求める問題。

解法

前からi番目の人がt分以内に乗る確率をDPで求めて足す。

CF 518F. Pasha and Pipe

問題

http://codeforces.com/problemset/problem/518/F

二次元グリッド内にパイプが何通り引けるかを求める問題。

グリッドのセルは * か . で構成されていて、パイプは . のセルにしか引けず、更に様々な条件がある。

解法

[座標][次に向かおうとする方向][何回曲がったか]でDP.

CF 514 E. Darth Vader and Tree

問題

http://codeforces.com/problemset/problem/514/E
各ノードの子の数がn個でそれぞれの子へのエッジの重みがd[i]で与えられた木に対して、根ノードから距離x以下にあるノードの個数をカウントする問題。

解法

d[i]の範囲が1以上100以下なので100*100の行列にして繰り返し二乗法

CF 508D

問題

3文字の文字列がn個与えられる。これらの文字列を連続部分文字列として含むような文字列を構成せよという問題。

解法

以前紹介したしりとりの問題と同じような感じでやってDFSする。
しかし文字の種類が62種類あり、グラフのノード数はその二乗あるので上手くDFSしなきゃいけない。

POJ 3254 Corn Fields

問題

http://poj.org/problem?id=3254

n*mのグリッドが与えられる。各要素は0または1であり、1のグリッドには物を置くことが出来る。隣接した二つのマスにものを置いてはいけないという制約下で、何通りの置き方があるかを答える問題。

解法

dp[i][bit] = i列目を状態bitで置いた時の置き方の場合の数

とするとO(2^(n+m))で解ける。

最初は0も連続してはいけないと勘違いしてて変なこと書いてた。

yukicoder 150 "良問"(良問とは言っていない

問題

http://yukicoder.me/problems/344

要するに入力された文字列sを、

先頭から見たときに"good","problem"がこの順に見つかるようにするためには何文字変更するべきかを求める問題。

100個の100字以内の文字列に対して探さなければならない。

解法

tbl1[i] = str[0~i]の中で"good"とのハミング最小距離

tbl2[i] = str[i~n-1]の中で"problem"とのハミング最小距離

とすると,tbl1[i]+tbl2[i+1]で求めることが出来る。

tbl1[i] = min(tbl[i-1], haming("good", str[i-3~i])

で求められるのでO(4・n) = O(n)

tbl2も同様にして求めることが出来る。

なので全体としてO(n)で求めることが出来る。

SRM 647 Div2 Hard

問題

各成分が0以上の成分であるa[i](1<=i<=N)を以下の条件を満たすように定めたい。
1. | a[i] - a[i+1] | <= K
2. a[x[i]] <= t[i]
取りうる数列の最大値を求めよ.
ただし
N<=10^9くらい
size(x) = size(t) <= min(500,N)

解法

xとtのサイズが小さいのでa[x[i]]から傾きKの直線を弾いて交差するものを縮め、それを逆向きにもやって更新がなくなるまで続けた後に最大の高さを求めるみたいなことをやる。

SRM 648 Div2 Hard

問題

整数NとKが入力として与えられる。
次の二つの条件を満たす長さnの文字列sをどれでも良いので一つ出力せよ。
1. sの各文字はA,B,Cのどれかである
2. s[i]<s[j]かつi<jとなるような(i,j)のペアがちょうどK個ある

3<=N<=30, K<=N(N-1)/2

解法

A,B,Cで構成出来る10文字くらいまでの全ての文字列に対してKを求めて色々眺めてみると、「前半2/3はA,Bのみで構成しても良い」ということが分かる。

(例えばN=8とN=9に対して並べたもの)

よって前半2/3文字は全探索で予めテーブルを
tbl[Aの個数][Kの値]
で作っておき、残りの1/3は全探索して足してvalidになったらそれを出力する。
残りの1/3の全探索の時、テーブルのどこが条件を満たすかの条件はO(N)で分かる。

N<=30なので、計算量としては2^(20)*3^(10)*30でかなり危なかったけどなんとか通った。

他のコードを見ると場合分けしまくっててかなり賢かった。

SRM 649 DIV2 Mid

問題

自然数NとKが入力される(どちらも100以下)
最初、集合AをA={N}とする。
何度かのステップでAの要素を全て0にしたい。一つのステップでは、Aの要素全てに対して、それぞれに1と2のどちらかを適用することが出来る。
1.その要素akをAから削除した後、akを二つの和に分割してAに追加する。
つまり、A -> A-{ak}+{i,ak-i}(1<=i<=ak-1)
2.akの値を1減らす
また、制約として1.の操作は全部で2回しか行うことが出来ない。

(最終的なAの要素数はいくらになっても構わない)
最小ステップ数はいくらか。

Sample Input

N=5,K=2の場合
{5} -> {2,3} (1の操作) -> {1,2} (2の操作) -> {1,1}(1の操作を1に,2の操作を2に) -> {0,0}

N=15,K=4の場合
{15} -> {7,8} (1の操作) -> {3,4,4,4} (2の操作を2回適用) -> {2,2,2,3,3} (1の操作は残り1回しか適用できないので一つの4に適用してあとは1の操作) -> {0,0,0,0,0}(1の操作を3回)
の合計6ステップ。

解法

f(n,k) = {n}をk回の分割が許容された状態における最小ステップ数
とおいてDP.

yukicoder 134 走れ！サブロー君

問題

http://yukicoder.me/problems/273

解法

bitDP.
解法は問題見てすぐ分かって紙にプログラム書いてバカみたいにたくさんメモリとってたけどまぁなんとかなった。
状態を規定するのは訪問済みノードのbitと今いるノードで十分だけどdfsするときに引数として今の重さを持ってると余計な計算しなくて良いから楽だと気づいた。