No.2446 完全列

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 教育的問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 16
作問者 : 👑

p-adic / テスター : 👑

AngrySadEight

1 ProblemId : 9631 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2023-08-30 09:55:39

問題文

入力に $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

入力

出力

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もしくは右上の雲マークをクリックしてアカウントを作成してください。