Hatena::Grouptopcoder

pepsin-amylaseの日記

 | 

2013-12-03競技プログラミング アドベントカレンダー Div.2013 3日目

不定・不能と線型代数

20:43

さて、いろいろな連立一次方程式に掃き出し法を適用していくと、様々なケースに出会います。

まずはこちらのケース。

\left\{ \begin{array}{l} x+2y+3z=6 \\ 2x+5y+4z=11 \\ 3x+3y+7z=18 \end{array} \right.

これに掃き出し法を適用すると、途中でに次のようになります。

\left\{ \begin{array}{l} x+7z=8 \\ y-2z=-1 \\ 0=1 \end{array} \right.

最後の式がおかしいですね。このような連立一次方程式は不能であるといい、解が存在しません。

次はこちら。

\left\{ \begin{array}{l} x+2y+3z=6 \\ 2x+5y+4z=11 \\ 3x+3y+7z=17 \end{array} \right.

先ほどの例に似ていますが、最後の定数が違います。こちらに掃き出し法を適用すると次のようになります。

\left\{ \begin{array}{l} x+7z=8 \\ y-2z=-1 \\ 0=0 \end{array} \right.

この場合は z を移項し

\left\{ \begin{array}{l} x=8-7z \\ y=-1+2z \end{array} \right.

とすることで、z をパラメータとした解を表示する事ができます。この場合は連立一次方程式が不定であるといい、解が複数存在します。

さて、連立一次方程式の解には3つの場合があることがわかりました。

  • 一意に定まる
  • 存在しない(不能)
  • 複数存在する(不定)

このような状態を調べるために、線型代数で用いられる行列の階数(ランク)を定義します。今回は、競技プログラミングに適した形で導入します。

  • 行列 A に掃き出し法を適用した結果の行列のうち、0でない要素を含む行の個数を A の階数と呼ぶ。

これを用いて、次のようにして解の様子を調べることができます。

  • 係数行列と拡大係数行列の階数が異なるときは不能
  • 係数行列と拡大係数行列の階数が等しく、係数行列の階数と変数の個数が異なるときは不定
  • 係数行列と拡大係数行列の階数と変数の個数がすべて等しいときは一意解が存在

掃き出し法は連立方程式の解を変えずに変形を繰り返すアルゴリズムです。係数行列と拡大係数行列の階数が異なるとき、掃き出し法の終了後の行列は不能な連立一次方程式の例のように定数ベクトルの部分だけに非ゼロの成分が残ります。これは 0 = 1 を意味し、矛盾します。したがって、この場合には解が存在しないのです。

先に述べたように掃き出し法は解を保存しますので、係数行列のランクは連立方程式を解くときに変数をいくつ消去することができるかを示していると解釈できます。したがって、これによってちょうど変数が全て消去できるならばそれが一意の解となり、余る変数があるならば余った変数を用いて解のパラメータ表示ができるので解は複数個あることになります。ちなみに、このときのパラメータの個数を解の自由度と呼びます。一意解が存在することは解の自由度が 0 であるともいえます。

例題 Tree Reconstruction

今年の JAG 春コンテストから例題を1つ解いてみます。

問題はこちらです。J: Tree Reconstruction - Japan Alumni Group Spring Contest 2013 | AtCoder

問題概要

有向グラフが与えられる。ここに非負流量の循環フローが流れていることがわかっている。すなわち、各辺に非負の流量が設定されていて、各頂点は流量保存則を満たす。あなたは各辺の流量を知らないが、できるだけ少ない辺を調べてすべての辺の流量を決定したい。いくつの辺を調べればよいか求めよ。

解法

頂点 v に関する流量保存則は v に入る辺の流量の和と v から出る辺の流量の和が等しいというもので、これは各辺の流量を変数と見た時に一次式です。したがって、すべての頂点について立式して連立することで連立一次方程式を得ます。この連立一次方程式はすべての流量が 0 という自明解を持ちます(フローが全く流れない場合に対応します)ので、不能ではありません。不能でないとき、連立一次方程式は解の自由度を持ちますが、これは消去しきれずに残った変数の個数のことでした。したがって、この残った変数の値(= ある辺での流量)がわかれば、解が一意に定まることになります。以上の議論から、出力すべき答えはこの連立一次方程式の解の自由度で、これは掃き出し法によって求められます。

出題者による解説もあります。

有効なWikiNameではありません - ACM-ICPC Japanese Alumni Group

例題 XorCards

SRM 590 の Div.1 Medium 問題に、連立一次方程式の解の数え上げによって解く問題が出題されました。

問題はこちらです。TopCoder Statistics - Problem Statement

問題概要

いくつかの非負整数が書かれたカードが与えられる。このカードの部分集合のうち、部分集合すべての xor を取った値が、ある整数 limit 以下になるようなとり方は何通りあるか求めよ。

解法

xor sum について考えます。例えば、limit が 22 = 0b10110 であったとき、考えられる xor sum は次のようになります(? は don't care)。

  • 0b0????
  • 0b100??
  • 0b1010?
  • 0b10110

要するに、1 が立っているところを 0 にして以下を don't care にしたものを列挙しています。これらの表す集合は互いに重複しないので、それぞれの場合について考えます。たとえば xor sum = 0b100?? のときについて考えます。

カードの数を 18, 6, 20、各カードを選択するかどうかをx_0, x_1, x_2とすると、

18 \cdot x_0 \quad xor \quad 6 \cdot x_1 \quad xor \quad 20 \cdot x_2 = 0b100??

これを bit wise に考えると、例えば最上位ビットは次のようになります *1

1 \cdot x_0 + 0 \cdot x_1 + 1 \cdot x_2 = 1

これを定数が don't care でない各ビットについて連立させた方程式の解の個数を数え上げればよいことになります。これは mod 2 上での連立一次方程式です。mod を取るときの話をしていませんでしたが、mod を取る数が素数の場合は基本的には割り算のところを修正する(逆元を掛けるようにする)だけで問題なく掃き出し法が使えます。実際に掃き出し法を行うことで、解のパラメータ表示を得ます。このとき、各パラメータが 0, 1 のみを取ること、パラメータが異なれば解も当然異なることを考えると、この方程式の解の個数は 2^(解の自由度) であることがわかります。

全体として、xor sum の各ケースについて連立一次方程式の解を数え上げて足せば、求める答えになります。

公式の解説もあります。

Login - TopCoder Wiki

*1: xor 演算が mod 2 での足し算であるという事実を用いています

 |