昨日CodeChefの問題に出てきて分からなかったんですが、有名問題ぽい見た目をしているのにどう検索していいかよく分からなかった。 問題 自然数からなる長さの等しい数列 , であって、次の条件： を満たす時、 の最小値を求めよ(数列長は自由に取って良いも…

人と違う解法(?)だったのでメモ書き リンク codeforces.com 問題概要 長さNの数列が与えられ、次の操作を何回でも行うことができる。 隣接する値が同じ項を選んで、取り除く。そしてそこに元の値+1の要素を挿入する この時達成可能な数列の長さの最小値を求…

リンク https://codeforces.com/contest/808/problem/E 問題概要 ナップサック問題 ただ制約が特殊 解法 い つ も の dp[i]:iの重さを持つ時の価値の最大値,というDPは計算量がO(NM)になってしまい間に合わない。 明らかに怪しい制約があるのでそれを生かす…