最長増加部分列ってどちら様？？？ -AtCoder学習日記 #4

概要

今回はARC125-Cについてです。
今回の問題に至っては問題文の理解から時間がかかりました。最長増加部分列(LIS)についての問題のようです。

私事：やっと茶色に乗ることができました！！！

最長増加部分列とは？

部分列

そもそも最長増加部分列を理解する前に、部分列について知る必要がありそうです。
部分列とは、「ある数列のうち、いくつかの項を取り出して順番を変えずに作れる数列」のことです。

例えば数列を考えると、は部分列ですし、も部分列です。
途中の項を飛ばしてもOKですが順番を変えるのはNGです。
そのため、は部分列ではありません。

増加部分列

次に増加部分列の説明です。
増加部分列は「となる部分列」のことです。

例えば数列を考えると、は増加部分列ですし、も増加部分列です。
すべての項において常に増加するため、は増加部分列ではありません。

最長増加部分列

最後に最長増加部分列についてです。
最長増加部分列は「増加部分列の内、最長のもの」です。
先程の例の数列だとが最長増加数列です。

ACになるコード

n, k = map(int, input().split())
a_list = list(map(int, input().split()))

ans = []
used = [0] * (n + 1)
i = 1
for a in a_list[:-1]:
    ans.append(a)
    used[a] = 1
    while i < a:
        if used[i] == 0:
            ans.append(i)
            used[i] = 1
            i += 1
            break
        i += 1

for j in range(n, i - 1, -1):
    if used[j] == 0:
        ans.append(j)

print(" ".join(map(str, ans)))

指定された数列を入れつつ、入れられるところは小さい数字から入れていくって感じですね。
その後、余った数字は単調に減少するようにします。

まとめ

• 最長増加部分列は「増加部分列の内、最長のもの」
• 再帰的に考えてみるのもあり
• やっと茶コーダー！

参考文献

部分列 | 数列 | 実数 | 数学 | ワイズ yukicoder.me