atcoder.jp LCS(Longest Common Subsequence)をもとめよう。 典型典型と言ってるわりに以外に詰まった問題。反省しろ。 文字列の中身を1文字目, 2文字目, 3文字目...とすると dp[i][j]: 一つ目の文字列が i 文字目まで、二つ目の文字列が j 文字目まで見た時…

atcoder.jp 前回の続き。 しばらく普通のしゃくとりの例題と実装を説明するので上の問題の解説はしばらく後。 普通のしゃくとり法 普通のしゃくとり法は、条件を満たす区間の中で最善になる可能性のあるものを、区間の両端を動かすことにより求める。 たとえ…

atcoder.jp 最大20万の長さの自然数列を与えられ、そこにしきりを3ついれて、4つに分割する。4つの数列の和の最大値と最小値の差を最小化するとき、その差はいくつになるか。 例） 5 2 3 6 1 3 2 ベストな分割方法は{5}, {2, 3}, {6}, {1, 3, 2}にして和は5,…