この記事は 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ヶ月しかありませんが、来年からのコンテストではぜひ線形代数や連立一次方程式を背景とした問題を解きまくってくださいね！