Atcoderの過去問Sequence Decomposing (AtCoder Beginner Contest 134 E)を解いているとき、面白いひらめきが得られたので書き残しておきます。

ザ・ゲームによるSequence Decomposingの考え方

突然ですが、この問題はそこそこ有名なボードゲーム、ザ・ゲームに置き換えて考えることができます。
ザ・ゲームの詳細な説明は省きますが、大まかなルールは以下となります。

• 各プレイヤーに配られたカードを手札とし、順番に出していく
• カードを出すための場が4つある
  • 2つの場は1から大きい方向へ、残り2つの場は100から小さい方向へ出していくことができる
  • ただし、飛ばされた数字は後から出すことができない
• 全員がカードを出し切ればクリア

そしてをザ・ゲームのルールから着想を得て、以下のようなルールに置き換えます。

• N枚のカードを手札とし、これを決まった順番で出していく
• カードを出すための場は自由に増やすことができる
  • いずれの場も大きい方向へのみ出していくことができる
  • ただし、飛ばされた数字は後から出すことができない
  • 場を増やしたい場合は、任意の数字のカードを出すことができる
• 全てのカードを出し切ればゲーム終了

このルールに置き換えた場合、できるだけ場の数が増えないようにカードを出していくと、全てのカードを出し終えたときの場の数がSequence Decomposingにおける答え（色の数）になります。

で、実際に解く際のデータの持ち方としては、「各場に出された最後のカード（数字）をソート済リストで保持」しておけばOKです。
どの場にカードを出すかを決定する際は、各場に出された最後のカード（数字）さえ分かればよいので、場に出されたカードを全て記録し続ける必要はありません。

ソースコード

解いている問題の本質は同じなのでソースコードは他の人と大差ないと思いますが、一応載せておきます。

言語はPythonで、二分探索のライブラリbisectを使用しています。

import bisect

n = int(input())
A = []

for i in range(n):
    A.append(int(input()))

colors = []
for i in A:
    target_index = bisect.bisect_left(colors, i) - 1
    if target_index < 0:
        colors.insert(0, i)
    else:
        colors[target_index] = i

print(len(colors))

↑のコードのは比較的シンプルで理解しやすい書き方ですが、colors.insert()が遅く、計算量が大きいという欠点があります。
そこで多少可読性は下がりますが「予め配列を確保しておいてインデックスをずらす」という手法を取ると以下のようになります。

import bisect

n = int(input())
A = []

for i in range(n):
    A.append(int(input()))

colors = [-1] * n
length = 0

for i in A:
    target_index = bisect.bisect_left(colors, i, n-length, n) - 1
    colors[target_index] = i
    if target_index < n-length:
        length += 1

print(length)

前者では1800msec程度かかりましたが、後者では220msec程度となり、高速な処理ができるようになりました。

所感

というわけで、自分が問題を解いていた時に頭に思い描いていた思考法を言語化してみました。
ボードゲームも制約条件の下で最適解を目指す事が多いですが、まさかこんなところで役立つとは思いませんでした。
公式の解説が理解できない…！といったような方の理解の助けになれば幸いです。（といっても、ボードゲームが分かる人にしか通じないかもしれませんが…）

そしてその後、さらに公式の解説を読んだらLIS(Longest Increasing Subsequence)やLDS(Longest Decreasing Subsequence)、といったキーワードが。
この辺りはちゃんと理解できているか分からないので、あとで読んでおきたいなぁ。