大雑把な考え方

（これは writer の行った考察の例です）

1. \(P_1\) 行目、 \(Q_1\) 列目をすべて 0 で埋める
2. 残りのマスについて、 \(i\) 行目のうち \(Q_1\) 列目以外を結合した文字列を \(S'_i\) 、 \(j\) 列目のうち \(P_1\) 行目以外を結合した文字列を \(T'_j\) としたとき、\(S'_{P_2} < S'_{P_3} < \dots < S'_{P_N}\) および \(T'_{Q_2} < T'_{Q_3} < \dots < T'_{Q_N}\) が成り立つように同じ方法で再帰的に書き込む

でとすればうまくいきそう

→辞書順について等号が成り立ってはいけないので「残りの各行、列は 1 を \(1\) つ以上含まなければならない」という条件が追加されてしまい、「同じ方法で再帰的に書き込む」がうまくできない…

→ 書き込みが全部 0 になるのがよくないので \(P_1\) 行目と \(Q_N\) 列目にそれぞれ 0,1 を書き込みようにすればうまくいきそう？

解法

1. \(P_1\) 行目のマスすべてに 0 を書き込む
2. \(Q_N\) 列目のマスのうちなにも書き込まれていないマスすべてに 1 を書き込む
3. 残りの \((N-1) \times (N-1)\) マスについて、\(i\) 行目のうち \(Q_N\) 列目以外を結合した文字列を \(S'_i\) 、 \(j\) 列目のうち \(P_1\) 行目以外を結合した文字列を \(T'_j\) としたとき、\(S'_{P_2} < S'_{P_3} < \dots < S'_{P_N}\) および \(T'_{Q_2} < T'_{Q_3} < \dots < T'_{Q_N}\) が成り立つように同じ方法で再帰的に書き込む

というアルゴリズムで書き込みを行うと書き込みは条件を満たします。特に問題文で述べられた条件のほかに

• 各列は 0 が書き込まれているマスを \(1\) つ以上含む

という条件も満たします。

これは

• 各列は \(P_1\) 行目に必ず 0 が書き込まれているため、 0 が書き込まれているマスを \(1\) つ以上含む

• \(P_1\) 行目は 1 を含まず、 \(P_2\) 行目は 1 を含むため \(S_{P_1} < S_{P_2}\) が必ず成り立つ

• \(Q_N\) 列目は \(P_1\) 行目以外は 1 で、 \(Q_{N-1}\) 列目は再帰的な書き込みで \(P_1\) 行目以外に 0 が書き込まれているマスが存在するので \(T_{Q_{N-1}} < T_{Q_N}\) が必ず成り立つ

• \(S_{P_i}\ (2\leq i)\) の辞書順は \(S'_{P_i}\) の辞書順に等しいため、再帰的な書き込みにより \(S_{P_2} < S_{P_3} < \dots < S_{P_N}\) が満たされる。 \(T_{Q_i}\ (i \leq N-1)\) についても同様

から \(N\) についての帰納法で示すことができます。

また、再帰的な書き込みの部分の挙動を考えると、結局以下のような書き込みを \(i=1,2,\dots,N\) の順で行えば条件を満たすことが分かります。

• まず \(P_i\) 行目のマスのうち、まだ何も書き込まれていないマスに 0 を書き込む。その後、 \(Q_{N+1-i}\) 列目のマスのうち、まだ何も書き込まれていないマスに 1 を書き込む