問題 問題概要 省略 解法 ナップザック問題に選んでいい品物の個数を制限する制約を追加した問題。 dp[i][j][l] := i番目のスクショまで見て、j枚貼り、幅lを使っているときの重要度の最大値 として、ループで値を埋めていく。 ミス なし。 コード #include <iostream></iostream>…

問題 問題概要 省略 解法 nやkは小さいので、全探索できるな。でも、kが毎回変わるから、単純にループを書こうと思うと、kに応じて、ループの回数を変えたコードを書かなければならなくなり、めんどくさいので、dfsで何回ループをしなければならないかを引数…

問題 問題概要 木のグラフが与えられる。その木に対して、辺を１つ加えでできる、閉路の長さを答える。 解法 まず、LCAを求める。LCAについては、蟻本。多くのクエリが与えられるので、いちいち親をたどっていては、間に合わない。そこで、頂点vから、2k回上…

問題 問題概要 与えられた文字列から、部分文字列として、共通のもの(T)を取り出し、S = T + TのSの長さを求める問題。 解法 まず、与えられた文字列を2つに分ける。その後、その2つの文字列の最長共通部分列(LCS)の長さを求めて、2倍したものが答えの候補と…

問題 問題概要 スペース入りのアルファベットンの文が与えられるので、単語ごとの頭文字をとり、それをつなげたものを表示する問題。 解法 まず、name[0]は必ず、頭文字になる。そのあとは、スペースのあとの文字が必ず頭文字になるので、スペースのあとの文…