問題 解法 以下 0-indexed とする。 の場合、区間を一方向に伸ばしながら Segment Tree 上の二分探索を行うなどして求める。 それ以外のとき、各 に対し、自身より大きい値か小さい値かしか興味がないので便宜上 + と - とおく。 (1) +0+ や -0- のとき この…

問題 解法?（本題とは関係なし） まず、dp[i][j][k] = i 個目まで見て末尾が j で k 個続いているものの個数 として各要素の遷移に かけて全体 のコードができる。 （下記コードのコメントアウト部分に対応） 簡単に思いつく高速化としてほとんどの a は dp[…

問題 解法 「mex を追加する、または mex 以外を追加する」という操作において、種類数という情報だけで遷移元と遷移先を表現できる（情報として十分である）ということに注目する。 dp[i] = 数列の要素が i 種類 とすると mex を追加する場合: 種類数だけで…

解説ACした。最適化が苦手。 問題のリンク 概要 正整数 が与えられるので、 が の倍数になるような非負整数 の組に対し、 の最小値を求めよ。 解説 のとき となる。(そもそも となる必要があるため) のとき であるとする。 は解なので、 のとき、 となるので…