CS6.006で習ったことだし、DPに強くなりたい。 問題は以下。 atcoder.jp 状態遷移図を書く。 遷移図 一つのノードから分岐する全てのノードを網羅できるようなサブ問題を考える。 ここでは、根ノードとそこからわかれる二つのノードを網羅する例を考えている…

わかったこと 文字列系のDPでよく使われるsub-problem prefix suffix substring 当然といわれれば当然。prefixとsuffixをどちらも使いそうな時はつまりsubstringである。 pseudo polynomial ナップザック問題： ナップザックに、重さ、価値の品物を入れるか…

ふと、まとまった時間でアルゴリズムを学び直したいと思った。 いつ転職しても(させられても)いいように。 MITのCS 6.006という講座がある。2011年の秋学期にMITで行われたアルゴリズムの授業であり、ほぼ全てのリソースが無料で公開されている。 G社に内定…

問題はこちら 意訳が間違っていたらご指摘ください。 フォーマットの説明 問題文 思考方法→答え の順で書いています。 Problem 5-1 base = 256、つまり256進数で表された整数の計算をするプログラムについて。 base = 256なので、我々が普段使う10種類の0-9…