問題一覧 > 数学的知識問題

No.3007 組み紐

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 12
作問者 : ジュ・ビオレ・グレイスジュ・ビオレ・グレイス / テスター : 👑 p-adicp-adic
3 ProblemId : 11798 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-01-10 18:48:08

問題文

$1$ 以上 $N$ 以下の整数からなる有限長の数列（空列も許容する）に対して、以下の操作を考えます:

  1. $1$ 以上 $N$ 以下の同じ数字が二個連続しているところを取り除く。
  2. $1$ 以上 $N$ 以下の同じ数字を二個連続でどこかに挿入する（先頭、末尾も可）。
  3. $1$ 以上 $N$ 以下の $i$ と $j$ が $|i-j| > 1$ となるとき、隣接する $i, \ j$ を $j, \ i$ に書き換える。
  4. $1$ 以上 $N$ 未満の $i$ について、隣接する $i,\ i+1, \ i$ を $i+1, \ i, \ i+1$ に書き換える。
  5. $1$ 以上 $N$ 未満の $i$ について、隣接する $i+1, \ i, \ i+1$ を $i,\ i+1, \ i$ に書き換える。
この5種類の操作を毎回勝手に選び何度か繰り返すことで、$1$ 以上 $N$ 以下の整数からなる数列 $A_1, \dots, A_K$ から $B_1, \dots, B_L$ を作ることができるとき、数列 $A$ と $B$ は「接続可能」ということにします。
さて、入力から与えられる $1$ 以上 $N$ 以下の整数からなる数列 $A_1, \dots, A_K$ と $B_1, \dots, B_L$ について、これらが接続可能であるかどうかを判定し、接続可能ならば YES、そうでないならば NO と出力してください。

入力

$N \ K \ L$
$A_1 \ \cdots \ A_K$
$B_1 \ \cdots \ B_L$

$1 \leq N, K, L \leq 10^4,$
$1 \leq A_k, B_l \leq N.$

出力

最後に改行してください。

サンプル

サンプル1
入力
1 3 2
1 1 1
1 1
出力
NO

$N = 1$ のときは、$K - L$ の偶奇を判定する問題になっている。

サンプル2
入力
4 4 6
3 2 4 3
2 3 4 2 3 4
出力
YES

$3 \ 2 \ 4 \ 3 \rightarrow 3 \ 2 \ 3 \ 3 \ 4 \ 3 \rightarrow 2 \ 3 \ 2 \ 3 \ 4 \ 3 \rightarrow 2 \ 3 \ 2 \ 4 \ 3 \ 4 \rightarrow 2 \ 3 \ 4 \ 2 \ 3 \ 4$

サンプル3
入力
100 7 8
3 8 13 18 23 28 33
4 8 12 16 20 24 28 32
出力
NO

問題文で与えられる操作では、数列の長さの偶奇は変わらないため、互いに移り合わない。

サンプル4
入力
100 2 6
1 1
99 100 99 100 99 100
出力
YES

$99 \ 100 \ 99 \ 100 \ 99 \ 100 \leftarrow 100 \ 99 \ 100 \ 100 \ 99 \ 100 \leftarrow 100 \ 99 \ 99 \ 100 \leftarrow 100 \ 100 \leftarrow \ \ \ \leftarrow 1 \ 1$

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