今日解いた競プロの問題。

ABC237-F: 解説AC。といいつつ、解説にはほぼdpテーブルの形しか書いてなかったので、自分で考察し直した。

まず簡単な場合として、LISが3ではなく1の数列の個数を数えることを考える。左から決めていくとしてこの場合、今まで出た中で最小の値よりも大きい数にしてしまうとLISが2以上に伸びてしまうので、今まで出た最小値をdpの状態として持っておく必要がある。その最小値以下の値のみ採用していけば良い。

次にLISが2の数列の個数を数えることを考える。ある数kがあって、k以下の値のみでLISが2になる場合、kより大きい数を追加すればLISが3に伸びてしまうので、このようなkをdpの状態として持たなければならない。また長さ2のLISに遷移することを考えて、長さ1のLISを構成する最小値(=今まで出た最小値)も持たなければならない。ということで、長さ2のLISを構成する最小値以下の値のみ採用していけばよい。

LISが3の数列も同様の発想で数えられる。長さ1のLISを構成する最小値、長さ2のLISを構成する最小値、長さ3のLISを構成する最小値をそれぞれ持てば良い。空間$O(NM^3)$の時間$O(NM^4)$となる。Mが小さいためこれで通る。

---

作業がなかなか手に付かない。何とか授業の復習1個と課題2個を終わらせた。

授業をなかなか集中して聞けないのだが、先に授業後の課題を見ておけば良いのではないかと考えた。現状だとどこが解けず、何の知識が足りないのかをあらかじめ自覚しておく作戦。