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

No.3007 Braid

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 14
作問者 : ジュ・ビオレ・グレイス / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 11798 / 自分の提出
問題文最終更新日: 2025-01-10 18:48:08
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 455 (順位表) の他の問題:

Problem Statement

Consider the following operations on finite sequences (the empty sequence is also allowed) consisting of integers between $1$ and $N$, inclusive:

  1. Remove two consecutive occurrences of the same number between $1$ and $N$, inclusive.
  2. Insert two consecutive occurrences of the same number between $1$ and $N$, inclusive, at any position (the beginning and the end are also allowed).
  3. For integers between $1$ and $N$, inclusive, $i$ and $j$ such that $|i-j| > 1$, rewrite adjacent $i, \ j$ as $j, \ i$.
  4. For an integer at least $1$ and $N$ less than, namely $i$, rewrite adjacent $i,\ i+1, \ i$ as $i+1, \ i, \ i+1$.
  5. For an integer at least $1$ and $N$ less than, namely $i$, rewrite adjacent $i+1, \ i, \ i+1$ as $i,\ i+1, \ i$.
When a sequence $B_1, \dots, B_L$ can be obtained from a sequence $A_1, \dots, A_K$ consisting of integers between $1$ and $N$, inclusive, by repeating these five types of operations some number of times, freely choosing an operation each time, we say that the sequences $A$ and $B$ are "connectable".
Now, given sequences $A_1, \dots, A_K$ and $B_1, \dots, B_L$ from the input, consisting of integers between $1$ and $N$, inclusive, determine whether they are connectable, and print YES if they are connectable and NO otherwise.

Input

$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.$

Output

Print a newline at the end.

Sample

Sample 1
Input
1 3 2
1 1 1
1 1
Output
NO

When $N = 1$, the problem reduces to determining the parity of $K - L$.

Sample 2
Input
4 4 6
3 2 4 3
2 3 4 2 3 4
Output
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$

Sample 3
Input
100 7 8
3 8 13 18 23 28 33
4 8 12 16 20 24 28 32
Output
NO

The operations given in the problem statement do not change the parity of the length of the sequence, so these sequences cannot be transformed into each other.

Sample 4
Input
100 2 6
1 1
99 100 99 100 99 100
Output
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もしくは右上の雲マークをクリックしてアカウントを作成してください。