問題一覧 > 通常問題

No.3427 Erasing a Subsequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 14
作問者 : syndrome / テスター : まみめ harel hirayuu_yc rogi52 遭難者 kidodesu 👑 ArcAki Eku
ProblemId : 12888 / yukicoder contest YNUCPC Contest 2 (順位表) / 自分の提出
問題文最終更新日: 2026-01-12 11:30:33
yukicoder contest YNUCPC Contest 2の他の問題:

問題文

長さ $N$ の数列 $S = (S_1, S_2, ..., S_N)$ と長さ $M$ の数列 $T = (T_1, T_2, ...,T_M)$ が与えられます。

ここで、$S$ は連続とは限らない部分列として $T$ を取り出す方法が $1$ 通り以上あることが保証されます。

$S$ から $T$ を取り除いた数列であって辞書式順序が最小になるものを出力してください。

ただし、$T_i \;(1 \leq i \leq M)$は $0$ 以上 $1000$ 未満の範囲から一様ランダムに生成した値です。

辞書式順序とは?
長さ $n$ の $2$ つの数列 $A = (A_1, A_2, ...,A_n)$ と $B = (B_1, B_2,...,B_n)$ があるとき、
$A < B$ であることを、以下の条件を満たす $i\;(1 \leq i \leq n)$ が存在することと定義したものを辞書式順序と呼びます。

  • $A_i<B_i$
  • $1$ 以上 $i$ 未満のすべての $j$ について $A_j = B_j$

入力

  • $1 \leq M \leq N \leq 1000$
  • $0 \leq S_i < 1000$
  • $T_i \;(1 \leq i \leq M)$は $0$ 以上 $1000$ 未満の範囲から一様ランダムに生成される。
  • 入力はすべて整数

入力の生成方法
次のようにテストケースを生成した。

  1. $N, M$ を制約を満たす範囲から選ぶ。
  2. $T_i \;(1 \leq i \leq M)$ を $0$ 以上 $1000$ 未満の範囲から一様ランダムに生成する。
  3. $S$ を、生成した $T$ を含むように生成する。$S_i \;(1 \leq i \leq N)$ は一様ランダムには生成していない。

入力は以下の形式で標準入力から与えられます。

$N \; M$  
$S_1\;S_2\;...\;S_N$  
$T_1\;T_2\;...\;T_M$

出力

答えとなる数列を空白区切りで $1$ 行に出力してください。

サンプル

サンプルは恣意的に作成したものであり、テストケースにも含まれません。

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

答えが空文字列になる場合、空行を出力してください。

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