問題文 : 塗り箸解法 : dp[i][j] : 区間[i, j]を塗るためのコストの最小値, とするとdp[i][i] = 1, dp[i][j] = for(k = i...j - 1) min(dp[i][k] + dp[k + 1][j]) - (t[i] == t[j])となる. これは, 区間の幅を小さいものから計算すれば実現できる.コード : #…

問題文 : スキー解法 : 全体の平均速度について2 分探索を行う. ある平均速度vを決めると, その平均速度でt 秒間高原を滑るとtv [m] 進むこととなる. 通った道のりの総和S と, 滑った時間の総和Tについて, S ≦ Tvを満たせば, その平均速度vで高原を滑り抜け…

問題文 : 判子解法 : まず, この作業でスタンプを作ることは, スタンプからIOIOI...OIの形を復元することを考える. このとき, 境界条件を考えないために, IO と OI を文字列に連結する. このとき, "OOO"や"III"の形で連結されている箇所があれば, 真ん中を変…