問題一覧 > 通常問題

No.2254 Reverse Only

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 54
作問者 : noya2noya2 / テスター : shobonvipshobonvip 👑 NachiaNachia
3 ProblemId : 9150 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-24 19:06:32

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\dots ,A_N),B=(B_1,B_2,\dots ,B_N)$ と正整数 $k$ が与えられます。

次の操作を $0$ 回以上行って $A$ を $B$ に一致させられるか判定してください。

  • $1\le l\le r\le N, r - l + 1 \ge k$ を満たす整数 $l,r$ を選ぶ。
  • $A$ の $l$ 項目から $r$ 項目までを反転させる。 つまり、$A_l,A_{l+1},\dots ,A_{r-1},A_r$ を $A_r,A_{r-1},\dots ,A_{l+1},A_l$ で同時に置き換える。

    • 制約

  • 入力はすべて整数
  • $1\le N\le 2\times 10^5$
  • $1\le k\le 2\times 10^5$
  • $1\le A_i,B_i\le 2\times 10^5\ (1\le i\le N)$

    • 入力

    $N$ $k$
$A_1$ $A_2$ $\dots A_N$
$B_1$ $B_2$ $\dots B_N$

    出力

    操作を $0$ 回以上行って $A$ を $B$ に一致させられるなら Yes を、そうでないなら No を出力してください。

    サンプル

    サンプル1
    入力
    4 3
3 4 1 2
1 2 3 4
    出力
    Yes

    $2$ 回の操作で一致させられます。

    $1$ 回目は $l=1,r=3$ とします。$2$ 回目は $l=2,r=4$ とします。数列 $A$ は次のように変化します。

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

    $A$ を $B$ に一致させることができるので Yes を出力します。

    サンプル2
    入力
    5 6
1 2 3 4 5
1 2 3 4 5
    出力
    Yes

    操作することはできませんが、はじめから一致しています。

    サンプル3
    入力
    3 1
3 1 4
1 5 9
    出力
    No

    一致させることはできません。

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