問題 問題概要 N個の寿司が並んでいる。順番に食べていくが、連続して食べることはできない。寿司にはおいしさがそれぞれ決まっている。食べた寿司のおいしさの合計の最大値を求めよ。またどの寿司を食べたかも求める。経路復元。 解法 動的計画法で解く。dp…

問題 問題概要 SをTにするときの編集距離の最小を求める問題。編集距離のdpの漸化式については以下のサイトが参考になる。 解法 dpで解くことができる。 dp[i][j] := 文字列Sのi番目までで、文字列Tのj番目までを作ることを考えた時の操作回数の最小値として…

問題 問題概要 a,b,cのどれかの倍数になる数字の個数を求める。 解法 包徐原理で解く。高１のどっかでやる3つの場合の公式を使えば解くことができる。 wikipediaの3つの有限集合に対して書かれている公式をそのまま使えばいい。 包除原理 - Wikipedia 集合a,…