No.918 LISGRID

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

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

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題（複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 45
作問者 :

ningenMe / テスター :

tempura_pp

7 ProblemId : 3092 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2020-12-06 13:00:40

$H$ 行 $W$ 列からなるグリッドがあります。
最初全てのマスには何も書かれていません。
ここに以下の条件を満たすように $H W$ 個の全てのマスに数字を書き込むことを考えます。

長さ $H$ の整数列 $S_{1}, S_{2}, \dots, S_{H}$ を考える。
$i$ ( $1 \leq i \leq H$ )番目の要素 $S_{i}$ を「グリッドの $i$ 行目に書き込まれた $W$ 個の数字を左から右に向かって順に見たものを一つの数列としたときの、その数列の最長増加部分列の長さ」と定義する。
この数列 $S$ の要素の順番を適切に並び替えると、数列 $A$ と一致させることが可能である。

長さ $W$ の整数列 $T_{1}, T_{2}, \dots, T_{W}$ を考える。
$j$ ( $1 \leq j \leq W$ )番目の要素 $T_{j}$ を「グリッドの $j$ 列目に書き込まれた $H$ 個の数字を上から下に向かって順に見たものを一つの数列としたときの、その数列の最長増加部分列の長さ」と定義する。
この数列 $T$ の要素の順番を適切に並び替えると、数列 $B$ と一致させることが可能である。

ここで部分列とは「ある整数列の要素を

0

個以上いくつか選んで削除し、残ったものを元の順序を保って並べた整数列」を表します。
増加部分列とは「整数列の部分列のうち、隣接する

2

要素を見ると常に右の方が真に大きいもの」を表します。
また最長増加部分列とは「増加部分列の長さが最長であるもの」を表します。

これらの条件を全て満たすように数字を書いたグリッドを一つ構築してください。
なお、条件を満たすグリッドは少なくとも一つ存在することが証明できます。

 $H W$ 
 $A_{1} A_{2} \dots A_{H}$ 
 $B_{1} B_{2} \dots B_{W}$

入力は全て整数である
$1 \leq H, W \leq 400$
$1 \leq A_{i} \leq W (1 \leq i \leq H)$
$1 \leq B_{i} \leq H (1 \leq i \leq W)$

 $C_{1, 1} C_{1, 2} \dots C_{1, W}$ 
 $C_{2, 1} C_{2, 2} \dots C_{2, W}$ 
 $⋮$ 
 $C_{H, 1} C_{H, 2} \dots C_{H, W}$

条件を満たすグリッドを上記の形式で出力してください。
出力するグリッドの要素は $1$ 以上 $H W$ 以下であり、全て異なります。
最後に改行してください。

2 2
2 1
2 2

2 1
3 4

この出力例のとき、図のように $S = {1, 2}, T = {2, 2}$ となります。
$S$ の要素の順番を並べ替えると $A$ に一致させることができ、 $T$ は既に $B$ に一致しているため条件を満たします。

3 2
2 2 2
3 2

1 5
2 3
4 6

答えは複数存在することがあります。

2 5
2 3
2 1 2 1 2

10 9 2 1 7
4 3 6 5 8

部分列の定義に「元の数列において連続であること」は含まれていないことに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。