No.2446 完全列
タグ : / 解いたユーザー数 15
作問者 : 👑
p-adic
/ テスター :
👑 
AngrySadEight
問題文
入力に $3$ 個の正整数 $L, M, N$ と、整数係数 $L \times M$ 行列 $A$ と整数係数 $M \times N$ 行列 $B$ が与えられます。
$(A,B)$ が良い組であるとは、任意の実数係数 $M$ 次元縦ベクトル $x$ に対して以下の $2$ 条件が同値であるということです：
- $Ax$ が零ベクトルである。
- $x = By$ を満たす実数係数 $N$ 次元縦ベクトル $y$ が存在する。
$(A,B)$ が良い組か否かを判定してください。
背景
左から $A$ を掛ける操作が定める線形写像 $\mathbb{R}^M \to \mathbb{R}^L$を $g$、左から$B$ を掛ける操作が定める線形写像 $\mathbb{R}^N \to \mathbb{R}^M$を $f$ と置きます。ホモロジー代数という分野においては、$(A,B)$ が良い組であるということを、線形写像の列
$\displaystyle \mathbb{R}^N \stackrel{f}{\to} \mathbb{R}^M \stackrel{g}{\to} \mathbb{R}^L $
が完全であると表現したり、完全列であると表現したりします。完全列という概念は代数の加群論や幾何などで多用されますし、圏論でも広く扱われていて近代数学における基本的な道具の１つです。
入力
以下、行列 $C$ の列数以下の正整数 $i$ と行数以下の正整数 $j$ に対し、$C_{i,j}$ で $C$ の $(i,j)$ 成分を表します。
入力は以下の形式で標準入力から $1 + L + M$ 行で与えられます。
- $1$ 行目に $L, M, N$ が半角空白区切りで与えられます。
- $L$ 以下の各正整数 $i$ に対し、$1 + i$ 行目に $M$ 以下の各正整数 $j$ に対する $A_{i,j}$ が $j$ の小さい順に半角空白区切りで与えられます。
- $M$ 以下の各正整数 $j$ に対し、$1 + L + j$ 行目に $N$ 以下の各正整数 $k$ に対する $B_{j,k}$ が $k$ の小さい順に半角空白区切りで与えられます。
$L$ $M$ $N$
$A_{1,1}$ $\cdots$ $A_{1,M}$
$\vdots$
$A_{L,1}$ $\cdots$ $A_{L,M}$
$B_{1,1}$ $\cdots$ $B_{1,N}$
$\vdots$
$B_{M,1}$ $\cdots$ $B_{M,N}$
制約
入力は以下の制約を満たします：
- $L, M , N$ は $1 \leq L, M, N$ かつ $LM, MN \leq 15$ を満たす整数
- $A , B$ の各成分 $a$ は $-6 \leq a \leq 6$ を満たす整数
出力
$(A,B)$ が良い組である場合はYesと、良い組でない場合はNoと出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 1 1 -2 3
出力
No
$A = (-2)$ かつ $B = (3)$ です。実数係数 $1$ 次元縦ベクトル $x$ を $(1)$ と定めると、$Ax = (-2 \cdot 1) = (-2)$ は零ベクトルではありませんが、実数係数 $L = 1$ 次元縦ベクトル $y$ を $(3^{-1})$ と定めると $x = By$ が成り立ちます。
サンプル2
入力
1 1 1 0 0
出力
No
$A = (0)$ かつ $B = (0)$ です。実数係数 $1$ 次元縦ベクトル $x$ を $(1)$ と定めると、$Ax = (0 \cdot 1) = (0)$ は零ベクトルですが、$x = By$ を満たす実数係数 $L = 1$ 次元縦ベクトル $y$ は存在しません。
サンプル3
入力
1 2 1 1 0 0 1
出力
Yes
$\displaystyle \begin{array}{rcl} \displaystyle A &\displaystyle = &\displaystyle \left( \begin{array}{cc} 1 & 0 \end{array} \right) \\ \displaystyle B &\displaystyle = &\displaystyle \left( \begin{array}{c} 0 \\ 1 \end{array} \right) \\ \end{array} $
です。$x$ を実数係数 $2$ 次元縦ベクトル $x$ とし、実数 $x_0, x_1$ を用いて
$\displaystyle x = \left( \begin{array}{c} x_0 \\ x_1 \end{array} \right) \\ $
と置きます。$Ax = (1 \cdot x_0 + 0 \cdot x_1) = (x_0)$ より、$Ax$ が零ベクトルである必要十分条件は $x_0 = 0$ です。
$x_0 = 0$ ならば、実数係数 $1$ 次元縦ベクトル $y$ を $(x_1)$ と定めると $x = By$ となります。逆に $x = By$ を満たす実数係数 $1$ 次元縦ベクトル $y$ が存在するならば、実数 $y_0$ を用いて $y = (y_0)$ と置くと
$\displaystyle \left( \begin{array}{c} x_0 \\ x_1 \end{array} \right) = x = By = \left( \begin{array}{c} 0 \\ 1 \end{array} \right) (y_0) = \left( \begin{array}{c} 0 \\ y_0 \end{array} \right) $
となるので、第 $1$ 成分を比較することで $x_0 = 0$ であることが分かります。以上より、$x_0 = 0$ であることと $x = By$ を満たす実数係数 $1$ 次元縦ベクトル $y$ が存在することは同値です。すなわち $(A,B)$ は良い組です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。