No.3427 Erasing a Subsequence
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 14
作問者 :
syndrome
/ テスター :
まみめ
harel
hirayuu_yc
rogi52
遭難者
kidodesu
👑
ArcAki
Eku
タグ : / 解いたユーザー数 14
作問者 :
まみめ
遭難者
kidodesu
👑
問題文最終更新日: 2026-01-12 11:30:33
問題文
長さ $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$ 未満の範囲から一様ランダムに生成される。
- 入力はすべて整数
入力の生成方法
次のようにテストケースを生成した。
- $N, M$ を制約を満たす範囲から選ぶ。
- $T_i \;(1 \leq i \leq M)$ を $0$ 以上 $1000$ 未満の範囲から一様ランダムに生成する。
- $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もしくは右上の雲マークをクリックしてアカウントを作成してください。